分类
Algorithm C++

C++之父:链表是原罪吗?

翻译改编自https://isocpp.org/blog/2014/06/stroustrup-lists

链表是原罪吗?

作者:Bjarne Stroustrup

根据Web的某些角落,我的印象是向量总是比链表更好,而且我不了解其他数据结构,例如树(例如std::set)和哈希表(例如std::unordered_map)。显然,那是荒谬的。

问题似乎是约翰·本特利曾向我提出的一个有趣的小练习:将一系列随机整数插入到一个排序的序列中,然后按照原位置的顺序逐个删除这些元素定:你是否使用了vector(连续分配的元素序列)或list?我用这个例子来说明一些观点,鼓励思考算法,数据结构和机器架构,得出结论:

  • 不要不必要地存储数据
  • 保持数据紧凑
  • 以可预测的方式访问内存。

注意结论中没有vectorlist。请不要将示例与示例中的示例混淆。

这个例子的目的是说明一些一般原则并让人们思考。最初,大多数人说“当然选择list!”(我已经多次尝试过这个问题),因为“中间”有许多插入和删除(list很擅长)。这个答案是完全错误的。

我多年来一直在使用这个例子,并且让研究生实施并测量了这个练习和不同练习的几十种变体。其他人的例子和测量可以在网上找到。

  • 我尝试了map(它们比list要好得多,但仍比vector慢)
  • 我已经尝试了更大的元素大小
  • 我使用Binary Search和暴力插入向量(是的,它们甚至进一步加速)
  • 我查看了我的理论(不,我没有违反任何大O复杂性规则;只是某些操作对于一个数据结构而言比另一个更加昂贵)
  • 我有预先分配的链接(这比std::list遍历仍然性能更好)
  • 我使用了单链表forward_lists,(这没有多大区别,但是确保用户代码100%相当有点难度)
  • 我知道(并且说)500K列表并不常见(但这对我的要点无关紧要)。我们使用许多结构(大型和小型),其中可以选择链接和连续的表示。
  • 我知道listpush_front()更快,vectorpush_back()更快

我的观点不是关于列表。它们有它们的用途,但这个例子不是其中之一。请不要将示例与示例用于说明的内容混淆。这个例子是关于内存的使用:我们经常创建一个数据结构,对它进行一些需要访问的计算(通常是遍历),然后删除它。有序序列只是这种用法的一个例子,并且提供了示例以让人们思考在这种情况下重要的事情。我的建议是:

  • 不要不必要地存储数据
  • 保持数据紧凑
  • 以可预测的方式访问内存。

我强调cache的重要性。根据我的经验,除了真正的专家外,所有人都倾向于在讨论算法时忘记这些。

而且,是的,我的推荐是默认使用std::vector。更一般地说,除非有充分的理由不使用,否则请使用连续的表示。与C一样,C++默认设计用于执行此操作。

此外,请不要在没有测量的情况下对性能做出声明。我已经看到过这样一种情况,即将0-2元素列表更改为0-2元素向量会使算法产生因子2的差异。Nobody cares this.

发表评论

电子邮件地址不会被公开。 必填项已用*标注