正如标题所暗示的，我的程序有问题，我使用 std::list 作为堆栈并迭代列表的所有元素。当列表变得非常大时，该程序花费的时间太长了。
有人对此有很好的解释吗？它是一些堆栈/缓存行为吗？
（通过将列表更改为 std::vector 和 std::deque 解决了这个问题（顺便说一句，这是一个了不起的数据结构），一切都突然变得更快了）
编辑：我不是傻瓜，我不会访问列表中间的元素。我对列表所做的唯一一件事就是在末尾/开头删除/添加元素并遍历列表的所有元素。而且我总是使用迭代器来迭代列表。
问问题
7292 次
6 回答
26
列表具有糟糕的（不存在的）缓存局部性。每个节点都是一个新的内存分配，并且可能在任何地方。所以每次你跟随一个从一个节点到下一个节点的指针时，你都会跳到内存中一个新的、不相关的地方。是的，这会严重影响性能。缓存未命中可能比缓存命中慢两个数量级。在向量或双端队列中，几乎每次访问都将是缓存命中。向量是一个连续的内存块，因此迭代它的速度与您将获得的一样快。双端队列是几个较小的内存块，因此它会引入偶尔的缓存未命中，但它们仍然很少见，并且迭代仍然非常快，因为您获得的大部分缓存命中。
一个列表将几乎所有缓存未命中。性能会很糟糕。
实际上，从性能的角度来看，链表几乎不是正确的选择。
编辑：正如评论指出的那样，列表的另一个问题是数据依赖性。现代 CPU 喜欢重叠操作。但是如果下一条指令取决于这条指令的结果，它就不能这样做。
如果您正在迭代向量，那没问题。您可以即时计算要读取的下一个地址，而无需检查内存。如果您现在正在阅读地址x，那么下一个元素将位于x + sizeof(T)T 是元素类型的地址。所以那里没有依赖关系，CPU 可以立即开始加载下一个元素或之后的元素，同时仍处理较早的元素。这样，数据将在我们需要时为我们准备好，这进一步有助于掩盖访问 RAM 中数据的成本。
在一个列表中，我们需要跟随一个从节点i到节点的指针i+1，直到i+1被加载，我们甚至不知道去哪里寻找i+2。我们有数据依赖，所以 CPU 被迫一次读取一个节点，它不能提前开始读取未来的节点，因为它还不知道它们在哪里。
如果一个列表不是所有的缓存未命中，这不会是一个大问题，但是由于我们得到了很多缓存未命中，这些延迟是代价高昂的。
于 2009-09-09T22:44:16.800 回答
3
这是由于使用列表时会出现大量缓存未命中。使用向量，周围的元素存储在处理器缓存中。
于 2009-09-09T22:36:53.540 回答
1
看看下面的stackoverflow 线程。
于 2009-09-09T22:37:21.817 回答
1
有一个缓存问题：vector 中的所有数据都存储在一个连续的块中，并且每个列表元素都是单独分配的，并且可能恰好存储在相当随机的内存位置，这会导致更多的缓存未命中。但是，我敢打赌，您会遇到其他答案中描述的问题之一。
于 2009-09-09T22:42:16.710 回答
0
简单的答案是因为迭代向量根本不是迭代，它只是从数组的底部开始并一个接一个地读取元素。
我看到这被标记为 C++，而不是 C，但是由于它们在幕后做同样的事情，因此值得指出的是，您可以通过将元素分配到任意大的数组，以及 realloc()ing 和 memmove 来将元素添加到数组的开头和结尾() 在 2 个伴随数组之间运行，如果并且当您用完空间时。非常快。
将元素添加到数组开头的技巧是通过在开头将指针推进到数组中来偏置数组的逻辑开头，然后在前面添加元素时将其备份。（也是堆栈的实现方式）
以完全相同的方式，可以使 C 支持负下标。
C++ 使用向量 STL 类为您完成了所有这些工作，但仍然值得记住幕后发生的事情。
于 2013-08-19T06:41:53.117 回答
-2
[编辑：我的立场是正确的。std::list 没有运算符 []。对不起。]
从您的描述中很难分辨，但我怀疑您试图随机访问这些项目（即按索引）：
for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }
而不是使用迭代器：
for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }
“向量”和“双端队列”都擅长随机访问，因此在这两种情况下都可以充分发挥这些类型的性能——O(1)。但是“列表”并不擅长随机访问。按索引访问列表需要 O(n^2) 时间，而使用迭代器时需要 O(1) 时间。
于 2009-09-09T22:37:53.910 回答