25

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

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

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

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

4

14 回答 14

24

将泛型List<T>视为数组的替代品。它们支持数组所做的大部分事情，包括根据需要分配初始存储大小。

于 2008-09-16T19:27:27.453 回答
12

这实际上取决于您所说的“添加”。

如果你的意思是：

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

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

但是，如果您使用的是 ArrayList、List、Collection 等，那么调用“Add”方法可能会创建一个新数组——但他们对此很聪明，他们不只是调整 1 个元素的大小，他们几何增长，所以如果你只是偶尔添加很多值，它必须分配一个新数组。即使那样，如果您知道要添加多少元素，您也可以使用“Capacity”属性来强制它提前增长（list.Capacity += numberOfAddedElements）

于 2008-09-16T19:34:36.640 回答
5

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

如果您在 0.1% 的使用量中需要极速，请确保在尝试优化之前确实是您的列表访问问题。

于 2008-09-16T19:29:20.460 回答
3

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

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

如果您想使用数组进行高效阅读，但您要经常“添加”元素，您有两个主要选择：

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

2) 将数组分配为比您需要的更大，然后将对象放入预先分配的单元格中。如果您最终需要比预分配更多的元素，您可以在数组填满时重新分配，每次将大小加倍。这给了 O(log n) 调整大小的性能，而不是 O(n)，就像使用 reallocate-once-per-add 数组一样。请注意，这几乎就是 StringBuilder 的工作方式，为您提供了一种更快的方式来不断地追加到字符串。

于 2008-09-16T19:30:50.533 回答
3

何时放弃使用数组

  1. 首先，当数组的语义与您的意图不匹配时- 需要动态增长的集合？不允许重复的集合？一个必须保持不变的集合？在所有情况下都避免使用数组。这是 99% 的情况。只是陈述明显的基本观点。

  2. 其次，当您没有为绝对的性能关键性进行编码时- 这大约是 95% 的情况。数组性能稍微好一点，尤其是在迭代中。它几乎总是无关紧要。

  3. 当您没有被带有params关键字的参数所强迫时- 我只是希望params接受任何IEnumerable<T>甚至更好的语言构造本身来表示序列（而不是框架类型）。

  4. 当您不编写遗留代码或处理互操作时

简而言之，您实际上需要一个数组是非常罕见的。我会补充一点，为什么人们可以避免它？

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

  2. Array 是在前泛型时代设计的，它通过大量运行时黑客来模仿泛型，它会在这里和那里展示它的古怪之处。我发现的一些问题：

    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对于 structs 和 classes ，运行时实现的方法可能会有所不同。这没什么大不了的，但是如果您忘记为期望泛型集合查找泛型的引用类型正确覆盖非泛型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>在末尾添加 a 或在任何位置插入任何容量。无法替代数组的确切行为，但人们大多将数组用作只读集合，您无法在其末尾添加任何内容。一个替代品是ReadOnlyCollection<T>。我进行了这种扩展方法：

public ReadOnlyCollection<T> ToReadOnlyCollection<T>(IEnumerable<T> source)
{
    return source.ToList().AsReadOnly();
}
于 2013-11-11T13:23:52.467 回答
2

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

因此，当您不知道数组的大小时，不应该使用数组，否则大小可能会发生变化。但是，如果您有一个固定长度的数组，它们是一种通过索引检索元素的简单方法。

于 2008-09-16T19:26:56.550 回答
2

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

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

于 2008-09-16T19:29:24.250 回答
2

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

ArrayList只是一个在需要时增长的数组。Add 是摊销 O(1)，只是要小心确保调整大小不会在错误的时间发生。插入是 O(n) 必须将右侧的所有项目移过来。删除是 O(n) 必须将右侧的所有项目移过。

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

最好的办法是选择适合您的问题的数据结构。这取决于很多事情，因此您可能想要浏览System.Collections.Generic命名空间。

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

-瑞克

于 2008-09-16T20:16:17.163 回答
1

你能做的最好的事情是尽可能多地分配你需要的内存。这将防止.NET不得不进行额外的调用来获取堆上的内存。如果做不到这一点，那么以五个或任何对您的应用程序有意义的数量进行分配是有意义的。

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

于 2008-09-16T19:27:47.453 回答
1

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

于 2008-09-16T19:28:02.333 回答
1

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

于 2008-09-16T19:29:33.797 回答
1

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

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

或者你可以只使用一个链表。然后，但是查找速度很慢...

于 2008-09-16T19:33:56.627 回答
1

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

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

于 2008-09-16T20:07:13.987 回答
1

如果您要进行大量添加，并且不会进行随机访问（例如myArray[i]）。您可以考虑使用链表 ( LinkedList<T>)，因为它永远不会像List<T>实现一样“增长”。但是请记住，您只能LinkedList<T>使用IEnumerable<T>接口真正访问实现中的项目。

于 2008-09-16T20:21:07.730 回答