为什么将c＃通用列表实现为仅追加数组？

Question

C＃通用列表System.Collections.Generic.List<T>是使用可增长数组作为后备存储来实现的，其方式类似于更多基于数组列表的实现。显然，当对例如实现为链接列表的列表执行随机（索引）访问时，这提供了巨大的好处。

但是我想知道为什么没有选择将其实现为圆形数组。对于索引随机访问并附加到列表的末尾，此实现将具有相同的O（1）性能。但这将提供其他好处，例如允许O（1）进行前置操作（即在列表的前面插入新元素），并且平均将随机插入和删除所需的时间减半。

到目前为止的一些答案摘要

如@Hachet所指出的，为了使圆形数组实现具有与相似的索引性能，System.Collections.Generic.List<T>将要求它必须始终增长到2的幂的容量（以便廉价的模运算可以执行）。这将意味着无法像当前构建列表实例那样将其大小调整为用户提供的准确初始容量。因此，这是一个明显的权衡问题。

而且，正如一些快速而肮脏的性能测试所表明的那样，对于圆形数组实现，索引编制可能会慢2-5倍。

由于索引是一个明显的优先事项，我可以想象这会付出太大的代价，而在前置操作中要获得更好的性能，而在随机插入/删除操作中要获得更好的性能。

这是重复的，带有一些补充答案信息

这个问题确实与为什么典型的数组列表实现不是双端的有关？，我在发布问题之前没有发现。我猜没有以完全令人满意的方式回答：

我还没有做过任何基准测试，但是在我看来，还有其他瓶颈（例如，非本地负载/存储）会大大超过此瓶颈。如果我没有听到更令人信服的消息，我可能会接受，谢谢。– Mehrdad '11 May 27'4:18

关于此问题的答案提供了有关如何使循环列表建立索引以使其表现良好的其他信息，包括代码示例以及使权衡决策变得更加清晰的一些定量数字。这样，它们提供的信息与另一个问题中提供的信息互补。因此，我同意这个问题的意图几乎是相同的，因此，我同意应将其视为重复。但是，如果现在附带的新信息丢失了，那将是一种耻辱。

另外，我仍然对实施选择的潜在其他原因感兴趣，而这两个问题的答案中可能还没有这些原因。

Answer 1

实际上，可以使用O（1）访问时间来实现圆形数组。但是，我不认为List<T>索引器的意图是O（1）。Big O表示法会跟踪性能，因为它与所操作的集合的大小有关。的实现者List<T>，除了希望O（1），很可能与其他的项目，如在紧密循环指令数和性能痴迷。在一般情况下，它必须尽可能接近阵列性能。访问数组的元素是一个非常简单的操作

• 将索引乘以大小乘以数组开头
• 尊重

在圆形数组中仍为O（1）的索引至少涉及一个分支操作。它必须根据所需索引检查数组索引是否需要环绕。这意味着具有已知边界的循环上的紧密数组将在其中包含分支逻辑。在原始数组上具有快速紧密循环的代码路径中，这将是重大的降级。

编辑

是的，不一定需要分支。但是，指令数仍将高于数组。我相信这仍然会影响作者的关注。

另外，另一个问题是，是否优先执行优先操作。如果不将“ prepend”（优先）作为优先级，那么为什么要在以前的情况下对性能造成任何影响（索引当然是优先级）？我的猜测是索引，枚举和添加到数组的末尾是被赋予最高优先级的方案。像prepend这样的操作可能被认为很少。