データの持ち方。

大きなデータを扱う際などは、使われ方に応じて持つこととよい。というのもかなりの効果を得ることができるからである。以前までは以下のように構造体に配列の先頭を指すポインタを宣言し、後にメモリを動的確保していた。

typedef struct {
　int nodeNum;
　int arcNum;
　int maxLength;
　int minLength;
　int *head;
　int *length;
　int *incident;
　int *potential;
　int *prevNode;
} graph_t;

しかし最適化問題を実装する際には、複数の配列の同一 ID を参照する機会が多い。最短経路問題では、特に次の２つついてである。

１．接続点 (head[ ])と、その長さ(length[ ])
２．ポテンシャル(potential[])と、直前接点(prevNode[ ])と、
　　点から出ている枝・その長さを保存している ID (incident[ ])

しかしこのようなデータの持ち方をしてしまうと、せっかく同じタイミングでデータを参照するのに各配列に別々にアクセスしなければならない。そこで同じタイミングで参照するデータは近くに持つことが望ましい。

typedef struct {
　int head;
　int length;
} arc_t;

typedef struct {
　int incident;
　int potential;
　int prevNode;
} node_t;

typedef struct {
　int nodeNum;
　int arcNum;
　int maxLength;
　int minLength;
　arc_t *arc;
　node_t *node;
} graph_t;

このようにするだけでもかなり改善ができる。同じデータ型であれば配列のほうが良いと思われるが複雑なものであると混乱するので、まずはこのようにしてみるとよいだろう。