Имеет ли List.Insert какое-либо ограничение производительности?

Ответ 1

Класс List является общим эквивалентом класса ArrayList. Он реализует общий интерфейс IList, используя массив, размер которого динамически увеличивается по мере необходимости.

(источник)

Значение, что внутренние данные хранятся в виде массива, и поэтому вполне вероятно, что для выполнения insert ему нужно будет переместить все элементы на место, поэтому его сложность - O (N), а add является (амортизированным) постоянным временем O (1), поэтому да.

Резюме. Да, он будет почти всегда медленнее, и он будет медленнее, чем больше ваш список.

Ответ 2

Если сомневаетесь, проведите эмпирический эксперимент:

List<object> SomeList = new List<object>();

Stopwatch sw = new Stopwatch();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Insert(0, String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);
sw.Reset();

SomeList = new List<object>();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Add(String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);

Insert занимает 2800 мс на моей машине; Add занимает 0,8 мс. Так что да, Insert гораздо менее производительный.

Ответ 3

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

В документации для List<T>.Insert() указано:

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

В документации для List<T>.Add() указано:

Если значение Count меньше емкости, этот метод является операцией O (1). Если емкость должна быть увеличена для размещения нового элемента, этот метод становится операцией O (n), где n является Count.

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

Стивен Клири предоставил хорошую реализацию Deque здесь: http://nitodeque.codeplex.com/

Ответ 4

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

В целом, Insert занимает (возможно, много) больше времени, потому что ему нужно переместить все элементы, находящиеся в списке, чтобы освободить место для нового элемента, так что это O (n ) по длине списка (если список заполнен до емкости, ему также потребуется изменить размер, но это все еще операция O (n)). С другой стороны, Add просто добавляет новый элемент без необходимости перемещать что-либо, чтобы он быстрее - операция O (1) (если только список не должен изменяться, как указано выше).

В этом конкретном примере, где список пуст для начала, разница в производительности не будет.

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

Ответ 5

Для пустого списка это ничем не отличается.

Но для чего-либо еще он должен быть медленнее *, потому что для вставки спереди необходимо, чтобы весь массив поддержки был сдвинут один вправо.

* За исключением того, что Add вызывает увеличение Capacity.

Ответ 6

Конечно, да.

Так как List<T> поддерживается массивом, любая операция для вставки в начале списка должна перемещать (или копировать) все остальные элементы массива. Операция, которая добавляется в конец списка, будет выполняться в постоянное время, независимо от количества элементов в списке.