为什么我插入STL列表运行缓慢？

Question

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

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编译器.我知道列表末尾的插入可以在恒定的时间内完成,那为什么第一个代码运行缓慢？是否有机会优化链表实施？

提前致谢

Answer 1

插入列表需要分配新节点.因此,当您进行6000次回拨时,您必须进行6000次内存分配.在数组的情况下,您根本不需要进行任何分配,因此速度要快得多.这是完全不同的.

Answer 2

避免std::list.这是一个双向链表,非常缓存不友好(节点随机分布在内存中)并且涉及很大的开销(每个元素2个指针).因此,每次附加内容时,列表都会分配2*sizeof(void*)+sizeof(int)字节,还会分配一些内存管理开销operator new.

在算法的后面,当你迭代这些值时,你会在整个内存中跳转,这会更慢.

2d阵列没有这个问题,但它确实浪费了一些内存.

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

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

请注意,矢量也可以是push_back值O(1)(以及a std::deque,它可以追加得更快但在遍历时更慢).如果预期图形是密集的,则邻接矩阵可能是更好的选择.