1

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

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

到目前为止的一些答案的总结

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

正如一些快速而肮脏的性能测试所示，对于循环数组实现，索引可能会慢 2-5 倍左右。

由于索引是一个明显的优先事项，我可以想象这将是一个太大的惩罚，而不是在前置操作上获得更好的性能和在随机插入/删除上稍微更好的性能。

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

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

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

这个问题的答案提供了有关如何使循环列表的索引表现得相当好的附加信息，包括一个代码示例，以及一些使权衡决策变得更加清晰的量化数字。因此，它们提供的信息与另一个问题中存在的信息相辅相成。所以我同意这个问题的意图非常相似，因此我同意它应该被视为重复。但是，如果现在随附此信息的新信息丢失，那将是一种耻辱。

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

4

2 回答 2

5

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

  • 将索引乘以大小添加到数组开始
  • 顺从

循环数组中的索引虽然仍然是 O(1)，但至少涉及一个分支操作。它必须根据所需的索引检查数组索引是否需要环绕。这意味着具有已知边界的循环上的紧密数组将在其中具有分支逻辑。这将是在原始数组上具有快速紧密循环的代码路径中的一个显着下降。

编辑

啊，是的，不一定需要分支。但是，指令数仍将高于数组的指令数。我相信这仍然会成为作者担忧的因素。

此外，另一个问题是 prepend 是否是优先操作。如果 prepend 不被视为优先事项，那么为什么要在这种情况下（索引肯定是优先事项）受到任何性能影响？我的猜测是索引、枚举和添加到数组的末尾是被赋予最高优先级的场景。像 prepend 这样的操作可能被认为是罕见的。

于 2013-08-30T22:36:14.767 回答
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);
    }
}
于 2013-08-30T23:58:29.153 回答