Когда я должен использовать список по сравнению с LinkedList
https://stackoverflow.com/questions/169973
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Когда лучше использовать Список против a Связанный список?
Решение
Изменить
Пожалуйста, прочитайте комментарии к этому ответу. Люди утверждают, что я не делал правильные тесты. Я согласен, что это не должно быть принятым ответом. Как я был узнав, что я сделал несколько тестов и хотел поделиться ими.
Оригинальный ответ ...
Я нашел интересные результаты:
// Temporary class to show the example
class Temp
{
public decimal A, B, C, D;
public Temp(decimal a, decimal b, decimal c, decimal d)
{
A = a; B = b; C = c; D = d;
}
}
Связанный список (3,9 секунды)
LinkedList<Temp> list = new LinkedList<Temp>();
for (var i = 0; i < 12345678; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
Список (2,4 секунды)
List<Temp> list = new List<Temp>(); // 2.4 seconds
for (var i = 0; i < 12345678; i++)
{
var a = new Temp(i, i, i, i);
list.Add(a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
Даже если вы обращаетесь только к данным, это существенно медленнее !! Я говорю, никогда не используйте связанный список.
<Ч> <Ч> <Ч>Вот еще одно сравнение, выполняющее много вставок (мы планируем вставить элемент в середине списка)
Связанный список (51 секунда)
LinkedList<Temp> list = new LinkedList<Temp>();
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
var curNode = list.First;
for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
curNode = curNode.Next;
list.AddAfter(curNode, a); // Insert it after
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
Список (7,26 секунды)
List<Temp> list = new List<Temp>();
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.Insert(i / 2, a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
Связанный список, имеющий ссылку на место, куда вставить (0,04 секунды)
list.AddLast(new Temp(1,1,1,1));
var referenceNode = list.First;
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
list.AddBefore(referenceNode, a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
Таким образом, только если вы планируете вставить несколько элементов, и у вас также есть ссылка на то, куда вы планируете вставить элемент, тогда используйте связанный список. Просто потому, что вам нужно вставить много элементов, это не делает это быстрее, потому что поиск места, куда вы хотели бы вставить, требует времени.
Другие советы
В большинстве случаев List<T> является более полезным. LinkedList<T> будет стоить дешевле при добавлении / удалении элементов в середине списка, тогда как Find можно только дешево добавлять / удалять в конце списка.
ToArray эффективен только в том случае, если вы обращаетесь к последовательным данным (в прямом или обратном направлении) - произвольный доступ является относительно дорогим, поскольку он должен обходить цепочку каждый раз (следовательно, поэтому у него нет индексатора). Тем не менее, поскольку <=> по сути является просто массивом (с оберткой), произвольный доступ вполне допустим.
<=> также предлагает множество методов поддержки - <=>, <=> и т. д .; однако, они также доступны для <=> с .NET 3.5 / C # 3.0 с помощью методов расширения - так что это менее важный фактор.
Представление о связанном списке как о списке может немного ввести в заблуждение.Это больше похоже на цепочку.На самом деле, в .NET, LinkedList<T> даже не реализует IList<T>.В связанном списке нет реального понятия индекса, хотя может показаться, что оно существует.Конечно, ни один из методов, предоставляемых в классе, не принимает индексы.
Связанные списки могут быть односвязными или двусвязными.Это относится к тому, имеет ли каждый элемент в цепочке ссылку только на следующий (односвязный) или на оба предыдущих / следующих элемента (двусвязный). LinkedList<T> является вдвойне связанным.
Внутренне, List<T> поддерживается массивом.Это обеспечивает очень компактное представление в памяти.И наоборот, LinkedList<T> включает дополнительную память для хранения двунаправленных связей между последовательными элементами.Таким образом, объем памяти LinkedList<T> как правило, будет больше, чем для List<T> (с оговоркой, что List<T> может содержать неиспользуемые внутренние элементы массива для повышения производительности при операциях добавления.)
Они также имеют разные эксплуатационные характеристики:
Добавить
LinkedList<T>.AddLast(item)постоянное времяList<T>.Add(item)амортизированное постоянное время, линейный наихудший случай
Добавить
LinkedList<T>.AddFirst(item)постоянное времяList<T>.Insert(0, item)линейное время
Вставка
LinkedList<T>.AddBefore(node, item)постоянное времяLinkedList<T>.AddAfter(node, item)постоянное времяList<T>.Insert(index, item)линейное время
Удаление
LinkedList<T>.Remove(item)линейное времяLinkedList<T>.Remove(node)постоянное времяList<T>.Remove(item)линейное времяList<T>.RemoveAt(index)линейное время
Считать
LinkedList<T>.Countпостоянное времяList<T>.Countпостоянное время
Содержит
LinkedList<T>.Contains(item)линейное времяList<T>.Contains(item)линейное время
Очистить
LinkedList<T>.Clear()линейное времяList<T>.Clear()линейное время
Как вы можете видеть, они в основном эквивалентны.На практике API для LinkedList<T> является более громоздким в использовании, и детали его внутренних потребностей выливаются в ваш код.
Однако, если вам нужно выполнить много вставок / удалений из списка, это обеспечивает постоянное время. List<T> предлагает линейное время, так как дополнительные элементы в списке должны быть перетасованы после вставки / удаления.
Связанные списки обеспечивают очень быструю вставку или удаление элемента списка.Каждый элемент в связанном списке содержит указатель на следующий элемент в списке, поэтому для вставки элемента в позицию i:
- обновите указатель в элементе i-1, чтобы он указывал на новый элемент
- установите указатель в новом элементе так, чтобы он указывал на элемент i
Недостатком связанного списка является то, что произвольный доступ невозможен.Доступ к участнику требует обхода списка до тех пор, пока не будет найден нужный участник.
Разница между List и LinkedList заключается в их базовой реализации. Список - это массив на основе массива (ArrayList). LinkedList - это основанная на указателе узла коллекция (LinkedListNode). Что касается использования уровня API, оба они в значительной степени одинаковы, поскольку оба реализуют один и тот же набор интерфейсов, таких как ICollection, IEnumerable и т. Д.
Ключевое различие возникает, когда производительность имеет значение. Например, если вы реализуете список, который имеет тяжелый & Quot; INSERT & Quot; операция, LinkedList превосходит список. Поскольку LinkedList может сделать это за O (1) раз, но List может потребоваться расширить размер базового массива. Для получения дополнительной информации вы можете прочитать об алгоритмическом различии между LinkedList и структурами данных массива. http://en.wikipedia.org/wiki/Linked_list и Array
Надеюсь, это поможет,
Мой предыдущий ответ был недостаточно точным.Действительно, это было ужасно: D Но теперь я могу опубликовать гораздо более полезный и правильный ответ.
Я провел несколько дополнительных тестов.Вы можете найти его источник по следующей ссылке и перепроверить его в своей среде самостоятельно: https://github.com/ukushu/DataStructuresTestsAndOther.git
Краткие результаты:
Массив нужно использовать:
- Так часто, как только возможно.Это быстро и требует наименьшего объема оперативной памяти для хранения того же объема информации.
- Если вы знаете точное количество необходимых клеток
- Если данные сохранены в массиве < 85000 б
- При необходимости высокая скорость произвольного доступа
Список, который необходимо использовать:
- При необходимости добавить ячейки в конец списка (часто)
- При необходимости добавлять ячейки в начале / середине списка (НЕ ЧАСТО)
- Если данные сохранены в массиве < 85000 б
- При необходимости высокая скорость произвольного доступа
LinkedList необходимо использовать:
- При необходимости добавлять ячейки в начале / середине / конце списка (часто)
- При необходимости только последовательный доступ (вперед / назад)
- Если вам нужно сохранить БОЛЬШИЕ предметы, но их количество невелико.
- Лучше не использовать для большого количества элементов, так как это потребует дополнительной памяти для ссылок.
Более подробная информация:
Интересно узнать:
LinkedList<T>внутренне это не список в .NET.Это даже не реализуетIList<T>.И именно поэтому отсутствуют индексы и методы, связанные с индексами.LinkedList<T>это коллекция, основанная на указателе узла.В .NET это двусвязная реализация.Это означает, что предыдущие / следующие элементы имеют ссылку на текущий элемент.И данные фрагментированы - разные объекты списка могут быть расположены в разных местах оперативной памяти.Кроме того, будет использоваться больше памяти дляLinkedList<T>чем дляList<T>или Массив.List<T>в .Net - это альтернатива JavaArrayList<T>.Это означает, что это оболочка массива.Таким образом, он выделяется в памяти как один непрерывный блок данных.Если размер выделенных данных превысит 85000 байт, они будут перемещены в кучу больших объектов.В зависимости от размера это может привести к фрагментации кучи (легкая форма утечки памяти).Но в то же время, если размер < 85000 байт - это обеспечивает очень компактное представление в памяти с быстрым доступом.Одиночный непрерывный блок предпочтительнее для производительности произвольного доступа и потребления памяти, но для коллекций, размер которых необходимо регулярно менять, структуру, такую как массив, обычно необходимо скопировать в новое местоположение, тогда как связанный список нужен только для управления памятью для вновь вставленных / удаленных узлов.
Основным преимуществом связанных списков над массивами является то, что ссылки дают нам возможность эффективно переупорядочивать элементы. Седжвик, р. 91
Когда вам нужен встроенный индексированный доступ, сортировка (и после этого двоичного поиска) и " ToArray () " метод, вы должны использовать список.
Обычное обстоятельство использования LinkedList выглядит следующим образом:
Предположим, вы хотите удалить много определенных строк из списка строк большого размера, скажем, 100 000. Строки для удаления можно найти в HashSet dic, и список строк, как полагают, содержит от 30000 до 60000 таких строк для удаления.
Тогда какой тип списка лучше всего подходит для хранения 100 000 строк? Ответ LinkedList. Если они хранятся в ArrayList, то итерация по нему и удаление совпадающих строк может занять до миллиардов операций, в то время как с помощью итератора и метода remove () требуется всего около 100 000 операций.
LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
String string = iterator.next();
if (dic.contains(string))
iterator.remove();
}
Это адаптировано из принятого Тоно Нама исправления нескольких неверных измерений.
Тест:
static void Main()
{
LinkedListPerformance.AddFirst_List(); // 12028 ms
LinkedListPerformance.AddFirst_LinkedList(); // 33 ms
LinkedListPerformance.AddLast_List(); // 33 ms
LinkedListPerformance.AddLast_LinkedList(); // 32 ms
LinkedListPerformance.Enumerate_List(); // 1.08 ms
LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms
//I tried below as fun exercise - not very meaningful, see code
//sort of equivalent to insertion when having the reference to middle node
LinkedListPerformance.AddMiddle_List(); // 5724 ms
LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms
LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms
LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms
Environment.Exit(-1);
}
И код:
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace stackoverflow
{
static class LinkedListPerformance
{
class Temp
{
public decimal A, B, C, D;
public Temp(decimal a, decimal b, decimal c, decimal d)
{
A = a; B = b; C = c; D = d;
}
}
static readonly int start = 0;
static readonly int end = 123456;
static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);
static Temp temp(int i)
{
return new Temp(i, i, i, i);
}
static void StopAndPrint(this Stopwatch watch)
{
watch.Stop();
Console.WriteLine(watch.Elapsed.TotalMilliseconds);
}
public static void AddFirst_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Insert(0, temp(i));
watch.StopAndPrint();
}
public static void AddFirst_LinkedList()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (int i = start; i < end; i++)
list.AddFirst(temp(i));
watch.StopAndPrint();
}
public static void AddLast_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Add(temp(i));
watch.StopAndPrint();
}
public static void AddLast_LinkedList()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (int i = start; i < end; i++)
list.AddLast(temp(i));
watch.StopAndPrint();
}
public static void Enumerate_List()
{
var list = new List<Temp>(query);
var watch = Stopwatch.StartNew();
foreach (var item in list)
{
}
watch.StopAndPrint();
}
public static void Enumerate_LinkedList()
{
var list = new LinkedList<Temp>(query);
var watch = Stopwatch.StartNew();
foreach (var item in list)
{
}
watch.StopAndPrint();
}
//for the fun of it, I tried to time inserting to the middle of
//linked list - this is by no means a realistic scenario! or may be
//these make sense if you assume you have the reference to middle node
//insertion to the middle of list
public static void AddMiddle_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Insert(list.Count / 2, temp(i));
watch.StopAndPrint();
}
//insertion in linked list in such a fashion that
//it has the same effect as inserting into the middle of list
public static void AddMiddle_LinkedList1()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
LinkedListNode<Temp> evenNode = null, oddNode = null;
for (int i = start; i < end; i++)
{
if (list.Count == 0)
oddNode = evenNode = list.AddLast(temp(i));
else
if (list.Count % 2 == 1)
oddNode = list.AddBefore(evenNode, temp(i));
else
evenNode = list.AddAfter(oddNode, temp(i));
}
watch.StopAndPrint();
}
//another hacky way
public static void AddMiddle_LinkedList2()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start + 1; i < end; i += 2)
list.AddLast(temp(i));
for (int i = end - 2; i >= 0; i -= 2)
list.AddLast(temp(i));
watch.StopAndPrint();
}
//OP's original more sensible approach, but I tried to filter out
//the intermediate iteration cost in finding the middle node.
public static void AddMiddle_LinkedList3()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
{
if (list.Count == 0)
list.AddLast(temp(i));
else
{
watch.Stop();
var curNode = list.First;
for (var j = 0; j < list.Count / 2; j++)
curNode = curNode.Next;
watch.Start();
list.AddBefore(curNode, temp(i));
}
}
watch.StopAndPrint();
}
}
}
Вы можете видеть, что результаты соответствуют теоретическим показателям, которые были задокументированы другими здесь. Совершенно ясно - LinkedList<T> выигрывает в случае вставок. Я не проверял удаление из середины списка, но результат должен быть таким же. Конечно, List<T> есть и другие области, где он работает лучше, чем O (1) произвольный доступ.
По существу, a List<> в .NET - это оболочка над массив.A LinkedList<> это связанный список.Итак, вопрос сводится к тому, в чем разница между массивом и связанным списком, и когда следует использовать массив вместо связанного списка.Вероятно, два наиболее важных фактора при принятии вами решения о том, какой из них использовать, сводятся к:
- Связанные списки имеют гораздо лучшую производительность вставки / удаления, при условии, что вставки / удаления не относятся к последнему элементу в коллекции.Это связано с тем, что массив должен сдвигать все оставшиеся элементы, которые появляются после точки вставки / удаления.Однако, если вставка / удаление находится в конце списка, этот сдвиг не требуется (хотя размер массива, возможно, потребуется изменить, если его емкость будет превышена).
- Массивы обладают гораздо лучшими возможностями доступа.Массивы могут быть проиндексированы напрямую (за постоянное время).Связанные списки должны быть пройдены (линейное время).
Я согласен с большей частью изложенного выше. И я также согласен, что список выглядит как более очевидный выбор в большинстве случаев.
Но я просто хочу добавить, что во многих случаях LinkedList гораздо лучше, чем List, для большей эффективности.
<Ол>Надеюсь, кто-то найдет эти комментарии полезными.
Используйте LinkedList<>, когда
Token Stream. Для всего остального лучше использовать List<>.
Здесь так много средних ответов ...
В некоторых реализациях связанных списков используются базовые блоки предварительно выделенных узлов. Если они этого не делают, то постоянное время / линейное время не так важно, так как производительность памяти будет низкой, а производительность кеша - еще хуже.
Использовать связанные списки, когда
1) Вы хотите безопасность потоков. Вы можете создавать более безопасные многопоточные алгоритмы. Затраты на блокировку будут доминировать в списке одновременных стилей.
2) Если у вас большая очередь, например структуры, и вы хотите удалить или добавить ее где угодно, но конец всегда. > 100К списков существует, но не так часто.
Я задал похожий вопрос, связанный с производительность коллекции LinkedList и обнаружил Стивена Клири C # реализация Deque была решением. В отличие от коллекции Queue, Deque позволяет перемещать предметы вперед / назад вперед и назад. Он похож на связанный список, но с улучшенной производительностью.
