2

我正在尝试使用邻接表实现无向图。我使用了以下代码：

int v,e;
scanf("%d%d",&v,&e);
list<int> graph[3000];
for(int i=0;i<e;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    graph[a].push_back(b);
    graph[b].push_back(a);
}

为了测试我的代码的运行时间，我创建了一个包含 3000 个顶点和所有可能边的输入文件。运行时间为 2.2 秒。我尝试通过将其更改为二维数组来进行优化，如下所示

int graph[3000][3000];

for(int i=0;i<e;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    graph[a][p[a]]=b;
    graph[b][p[b]]=a;
    p[a]++;
    p[b]++;
}

其中“p”的大小为 3000，初始化为全零。对于相同的输入文件，此代码仅在 0.35 秒内运行。我正在使用 gcc-4.3.2 编译器。我知道在列表末尾插入可以在恒定时间内完成，那么为什么第一个代码运行缓慢？是否有机会优化链表实现？

提前致谢

4

3 回答 3

7

避免std::list。这是一个双向链表，它对缓存非常不友好（节点随机分布在内存中）并且涉及大量开销（每个元素 2 个指针）。所以每次你追加一些东西时，列表都会分配2*sizeof(void*)+sizeof(int)字节和额外的一些内存管理开销operator new。

稍后在算法中，当您迭代这些值时，您实际上会跳过整个内存，这会更慢。

二维数组没有这个问题，但确实浪费了一些内存。

我通常将邻接表表示为向量的向量。

std::vector<std::vector<int> > graph;

请注意，向量也可以push_back取值O(1)（以及 a std::deque，它可以更快地追加，但在遍历时更慢）。如果预计图是密集的，那么邻接矩阵可能是更好的选择。

于 2013-04-06T20:31:11.363 回答
6

插入列表需要分配一个新节点。因此，当您进行 6000 次推回时，您必须进行 6000 次内存分配。在数组的情况下，您根本不需要进行任何分配，因此速度要快得多。这就是全部的区别。

于 2013-04-06T20:21:44.517 回答
0

要在这里扩展答案，请自己实现一个链表类，您会发现它为什么很慢。

可以做一些事情，例如实现一个包含容量值、大小值和指向实际列表中第一个节点的指针的列表。该指针实际上是一个动态数组，当 size==capacity 时，数组被调整大小并且容量增加了一些因子（例如 10）。

缺点是它被限制为 2^(sizeof capacity * CHAR_BIT) - 1 个元素，而每次仅分配节点涉及更长的插入时间，而理论上节点数量不受限制。在将更快的列表实现的容量最大化之前，您很可能会用完内存，但不能保证这一点，更不用说调整列表的大小通常涉及对其进行复制，因此最大容量突然变得很大无论如何，它的限制较小。

链表通常很慢。它们有其用途，但如果您需要更快的运行时间，找到更好的实现，使用不同的容器，例如 std::vector，或者自己创建一个解决方案，尽管老实说标准容器做得很好。

于 2013-07-04T17:22:14.220 回答