Подтвердить что ты не робот

Почему LinkedList в целом медленнее, чем список?

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

Я думал, что заполнение наборов некоторыми случайными целыми числами должно быть достаточным. Я запускал этот код в режиме Debug, чтобы избежать оптимизации компилятора. Вот код, который я использовал:

var rand = new Random(Environment.TickCount);
var ll = new LinkedList<int>();
var list = new List<int>();
int count = 20000000;

BenchmarkTimer.Start("Linked List Insert");
for (int x = 0; x < count; ++x)
  ll.AddFirst(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();

BenchmarkTimer.Start("List Insert");
for (int x = 0; x < count; ++x)
  list.Add(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();

int y = 0;
BenchmarkTimer.Start("Linked List Iterate");
foreach (var i in ll)
  ++y; //some atomic operation;
BenchmarkTimer.StopAndOutput();

int z = 0;
BenchmarkTimer.Start("List Iterate");
foreach (var i in list)
  ++z; //some atomic operation;
BenchmarkTimer.StopAndOutput();

Здесь выводится:

Linked List Insert: 8959.808 ms
List Insert: 845.856 ms
Linked List Iterate: 203.632 ms
List Iterate: 125.312 ms

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

У кого-нибудь еще есть мысли о том, почему это так? Я пропустил что-то явно очевидное?

Примечание: здесь приведен пример простого класса BenchmarkTimer: http://procbits.com/2010/08/25/benchmarking-c-apps-algorithms/

4b9b3361

ОТВЕТЫ

Ответ 1

Обновить (в ответ на ваш комментарий): вы правы, обсуждать нотацию Big-O само по себе не совсем полезно. Я включил ссылку на ответ Джеймса в своем первоначальном ответе, потому что он уже предложил хорошее объяснение технических причин, по которым List<T> превосходит LinkedList<T> в целом.

В принципе, это вопрос распределения памяти и локальности. Когда все ваши элементы коллекции хранятся в массиве внутри (как в случае с List<T>), все это в одном непрерывном блоке памяти, к которому можно получить доступ очень быстро. Это применимо как к добавлению (поскольку это просто записывается в местоположение в уже выделенном массиве), так и в итерации (так как это обеспечивает доступ ко многим ячейкам памяти, которые очень близки друг к другу, а не к указателям на полностью отключенные ячейки памяти).

A LinkedList<T> - это специализированная коллекция, которая только затмевает List<T> в том случае, когда вы выполняете случайные вставки или удаления из середины списка, и даже тогда, возможно только.

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

Вот почему я упомянул, что List<T>.Add имеет амортизированная сложность O (1). Это означает, что добавление в список также является операцией, которая линейно масштабируется с размером ввода, тем же (эффективно), что и связанный список. Забудьте о том, что иногда список должен изменять размер (это то, где "амортизируется", я предлагаю вам посетить эту статью в Википедии, если вы еще этого не сделали). Они масштабируют тот же.

Теперь, что интересно и возможно интуитивно, это означает, что разница в производительности между List<T> и LinkedList<T> (опять же, когда дело доходит до добавления) становится более очевидной по мере увеличения количества элементов. Причина в том, что, когда список заканчивается в своем внутреннем массиве, он удваивает размер массива; и, следовательно, с большим количеством элементов, частота операций изменения размера уменьшается до точки, где массив в основном никогда не изменяет размер.

Итак, скажем, List<T> начинается с внутреннего массива, достаточно большого, чтобы содержать 4 элемента (я считаю, что это точно, хотя я точно не помню). Затем, когда вы добавляете до 20 миллионов элементов, он изменяет размер в общей сложности ~ (log 2 (20000000) - 1) или 23 раза. Сравните это с 20 миллионов раз, вы выполняете значительно менее эффективный AddLast на LinkedList<T>, который выделяет новый LinkedListNode<T> при каждом вызове, и эти 23 изменения размера кажутся довольно незначительными.

Надеюсь, это поможет! Если я не был бы ясен по каким-либо вопросам, дайте мне знать, и я сделаю все возможное, чтобы уточнить и/или исправить себя.

Джеймс находится на правильном пути.

Помните, что запись с большими выводами предназначена для того, чтобы дать вам представление о том, как масштабируется производительность алгоритма. Это не означает, что что-то, что выполняется в гарантированное время O (1), превосходит что-то другое, которое выполняется в амортизированном времени O (1) (как в случае с List<T>).

Предположим, у вас есть выбор из двух заданий, один из которых требует коммутации в 5 милях от дороги, которая иногда страдает от пробок. Обычно этот диск должен занять около 10 минут, но в плохой день это может быть больше похоже на 30 минут. Другая работа составляет 60 миль, но шоссе всегда ясно и никогда не имеет пробок. Этот диск всегда занимает у вас час.

Это в основном ситуация с List<T> и LinkedList<T> для добавления в конец списка.

Ответ 2

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

Контрастируйте это с LinkedList, который всегда должен выделять память для обертывания int. Таким образом, я думаю, что распределение памяти, вероятно, является тем, что вносит наибольший вклад в ваше время. Если вы уже выделили node, он должен быть быстрее в целом. Я бы попробовал эксперимент с перегрузкой AddFirst, который проверяет LinkedListNode (т.е. Создает LinkedListNode за пределами области действия таймера, просто добавив его).

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

Ответ 3

Как сказал Джеймс в своем ответе, распределение памяти, вероятно, является одной из причин, почему LinkedList работает медленнее.

Кроме того, я считаю, что основное различие связано с недействительным тестом. Вы добавляете элементы в начало связанного списка, но до конца обычного списка. Не добавили бы элементы в начало обычного списка, чтобы снова изменить результаты сравнения в пользу LinkedList?

Ответ 4

Так как в других ответах это не упоминалось, я добавляю еще один.

Несмотря на то, что в заявлении на печать указано "List Insert", вы на самом деле называете List<T>.Add, который является одним из видов "вставки", на самом деле List. Добавление - это особый случай использования только следующего элемента - базового массива хранения, и ничто не должно убираться с пути. Попытайтесь использовать List<T>.Insert вместо этого, чтобы сделать его наихудшим, а не лучшим.

Edit:

Подводя итог, для целей вставки список представляет собой структуру данных специального назначения, которая выполняется только при одном типе вставки: добавьте в конец. Связанный список - это структура данных общего назначения, которая одинаково быстро вставляется в любом месте в списке. И есть еще одна деталь: связанный список имеет более высокую память и накладные расходы процессора, поэтому его фиксированные затраты выше.

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

Ответ 5

Я настоятельно рекомендую статью Хруст числа: почему вы никогда не должны использовать связанный список снова. Там не так много, чего нет нигде, но я потратил немало времени, пытаясь понять, почему LinkedList <T> было намного медленнее, чем Список <T> в ситуациях, которые, как я думал, явно одобрили бы связанный список, прежде чем я его найду, и, посмотрев его, все стало немного лучше:

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

С другой стороны, у вектора [эквивалентного ArrayList или List <T> ] его элементы хранятся в соседней памяти, и так делает, позволяет максимизировать использование кеша и избегать промахов в кэше. Часто на практике это больше, чем компенсирует затраты, возникающие при перемещении данных.

Если вы хотите услышать это из более авторитетного источника, это от Советы для Улучшение временного кода в MSDN:

Иногда структура данных, которая выглядит великолепно, оказывается ужасной из-за плохой локальности ссылки. Вот два примера:

  • Динамически выделенные связанные списки ( LinkedListNode <T> - ссылочный тип, поэтому он динамически распределен) может снизить производительность программы, поскольку при поиске или когда вы проходите список до конца, каждая пропущенная ссылка может пропустить кеш или вызвать ошибку страницы. Реализация на основе простых массивов на самом деле может быть намного быстрее из-за лучшего кэширования и меньшего количества ошибок страницы - даже учитывая тот факт, что массив будет сложнее расти, он все равно может быть быстрее.

  • Таблицы хэшей, которые используют динамически распределенные связанные списки, могут ухудшить производительность. По существу, хэш-таблицы, которые используют динамически распределенные связанные списки для хранения их содержимого, могут значительно ухудшиться. Фактически, в конечном счете простой линейный поиск по массиву может быть быстрее (в зависимости от обстоятельств). Хэш-таблицы на основе массива (IIRC, Dictionary < TKey, TValue > основаны на массивах) - часто игнорируемая реализация, которая часто имеет превосходную производительность.

Это мой оригинальный (гораздо менее полезный) ответ, где я сделал некоторые тесты производительности.

Общий консенсус, похоже, заключается в том, что связанный список распределяет память на каждом добавлении (потому что node является классом), и это, похоже, так. Я попытался выделить код выделения из временного кода, который добавляет элементы в список, и сделал суть из результата: https://gist.github.com/zeldafreak/d11ae7781f5d43206f65

Я запускаю тестовый код 5 раз и вызываю GC.Collect() между ними. Вставка 20 миллионов узлов в связанный список занимает 193-211 мс (198 мс) по сравнению с 77-89 мс (81 мс), поэтому даже без распределения стандартный список немного превышает 2x быстрее. Итерирование по списку занимает 54-59 мс, по сравнению с 76-101ms для связанного списка, что более скромно на 50% быстрее.

Ответ 6

Я сделал тот же тест с List и LinkedList, вставляя в список фактические объекты (на самом деле, анонимные типы), а связанный список в этом случае медленнее, чем List.

Однако LinkedList ускоряет работу, если вы вставляете элементы, подобные этому, вместо использования AddFirst и AddLast:

LinkedList<T> list = new LinkedList<T>();
LinkedListNode<T> last = null;
foreach(var x in aLotOfStuff)
{
    if(last == null)
        last = list.AddFirst(x);
    else
        last = list.AddAfter(last, x);
}

AddAfter кажется быстрее, чем AddLast. Я бы предположил, что внутри .NET будет отслеживать "хвост" /последний объект по ref и идти прямо к нему при выполнении AddLast(), но, возможно, AddLast() заставляет его пересечь весь список до конца?