虽然之前有人问过关于链表与数组的问题,但答案大多归结为我们大多数人在某些时候可能已经学到的东西:
现在,像 Bjarne Stroustrup 这样受人尊敬的人已经argued https://www.youtube.com/watch?v=YQs6IC-vgmo数组实际上总是优于链表,因为它们更好地利用了现代硬件中实现的缓存架构。他还指出,阵列的性能优势随着其大小的增加而增加。
虽然我基本上理解他的论点并同意他的观点,但我想知道当数组的大小明显大于缓存大小时这是否仍然正确。我想说,在这种情况下,性能确实很重要。
总结一下:在大多数情况下,即使数组的大小远大于缓存大小并且大部分操作是插入或删除,数组的性能是否仍优于列表?如果是,这该如何解释?
数组的性能更好不仅因为缓存,还因为预取。
缓存有两个主要好处 - 顺序元素可能驻留在同一行中,因此您可以获取一次并多次使用整行(而在链接列表中,您的下一个元素位于其他位置,因此您无法享受到这种好处)。元素变得越大,这种好处就会减少,并且一旦元素超过线条尺寸,这种好处就会消失。
第二个好处更加微妙 - 您可以更好地利用缓存,因为它的组织方式有利于顺序分配。这意味着达到缓存大小的数组可能仍然适合,而随机分配的列表可能会存在一些冲突,即使列表大小小于缓存,也会导致颠簸。
然而,除了缓存之外,空间分配结构的更大好处是预取。大多数 CPU 会自动预取访问流(例如数组访问)中的下一行,因此会消除顺序访问场景中的所有未命中。
另一方面,所有这些好处都只是优化,因此它们只能线性加速性能,但永远无法减轻渐近复杂度差异,例如列表提供的 O(1) 插入。最终,您需要对代码进行基准测试,看看是否需要这种情况并创建瓶颈 - 如果是这样,可能需要混合方法。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)