С# List remove from end, действительно O (n)?

Я прочитал несколько статей, в которых указано, что List.RemoveAt() находится в O (n) времени.

Если я сделаю что-то вроде:

var myList = new List<int>();

/* Add many ints to the list here. */

// Remove item at end of list:
myList.RemoveAt(myList.Count - 1); // Does this line run in O(n) time?

Удаление из конца списка должно быть O (1), так как ему просто нужно уменьшить количество списков.

Нужно ли мне писать собственный класс для этого поведения или удалить элемент в конце списка С#, который уже выполняется в O (1)?

Ответы

Ответ 1

Обычно List<T>::RemoveAt является O (N) из-за необходимости сдвигать элементы после индекса вверх по слоту в массиве. Но для конкретного случая удаления из конца списка сдвиг не требуется, и, следовательно, O (1)

Ответ 2

Удаление последнего элемента будет фактически O(1), поскольку только в этом случае List не сдвигает следующие элементы в массиве. Вот код из Reflector:

this._size--;
if (index < this._size) // this statement is false if index equals last index in List
{
    Array.Copy(this._items, index + 1, this._items, index, this._size - index);
}
this._items[this._size] = default(T);

Ответ 3

Это должно дать вам идею

    public void RemoveAt(int index) {
        if ((uint)index >= (uint)_size) { 
            ThrowHelper.ThrowArgumentOutOfRangeException(); 
        }
        _size--; 
        if (index < _size) {
            Array.Copy(_items, index + 1, _items, index, _size - index);
        }
        _items[_size] = default(T); 
        _version++;
    }

Ответ 4

Мне кажется, что если это действительно актуально для вашего приложения, вы могли бы измерить его за меньшее время, чем потребовалось, чтобы задать вопрос. И теперь у вас есть как минимум два противоречивых ответа, поэтому вам все равно придется протестировать его.

То, что я пытаюсь сделать, заключается в том, что, если документы MSDN не говорят, что removeAt является O (1) для элементов в конце списка, вы не можете рассчитывать на то, что он работает таким образом, и это может измениться в любом данном обновлении .NET. В этом отношении поведение может отличаться для разных типов, для всего, что вы знаете.

Если List - это "естественная" структура данных, которую вы используете, используйте ее. Если удаление элементов из списка заканчивается тем, что вы являетесь "горячей точкой" вашего профилирования, возможно, пришло время реализовать свой собственный класс.