C#中的字符串数组和字符串列表有什么区别？

Question

我在MSDN上听说数组比集合更快。

你能告诉我为什么string[]比List<string>快吗？

- user605334

Answer 1

数组是比诸如列表之类的集合更低级别的抽象。CLR 直接知道数组，因此在迭代、访问等方面需要进行的工作略微减少。

然而，这几乎永远不应该决定你实际使用哪一个。在大多数实际应用中，性能差异将是可以忽略不计的。我很少发现使用数组而不是各种通用的集合类是合适的，事实上有些人认为数组有点有害。一个显著的缺点是，除了空数组之外，没有不可变的数组……而可以相对容易地通过 API 公开只读集合。

- Jon Skeet

---

鉴于MSDN声称“List<T>类是ArrayList类的泛型等效类。它使用一个大小根据需要动态增加的数组来实现IList<T>泛型接口。”这是否意味着一旦编译，List<>和数组之间的主要区别在于List<>中的某些方法需要检查是否需要调整大小？ - mlibby

@mcl：每次访问最终都要经过一个包装层，这在“原始”数组中是不存在的。这会带来一些小的性能损失。 - Jon Skeet

Answer 2

一个数组是不可调整大小的。这意味着在创建它时，将分配一块足够大的内存来容纳您指定的元素数量。

另一方面，一个列表是隐式可调整大小的。每次添加一个项时，框架可能需要分配更多的内存来容纳您刚刚添加的项。这是一个昂贵的操作，因此我们最终说“列表比数组慢”。

当然，这只是一个非常简化的解释，但希望足以说明问题。

- Jon

---

“每次添加一个项”都需要调整基础数组大小并不完全正确；特别是从不会有多个连续调整大小的情况。List类经过精心设计，使您永远不会陷入多个连续添加导致多个连续调整大小的情况。摊销的调整次数应与达到的最大大小的对数成比例；复制的总项目数应与最大大小成比例。 - Eric Lippert

@EricLippert：我知道，这就是为什么我在“可能需要”中加入了“可能”的原因。鉴于问题的难度和回答的简短性以及“足够接近”的目标，您肯定可以看出避免使用“摊销”和“O（N）”等术语是有意的。 - Jon

Answer 3

这篇文章是2004年的，意味着它涉及到 .net 1.1，那个时候还没有泛型。 当时数组与集合的性能差异确实是一个问题，因为集合类型会导致大量额外的装箱和拆箱操作。但自从 .net 2.0 引入泛型之后，性能差异几乎消失了。

- bniwredyc

Answer 4

数组是最简单的集合形式，因此比其他集合更快。列表（以及许多其他集合）实际上在内部使用数组来保存其项。

当然，数组也受其简单性的限制。最显著的是，您无法更改数组的大小。如果您想要一个动态集合，可以使用列表。

- Guffa

---

Array.Resize<T>()在更改数组大小的问题上有所不同。http://msdn.microsoft.com/en-us/library/bb348051.aspx - mlibby

@eric：嗯，我看过了。它所说的第一件事是：“将数组的元素数量更改为指定的新大小。”也许你的同事应该用不同的方式概括这个方法。或者除非正在实现库或编译器，否则你所提到的差异在大多数情况下都是语义上的。当列表大小增加时，List<T>是否不会做大致相同的事情？如果我们关心性能，并且有一个经常改变大小的结构，那么除了List<T>和Array之外，我们还有更好的选择吗？ - mlibby

@mcl：确实，列表“调整”底层数组（通过创建新数组并复制）。它使用双倍增长策略来实现，因此Add的平摊成本为O(1)，但最坏情况下的成本为O(n)，最坏情况下的内存浪费约为列表大小的100%。基本上，列表以浪费内存为代价换取了更快的速度。（我同意，该页面的措辞还有很大改进空间。非常令人困惑。） - Eric Lippert

Answer 5

List<string>是一个类，其中包含一个私有成员string[]。MSDN文档在多个地方都说明了这一点。List类基本上是数组的包装器，为数组提供了其他功能。

哪个更快取决于您对列表/数组的使用方式。对于访问和分配元素值，数组可能会稍微快一些，因为List是数组的抽象（正如Jon Skeet所说）。

如果您打算使用随时间增长的数据结构（获得越来越多的元素），则性能（平均速度）方面，List将开始发挥作用。这是因为每次调整数组大小以添加另一个元素时，它都是O(n)操作。当您向List添加元素（并且列表已满）时，列表将自动加倍其大小。我不会深入探讨细节，但基本上这意味着增加List的大小平均是一个O(log n)操作。当然，这也有缺点（如果您只超过其最后容量几个项目，则可以分配几乎两倍于实际需要的内存）。

编辑：上面的段落中有点混淆。正如Eric在下面所说，List的调整大小次数是O(log n)，但与调整数组大小相关的实际成本已摊销为O(1)。

- Jason Moore

---

你混淆了两个不同的事情。在双倍扩容列表中增加大小是每次添加的摊销O(1)操作。假设你从大小为1的数组开始，进行33次添加操作。你会复制第1个项目到第2个位置，第2个到第3个位置，第4个到第5个位置，第8个到第9个位置，第16个到第17个位置，第32个到第33个位置。这种调整大小的次数数量级为O(log n)；复制的总项目数为1+2+4+8+16+32=63，而你进行了33次添加操作，因此每次添加的平均成本略低于2个复制。这个恒定的边界为2无论列表增长多大都不会改变。 - Eric Lippert