Почему стек <T>и очередь <T>реализованы с помощью массива? - PullRequest
Новая
       55

Почему стек <T>и очередь <T>реализованы с помощью массива?

27 голосов
/ 08 июня 2010

Я читаю C # 4.0 в двух словах от братьев Албахари, и я наткнулся на это:

Стеки реализованы внутри с помощью массива , размер которого изменяется в соответствии с требованиями , как в случае очереди и списка. (стр. 288, пункт 4)

Я не могу не задаться вопросом, почему. LinkedList предоставляет O (1) вставки и удаления заголовка и хвоста (что должно хорошо работать для стека или очереди). Массив с изменяемым размером имеет O (1) амортизированную вставку (если я правильно помню), но O (n) худший случай (я не уверен насчет удаления). И он, вероятно, использует больше места, чем связанный список (для больших стеков / очередей).

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

Ответы [ 3 ]

23 голосов
/ 08 июня 2010

но O (n) худший случай

амортизированный худший случай по-прежнему равен O (1).Среднее и длинное время вставки усредняются - вот и весь смысл амортизированного анализа (и то же самое для удаления).

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

Кроме того, накладные расходы намного меньше, чем при использовании связанного списка.В общем, реализация на основе массива является просто (намного) более эффективной для почти всех вариантов использования, хотя время от времени доступ будет занимать немного больше времени (фактически, очередь может быть реализована несколько более эффективно, если принятьпреимущество страниц, которые сами управляются в связанном списке - см. реализацию C ++ 'std::deque).

22 голосов
/ 08 июня 2010

Вот примерная оценка ресурсов памяти, используемых для стека 100 System.Int32 с:

Для реализации массива потребуется следующее: 

type designator                          4 bytes
object lock                              4
pointer to the array                     4 (or 8)
array type designator                    4
array lock                               4
int array                              400
stack head index                         4
                                       ---
Total                                  424 bytes  (in 2 managed heap objects)

Для реализации связанного списка потребуется следующее: 

type designator                          4 bytes
object lock                              4
pointer to the last node                 4 (or 8)
node type designator         4 * 100 = 400
node lock                    4 * 100 = 400
int value                    4 * 100 = 400
pointer to next node  4 (or 8) * 100 = 400 (or 800)
                                     -----
Total                                1,612 bytes  (in 101 managed heap objects)

Основным недостатком реализации массива будет копирование массива, когда его нужно расширить. Игнорируя все другие факторы, это будет операция O (n), где n - количество элементов в стеке. Это выглядит довольно плохо, за исключением двух факторов: это почти никогда не происходит, поскольку расширение удваивается при каждом увеличении, а операция копирования массива высоко оптимизирована и удивительно быстра Таким образом, расширение на практике легко затопляется другими стековыми операциями.

Аналогично для очереди.

15 голосов
/ 22 февраля 2014

Это потому, что .NET был разработан для работы на современных процессорах. Которые намного, намного быстрее, чем шина памяти. Процессор работает на частоте около 2 гигагерц. Оперативная память вашей машины обычно составляет пару сотен мегагерц. Чтение байта из ОЗУ занимает более ста тактов.

Что делает кэши ЦП очень важными на современных процессорах, большое количество чипов расходуется на увеличение кэш-памяти до максимально возможного. На сегодняшний день типичным является 64 КБ для кэша L1, самая быстрая память и физически расположенная очень близко к ядру процессора, 256 КБ для кэша L2, медленнее и дальше от ядра, около 8 МБ для кэша L3, еще медленнее и дольше прочь, общая для всех ядер чипа.

Чтобы сделать кеши эффективными, очень важно иметь последовательный доступ к памяти. Чтение первого байта может быть очень дорогим, если необходим доступ к памяти L3 или RAM, следующие 63 байта очень дешевы. Размер «строки кэша», единица передачи данных для шины памяти.

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

Соответственно, все коллекции .NET, кроме LinkedList <>, реализованы как массивы внутри. Обратите внимание, что Stack <> уже естественным образом реализован в виде массива, поскольку вы можете только нажать и вытолкнуть элемент из конца массива. O (1) операция. Изменение размера массива амортизируется O (logN).

...