如何以及何时放弃在 C# 中使用数组？

Question

我总是被告知向数组添加元素是这样的：

创建数组+1元的空副本，然后将来自原始数组的数据复制到其中，然后加载新元素的新数据

如果这是真的，那么由于内存和 CPU 利用率的原因，在需要大量元素活动的场景中使用数组是禁忌的，对吗？

如果是这种情况，当您要添加大量元素时，您是否应该尽可能避免使用数组？您应该使用 iStringMap 吗？如果是这样，如果您需要两个以上的维度并且需要添加大量元素，会发生什么情况。您只是承受性能损失还是应该使用其他东西？

Answer 1

看看通用的 List<T> 作为数组的替代品。它们支持数组所做的大部分相同的事情，包括根据需要分配初始存储大小。

Answer 2

这实际上取决于“添加”的含义。

如果你的意思是：

T[] array;
int i;
T value;
...
if (i >= 0 && i <= array.Length)
    array[i] = value;

那么，不，这不会创建新数组，实际上是更改 .NET 中任何类型的 IList 的最快方法。

但是，如果您使用的是 ArrayList、List、Collection 等。然后调用“添加”方法 可能 创建一个新数组 - 但他们对此很聪明，他们不只是调整 1 个元素的大小，它们会呈几何级数增长，所以如果你只是每隔一段时间添加大量值，它就必须分配一个新数组。即使这样，如果您知道要添加多少元素，您也可以使用“容量”属性来强制它预先增长（list.Capacity += numberOfAddedElements)

Answer 3

一般来说，我更喜欢避免使用数组。只需使用列表<T>。它在内部使用动态大小的数组，并且对于大多数使用来说足够快。如果您使用多维数组，请在必要时使用 List<List<List<T>>> 。就内存而言并没有那么糟糕，并且添加项目也更简单。

如果您的使用率只有 0.1%，需要极快的速度，请在尝试优化之前确保列表访问才是真正的问题。

Answer 4

如果您要大量添加/删除元素，只需使用列表即可。如果它是多维的，您始终可以使用 List<List<int>> 或其他东西。

另一方面，如果您主要做的是，列表的效率低于数组 穿越 列表，因为数组都位于 CPU 缓存中的一个位置，而列表中的对象分散在各处。

如果您想使用数组进行高效读取，但要频繁“添加”元素，那么您有两个主要选择：

1）将其生成为列表（或列表的列表），然后使用 ToArray() 将其转换为高效的数组结构。

2）分配比您需要的更大的数组，然后将对象放入预先分配的单元格中。如果您最终需要的元素比预先分配的元素还要多，则可以在数组填满时重新分配数组，每次将大小加倍。这提供了 O(log n) 的调整大小性能，而不是像每次添加数组重新分配一次的 O(n) 性能。请注意，这几乎就是 StringBuilder 的工作原理，为您提供了一种更快的方法来连续附加到字符串。

Answer 5

何时放弃使用数组

1. 首先也是最重要的， 当数组的语义 不 符合你的意图 - 需要动态增长的收藏吗？不允许重复的集合？一个必须保持不可变的集合？在所有这些情况下避免使用数组。99%的情况都是如此。只是陈述明显的基本点。

2. 第二， 当你是 不是 绝对性能关键的编码 - 大约 95% 的情况都是这样。 数组性能更好 边际地, 尤其是在迭代中. 。这几乎总是无关紧要的。

3. 当你在 不是 因与人争论而被迫 params 关键词 - 我只是希望 params 接受任何 IEnumerable<T> 或者甚至更好的是语言构造本身来表示 顺序 （而不是框架类型）。

4. 当你是 不是 编写遗留代码，或处理互操作

简而言之，您实际上很少需要数组。我会补充一下为什么人们可以避免它？

1. 在我看来，避免使用数组的最大原因是概念性的。数组更接近实现，更远离抽象。数组传达更多信息 它是如何完成的 比 做了什么 这违背了高级语言的精神。这并不奇怪，考虑到数组更接近金属，它们直接来自特殊类型（尽管数组内部是一个类）。不是为了教学，但数组确实可以转化为很少需要的语义。最有用和最常见的语义是具有任何条目的集合、具有不同项目的集合、键值映射等以及可添加、只读、不可变、尊重顺序的变体的任意组合。想一想，您可能想要一个可添加的集合，或者包含预定义项的只读集合，无需进一步修改，但是您的逻辑是否经常看起来像“我想要一个动态可添加的集合，但只有固定数量的集合，并且它们也应该是可修改的” “？我想说非常罕见。

2. 数组是在前泛型时代设计的，它通过大量运行时黑客来模仿泛型，并且它会时不时地表现出它的奇怪之处。我发现的一些收获：

   1. 协方差被破坏。

      string[] strings = ...
      object[] objects = strings;
      objects[0] = 1; //compiles, but gives a runtime exception.
      

   2. 数组可以为您提供对结构的引用！. 。这与其他地方不同。一个样品：

      struct Value { public int mutable; }
      
      var array = new[] { new Value() };  
      array[0].mutable = 1; //<-- compiles !
      //a List<Value>[0].mutable = 1; doesnt compile since editing a copy makes no sense
      print array[0].mutable // 1, expected or unexpected? confusing surely
      

   3. 运行时实现的方法如 ICollection<T>.Contains 结构和类可以不同. 。这没什么大不了的，但是如果你忘记覆盖 非通用的 Equals 对于需要泛型集合查找的引用类型正确 通用的 Equals, ，您将得到不正确的结果。

      public class Class : IEquatable<Class>
      {
          public bool Equals(Class other)
          {
              Console.WriteLine("generic");
              return true;
          }
          public override bool Equals(object obj)
          {
              Console.WriteLine("non generic");
              return true;
          } 
      }
      
      public struct Struct : IEquatable<Struct>
      {
          public bool Equals(Struct other)
          {
              Console.WriteLine("generic");
              return true;
          }
          public override bool Equals(object obj)
          {
              Console.WriteLine("non generic");
              return true;
          } 
      }
      
      class[].Contains(test); //prints "non generic"
      struct[].Contains(test); //prints "generic"
      

   4. 这 Length 财产和 [] 索引器打开 T[] 似乎是您可以通过反射访问的常规属性（这应该涉及一些魔法），但是当涉及表达式树时，您必须吐出与编译器完全相同的代码。有 ArrayLength 和 ArrayIndex 分别执行此操作的方法。一个这样的 在这里提问. 。另一个例子：

      Expression<Func<string>> e = () => new[] { "a" }[0];
      //e.Body.NodeType == ExpressionType.ArrayIndex
      
      Expression<Func<string>> e = () => new List<string>() { "a" }[0];
      //e.Body.NodeType == ExpressionType.Call;
      

如何放弃使用数组

最常用的替代品是 List<T> 它有一个更干净的 API。但它是一个动态增长的结构，这意味着您可以添加到 List<T> 在末尾或插入任意位置至任意容量。数组的确切行为是无可替代的，但人们大多将数组用作只读集合，您无法在其末尾添加任何内容。替代品是 ReadOnlyCollection<T>. 。我携带这个扩展方法：

public ReadOnlyCollection<T> ToReadOnlyCollection<T>(IEnumerable<T> source)
{
    return source.ToList().AsReadOnly();
}

Answer 6

当调整数组大小时，必须分配一个新数组并复制内容。如果只是修改数组的内容，那么它只是一个内存分配。

所以，当你不知道数组的大小，或者大小可能会改变时，你不应该使用数组。但是，如果您有固定长度的数组，则它们是按索引检索元素的简单方法。

Answer 7

ArrayList 和 List 在需要时将数组增加一倍以上（我认为这是通过将大小加倍，但我没有检查源代码）。当您构建动态大小的数组时，它们通常是最佳选择。

当您的基准测试表明数组调整大小严重减慢您的应用程序时（请记住 - 过早优化是万恶之源），您可以评估编写具有调整大小行为的自定义数组类。

Answer 8

一般来说，如果您必须拥有最佳的索引查找性能，最好先构建一个列表，然后将其转换为数组，这样一开始会付出一些小代价，但以后可以避免。如果问题是您将不断添加新数据并删除旧数据，那么为了方便起见，您可能需要使用 ArrayList 或 List，但请记住它们只是特殊情况的数组。当它们“增长”时，它们会分配一个全新的数组并将所有内容复制到其中，这是非常慢的。

数组列表 只是一个在需要时增长的数组。添加的摊销时间为 O(1)，只需小心确保调整大小不会在错误的时间发生。插入的时间复杂度为 O(n)，右侧的所有项目都必须移过去。移除的时间复杂度为 O(n)，右侧的所有项目都必须移过去。

同样重要的是要记住，List 不是链接列表。它只是一个类型化的 ArrayList。列表 文档 确实注意到它在大多数情况下表现更好，但没有说明原因。

最好的办法是选择适合您的问题的数据结构。这取决于很多事情，所以你可能想浏览 系统.集合.通用 命名空间。

在这种特殊情况下，我会说如果你能想出一个好的关键值 字典 将是你最好的选择。它的插入和删除接近 O(1)。然而，即使使用字典，您也必须小心不要让它调整其内部数组的大小（O(n) 操作）。最好通过在构造函数中指定比您期望使用的初始容量更大的容量来为它们提供大量空间。

-瑞克

Answer 9

标准数组应该定义一个长度，它在连续块中保留它所需的所有内存。向数组添加一个项目会将其放入已保留的内存块内。

Answer 10

数组非常适合少量写入和多次读取，特别是那些具有迭代性质的数据 - 对于其他任何内容，请使用许多其他数据结构之一。

Answer 11

你是对的，数组非常适合查找。然而，修改数组的大小是昂贵的。

在修改数组大小的情况下，您应该使用支持增量大小调整的容器。您可以使用 ArrayList，它允许您设置初始大小，并且您可以不断检查大小与容量，然后将容量增加一大块以限制调整大小的次数。

或者您可以只使用链接列表。然而查找速度很慢......

Answer 12

关于各种数组类型的效率，此论坛帖子可能对您有用，也可能没有用：C# 数组 - 多维数组与字典顺序数组

Answer 13

如果我认为我要在集合的生命周期内向集合添加很多项目，那么我会使用列表。如果我确定声明集合时集合的大小是多少，那么我将使用数组。

另一次，我通常在列表上使用数组是当我需要返回一个集合作为对象的属性时 - 我不希望调用者通过列表的 Add 方法添加该集合的项目，而是希望他们将项目添加到集合中通过我的对象的界面。在这种情况下，我将获取内部 List 并调用 ToArray 并返回一个数组。

Answer 14

如果您要进行大量添加， 和 您不会进行随机访问（例如 myArray[i]）。您可以考虑使用链表（LinkedList<T>），因为它永远不必像 List<T> 执行。但请记住，您只能真正访问 LinkedList<T> 实施使用 IEnumerable<T> 界面。

Answer 15

您能做的最好的事情就是如果可能的话，预先分配您需要的尽可能多的内存。这将防止 。网 不必进行额外的调用来获取堆上的内存。如果做不到这一点，那么以五个为一组或任何对您的应用程序有意义的数字进行分配是有意义的。

这是一条可以应用于任何事物的规则。