Список C # удалить с конца, действительно O (n)? - PullRequest
Новая
       7

Список C # удалить с конца, действительно O (n)?

25 голосов
/ 22 марта 2011

Я прочитал несколько статей о том, что 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), так как ему просто нужно уменьшить счетчик списка.

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

Ответы [ 5 ]

25 голосов
/ 22 марта 2011

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

5 голосов
/ 22 марта 2011

Удаление последнего элемента фактически будет 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);
2 голосов
/ 22 марта 2011

Это должно дать вам представление 

    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++;
    }
0 голосов
/ 11 апреля 2019

Если говорить асимптотически, O (N) - сложность времени самого метода в наихудшем случае, где N - количество. Это не может работать хуже, чем это.

Практически, это было бы в порядке O (N-I) (игнорируя постоянные издержки времени), где I - индекс. Это выводимо, так как все элементы за указанным индексом I необходимо сместить на позицию, предшествующую им соответственно в списке.

Чтобы понять это интуитивно, если N равно 100, а индекс равен 99 (последний элемент), то нет элементов, которые нужно «сдвигать», только последний элемент удаляется (или просто счет уменьшается без изменения размера). структуры данных).

Аналогично, когда N равно 100, а индекс равен 0 (первый элемент), необходимо выполнить 99 смен.

Запустите следующий код и убедитесь сами: 

int size = 1000000;
var list1 = new List<int>();
var list2 = new List<int>();

for (int i = 0; i < size; i++)
{
    list1.Add(i);
    list2.Add(i);
}

var sw = Stopwatch.StartNew();
for (int i = 0; i < size; i++)
{
    list1.RemoveAt(size-1);
    list1.Add(0);
}
sw.Stop();
Console.WriteLine("Time elapsed: {0}", sw.ElapsedMilliseconds);

sw = Stopwatch.StartNew();
for (int i = 0; i < size; i++)
{
    list2.RemoveAt(0);
    list2.Add(0);
}
sw.Stop();

Console.WriteLine("Time elapsed: {0}", sw.ElapsedMilliseconds);
0 голосов
/ 22 марта 2011

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

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

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

...