为什么c#泛型List被实现为仅追加数组

本文关键字：追加 数组 实现 泛型 List 为什么 | 更新日期: 2023-09-27 18:29:38

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

然而，我想知道为什么没有选择将其实现为循环数组。对于索引随机接入和附加到列表末尾，这样的实现将具有相同的O（1）性能。但这将提供额外的好处，例如允许O（1）预端操作（即在列表的前面插入新元素），并平均将随机插入和删除所需的时间减半。

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

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

正如一些快速&脏性能测试，对于圆形阵列实现，索引可能慢2-5倍左右。

由于索引是一个明显的优先事项，我可以想象，与预处理操作的更好性能和随机插入/删除的稍好性能相比，这将是一个太大的代价。

这是一个带有一些补充答案信息的副本

这个问题实际上与为什么典型的数组列表实现不是'；t双端？，这是我在发布问题之前没有发现的。我想，答案并没有完全令人满意：

我还没有做任何基准测试，但在我看来，还会有其他瓶颈（例如非本地加载/存储）大大超过这一点。如果我没有听到更令人信服的东西，我可能会接受，谢谢2011年5月27日下午4:18

这个问题的答案提供了关于如何使循环列表的索引表现良好的额外信息，包括一个代码示例，以及一些使权衡决策更加清晰的量化数字。因此，它们提供的信息与另一个问题中提供的信息是互补的。因此，我同意这个问题的意图是完全相同的，因此我同意应该将其视为重复。然而，如果现在随附的新信息丢失，那将是一种耻辱。

此外，我仍然对实施选择的潜在额外原因感兴趣，这些原因可能尚未出现在任何一个问题的答案中。

为什么c#泛型List被实现为仅追加数组

实际上，循环数组可以用O（1）访问时间来实现。然而，我不相信List<T>索引器的意图是O（1）。Big O表示法跟踪性能，因为它与操作的集合的大小有关。List<T>的实现者除了想要O（1）之外，还可能痴迷于其他项目，如指令数和紧循环中的性能。它需要在相同的场景中尽可能接近阵列性能，才能发挥普遍的作用。访问数组的元素是一个非常简单的操作

  • 将索引乘以大小添加到数组开头
  • 抗辩

循环数组中的索引，当仍然为O（1）时，至少涉及一个分支操作。它必须检查数组索引是否需要基于所需的索引进行换行。这意味着在具有已知边界的循环上的紧密数组将在其内部具有分支逻辑。这将是在原始数组上具有快速紧密循环的代码路径中的显著下降。

编辑

啊，是的，不一定需要树枝。然而，指令计数仍将高于数组的指令计数。我相信这仍然会引起作者的关注。

此外，另一个问题是，准备是否是一项优先操作。如果准备工作不被视为优先事项，那么为什么要在这样的场景中承受任何性能打击（索引当然是优先事项）？我的猜测是，索引、枚举和添加到数组末尾是优先级最高的场景。像准备手术这样的手术可能被认为是罕见的。

您的问题让我很好奇List<>之间的运行时差异有多大以及圆形版本。因此，我快速构建了一个框架，它强制大小为2的幂（避免了模运算），即最佳情况下的实现。我忽略了增长，因为我只是想比较索引器属性的时间差异。还不错；circularList[x]大约是list[x]的两倍慢，而且两者都很快。我也没有真正调试过，因为我的时间有限。这可能还缺少List<>

一般来说，我认为这种行为只是分散了List<>的主要目的，实际上很少使用。因此，您在许多用途上强制降低性能，以使极少数用途受益。我认为他们做出了一个很好的决定，没有把它列入List<>。

using System;
public class CircularList<T> {
    private int start, end, count, mask;
    private T[] items;
    public CircularList() : this(8) { }
    public CircularList(int capacity) {
        int size = IsPowerOf2(capacity) ? capacity : PowerOf2Ceiling(capacity);
        this.items = new T[size];
        this.start = this.end = this.count = 0;
        this.mask = size - 1;
    }
    public void Add(T item) {
        if (this.count == 0) {
            this.items[0] = item;
            this.start = this.end = 0;
        } else {
            this.items[++this.end] = item;
        }
        this.count++;
    }
    public void Prepend(T item) {
        if (this.count == 0) {
            this.items[0] = item;
            this.start = this.end = 0;
        } else {
            this.start--;
            if (this.start < 0) this.start = this.items.Length - 1;
            this.items[this.start] = item;
        }
        this.count++;
    }
    public T this[int index] {
        get {
            if ((index < 0) || (index >= this.count)) throw new ArgumentOutOfRangeException();
            return this.items[(index + this.start) & this.mask]; // (index + start) % length
        }
        set {
            if ((index < 0) || (index >= this.count)) throw new ArgumentOutOfRangeException();
            this.items[(index + this.start) & this.mask] = value; // (index + start) % length
        }
    }
    private bool IsPowerOf2(int value) {
        return (value > 0) && ((value & (value - 1)) == 0);
    }
    private int PowerOf2Ceiling(int value) {
        if (value < 0) return 1;
        switch (value) {
            case 0:
            case 1: return 1;
        }
        value--;
        value |= value >> 1;
        value |= value >> 2;
        value |= value >> 4;
        value |= value >> 8;
        return unchecked((value | (value >> 16)) + 1);
    }
}
相关文章：