Почему общий список С# реализован как массив только для добавления?

Ваш вопрос заставил меня задуматься, какова будет разница во времени выполнения между List‹> и круговой версией. Итак, я собрал быстрый скелет для того, который использует размеры, равные степени двойки (что позволяет избежать операций по модулю), то есть реализацию в лучшем случае. Я не упомянул о росте, потому что просто хотел сравнить разницу во времени свойств индексатора. Это было не так уж плохо; roundList[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);
    }
}

Действительно, круговой массив может быть реализован со временем доступа O(1). Однако я не верю, что целью индексатора List<T> было O(1). Нотация Big O отслеживает производительность в зависимости от размера коллекции, с которой она работает. Разработчики List<T>, помимо стремления к O(1), вероятно, были одержимы другими вещами, такими как количество инструкций и производительность в узких циклах. Он должен быть как можно ближе к производительности массива в тех же сценариях, чтобы быть в целом полезным. Доступ к элементу массива — очень простая операция

• Добавить индекс, умноженный на размер, в начало массива
• почтение

Индексирование в циклическом массиве, хотя и по-прежнему O (1), включает по крайней мере одну операцию ветвления. Он должен проверить, должен ли индекс массива обернуться или нет на основе желаемого индекса. Это означает, что плотные массивы над циклами с известными границами будут иметь внутри себя логику ветвления. Это было бы значительным шагом вниз в путях кода с быстрыми узкими циклами над необработанным массивом.

ИЗМЕНИТЬ

Ах да, ветка не обязательно нужна. Однако количество инструкций все равно будет выше, чем у массива. Я полагаю, что это по-прежнему будет учитывать опасения авторов.

Кроме того, еще одна проблема будет заключаться в том, является ли операция prepend приоритетной операцией. Если prepend не считался приоритетом, то зачем принимать какие-либо потери производительности в сценарии, который был (индексирование, безусловно, было приоритетом)? Я предполагаю, что индексация, перечисление и добавление в конец массива были сценариями с наивысшим приоритетом. Такие операции, как prepend, вероятно, считались редкими.