Почему Stack <T> и Queue <T> реализованы с массивом?

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

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

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

Есть ли еще что-то, кроме этого? В чем недостаток реализации двойной ссылки?

Ответ 1

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

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

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

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

Ответ 2

Здесь грубая гостевая память ресурсов памяти, используемая для стека 100 System.Int32 s:

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

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 - количество элементов в стеке. Это кажется довольно плохим, за исключением двух факторов: это почти никогда не происходит, поскольку расширение увеличивается на каждый шаг, и операция копирования массивов сильно оптимизирована и очень быстро растет. Таким образом, расширение на практике легко забивается другими операциями стека.

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

Ответ 3

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

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

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

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

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