Cグラフ隣接リストの実装

Question

実装を見つけてコードを実行していて、1つの部分がわかりにくいようです。

struct graph { 
    int n;    /* number of vertices */ 
    int m;    /* number of edges */ 
    struct successors { 
     int d;   /* number of successors */ 
     int len;  /* number of slots in array */ 
     char is_sorted; /* true if list is already sorted */ 
     int list[1]; /* actual list of successors */ 
    } *alist[1]; 
}; 

graph_add_edge機能で

/* do we need to grow the list? */ 
while (g->alist[u]->d >= g->alist[u]->len) { 
    g->alist[u]->len *= 2; 
    g->alist[u] = 
     realloc(g->alist[u], 
      sizeof(struct successors) + sizeof(int) * (g->alist[u]->len - 1)); 
} 

長さが倍増する必要もありませんなぜですか？それはなぜ必要なのでしょうか？次のアイテムのためのスペースを作るのに常にd + 1（後継者の数+1）ではないのですか？

Full code

Answer 1

それはサイズにあなただけの1のサイズに追加するのではなく、より多くのメモリを必要とするたびに倍増するCPU時間の点でより低コストだからです。

後者の場合、新しく追加されたエッジごとにreallocが呼び出され、reallocは非常に高価です。あなたは128エッジを持っていると想像してください：reallocは128回呼び出されますが、毎回サイズを倍増させると、それは7 = log2(128)回だけ呼び出されます。

reallocは、reallocが古いメモリ部分バッファを新しい大きな部分にコピーする可能性があり、部分が長いほどコピーが長くかかるため、元のメモリ部分が長くなるほど遅くなる可能性があります。