C图邻接表实现增长邻居数组

Question

我找到了一个实现并正在检查代码，但有一部分对我来说似乎不清楚。

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 可能会将旧的内存部分缓冲区复制到一个新的更大的缓冲区，并且该部分越长，复制的时间越长。

C图邻接表实现增长邻居数组

C graph adjacency list implementation growing neighbour array

c

graph

adjacency-list