-3

我们应该使用哪种数据结构来实现最快的顺序访问？

  • 向量
  • 单链表
  • 双向链表

非同步数据结构是什么意思？有些人称向量同步，但有些人不。

数组可以以随机方式和顺序访问方式访问，但是 LL 只能以顺序访问方式访问，那么当顺序访问时，如何确定数组是快速的还是 LL 呢？

4

3 回答 3

1

所有这三个项目都可以直接访问序列中的下一个项目。那说：

虽然向量、链表和双链表的顺序访问的复杂性可能相同；毫无疑问，向量几乎总是会提供最佳的实际性能。在查看方法的性能时，会考虑很多因素，而不仅仅是操作的 O(n) 或 Θ(n)。

最新的 C++ 规范中的向量保证了连续的内存分配（意味着项目在内存中紧随其后），这意味着从内存中查找一个对象将导致附近的对象也被加载到 L2 和 L1 缓存中（空间局部性）。这意味着访问同一向量中的后续项目将快得多，因为 CPU 不需要从内存中获取内容。

对于反向迭代，双链表和向量都会让你 O(1) 访问下一个（读取：上一个）项目，但同样的问题仍然存在。双链表必须执行多个操作才能到达下一个节点（但它是固定数量的操作，因此是 O(1) 值），包括读取指向下一个对象的指针的值，并加载该对象访问其内容的地址。向量在这里总是占上风。

向量还可以让您直接访问任何随机节点。双链表和单链表都不能这样做 - 您必须从头开始迭代（end 也是双链表的一个选项）才能获得随机索引。

基本上：99% 的时间，你应该使用向量。永远不要依赖 O(n) 或 Θ(n) 来获得实际性能，因为它隐藏了许多重要的指标。向量的缺点是，如果元素的数量超过了预先保留的空间量，则向量必须调整大小（通常这需要将所有数据复制到新位置）。一定大小的智能预留可以缓解这个问题；通常通过使用链表“解决”这个问题是过度热心的预优化，最终会伤害而不是帮助。

于 2012-12-02T10:47:56.410 回答
1

数组可以以随机方式和顺序访问方式访问，但是 LL 只能以顺序访问方式访问，那么当顺序访问时，如何确定数组是快速的还是 LL 呢？

因为顺序访问，当以随机访问的方式实现时，与从开始到实际寻找的替代方案相比将是恒定的n，这在时间上是线性的。

对于具有随机访问的容器，元素的顺序访问n可能如下所示：

cursor := getStartCursor()
cursor := cursor+n
getElementAt(cursor)

对于只有顺序访问的容器，它必须如下所示：

cursor := getStartCursor()
for i = 0 to n:
    cursor := getNextCursor(cursor)
getElementAt(cursor)

并且单个add操作与n取消引用属于不同的算法复杂性类别。

打个比方，顺序访问就像寻找复活节彩蛋一样，在没有找到前四个线索的情况下，你不能跳到第四个彩蛋。相比之下，每个鸡蛋所在位置的地图将使您能够随时前往您喜欢的任何鸡蛋，包括按原始顺序。

于 2012-12-02T10:43:36.550 回答
-2

访问的方向也很重要：从前到后：所有这些都是相等的（尽管取决于向量实现，它可能会快一点 - 分配与增量）

如果您可能需要在两者之间反转：双链表和向量（感谢 Mahmoud 指出这一点！）

于 2012-12-02T10:41:12.690 回答