C Graph Adjazenzliste Implementierung wachsenden Nachbar Array

Question

Ich fand eine Implementierung und ging durch den Code und ein Teil scheint mir unklar.

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]; 
}; 

in der graph_add_edge Funktion

/* 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)); 
} 

warum die Länge verdoppelt werden müssen? Warum wird es überhaupt benötigt? ist es nicht immer d + 1 (Anzahl der Nachfolger + 1), um Platz für den nächsten Gegenstand zu schaffen?

Full code

Answer 1

Weil es in Bezug auf die CPU-Zeit weniger kostspielig ist die Größe jedes Mal, wenn Sie mehr Speicherplatz benötigen, zu verdoppeln, statt nur 1 auf die Größe der Zugabe. Im letzten Fall wird für jede neu hinzugefügte Kante realloc aufgerufen, und realloc ist ziemlich teuer. Stellen Sie sich vor Sie haben 128 Kanten: realloc wird 128 Mal aufgerufen, aber wenn Sie die Größe jedes Mal verdoppeln, wird es nur 7 = log2(128) mal aufgerufen.

Außerdem realloc wird höchstwahrscheinlich langsamer, je länger Teil der ursprünglichen Speicher sein, weil realloc möglicherweise eine der alten Speicherabschnitt Puffer auf eine neue, größere kopieren, und je länger der Abschnitt ist, desto länger das Kopieren stattfinden wird.