Почему List (T) .Clear O (N)? - PullRequest
Новая
       20

Почему List (T) .Clear O (N)?

8 голосов
/ 26 января 2011

Согласно документации MSDN по методу List<T>.Clear :

Этот метод является операцией O (n), где n - граф.

Почему O (n)? Я спрашиваю, потому что я предполагаю, что очистка List<T> может быть достигнута простым выделением нового массива T[] внутри. Ни один другой класс не может иметь ссылку на этот массив, поэтому я не вижу вреда в этом подходе.

Теперь, может быть, это глупый вопрос ... выделяет ли массив T[] сам O (n)? По какой-то причине я бы так не думал; но, может быть, это так (разве мое отсутствие степени бакалавра в области образования показывает сейчас?). Если это так, я полагаю, это объяснило бы это, поскольку, согласно той же документации, процитированной выше, емкость списка остается неизменной, что означает, что необходимо построить массив одинакового размера.

(Опять же, это не похоже на то, что это могло бы быть правильным объяснением, так как тогда в документации должно было быть сказано: «где n - Емкость » - не Count *).

Я просто подозреваю , что этот метод, вместо выделения нового массива, обнуляет все элементы текущего; и мне любопытно узнать, почему это так.

* Ханс Пассант указал в комментарии к LukeH ответ , что документы верны. Clear только обнуляет элементы, которые были установлены в List<T>; ему не нужно «обнулять» все элементы после них.

Ответы [ 4 ]

7 голосов
/ 26 января 2011

Насколько мне известно, текущая реализация просто вызывает Array.Clear на своем внутреннем массиве T[], а Array.Clear - это процесс O (n).(Как указывает Ганс в комментариях, документы MSDN верны, что n в данном случае - это Count списка, а не Capacity.)

Но даже если бы он просто выделил новый массив T[] внутри, это все равно было бы процессом O (n), потому что выделение массива размером n предполагает инициализацию всех элементов n их нулями /Состояние null / default.

Конечно, ничто не может остановить какую-то внутреннюю хитрость, когда массив может быть инициализирован с длиной 0 или 42 или чем-то другим, а затем автоматически расширен на лету, как требуется,амортизация общей стоимости O (n).

6 голосов
/ 26 января 2011

Поскольку реализация List<T>.Clear() вызывает Array.Clear() для массива заднего списка и согласно документации , этот метод устанавливает все элементы этого массива на null.

Я бы предположил, что причина, по которой существующий массив очищается вместо создаваемого нового, заключается в том, что команда .NET определила, что эффективнее очистить существующий массив вместо выделения нового. Выделение нового массива также требует времени и памяти, так что это компромисс, который пытается оптимизировать для общих сценариев использования.

0 голосов
/ 26 января 2011

List<T>.Clear() вызывает Array.Clear(), как показано здесь: 

public virtual void Clear()
{
    if (this._size > 0)
    {
        Array.Clear(this._items, 0, this._size);
        this._size = 0;
    }
    this._version++;
}

В свою очередь, Array.Clear() вызывает внешнюю функцию, которая обнуляет элементы массива, который равен O (n):

[MethodImpl(MethodImplOptions.InternalCall), SecuritySafeCritical, ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
public static extern void Clear(Array array, int index, int length);
0 голосов
/ 26 января 2011

List<T> списки содержат некоторые объекты. Выделение нового List<T> не избавляет от объектов в старом списке, следовательно, это не операция clear.

Операция clear выполняет линейный однократный проход по списку, очищая все элементы один за другим. Поскольку существует n элементов, это займет O(n) времени.

Выделение T[] зависит от того, указан ли размер. Если указан размер, то память должна быть выделена для каждого элемента или, по крайней мере, для каждого указателя для этого элемента. Таким образом, это займет O(n). Однако, если мы просто инициализируем указатель для T[], это займет O(1) времени.

P.S. Степень CS не означает автоматически, что вы знаете (или помните) этот материал ... грустно, но, правда. Отсутствие степени CS совсем не вредно.

...