Почему deque реализован как связанный список вместо кругового массива?

CPython deque реализуется как дважды связанный список блоков размером в 64 элемента (массивы). Все блоки заполнены, за исключением тех, которые находятся на обоих концах связанного списка. IIUC, блоки освобождаются, когда a pop/popleft удаляет последний элемент в блоке; они выделяются, когда append/appendleft пытается добавить новый элемент и соответствующий блок заполнен.

Я понимаю перечисленные преимущества использования связанного списка блоков, а не связанного списка элементов:

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

Но почему вместо двусвязного списка в первую очередь не был выбран один круглый массив с динамическим размером?

AFAICT, круговая матрица сохранит все вышеперечисленные преимущества и сохранит (амортизированную) стоимость pop*/append* в O(1) (путем комбинирования, как и в list). Кроме того, это улучшит стоимость поиска по индексу от текущего O(n) до O(1). Круговой массив также будет проще реализовать, поскольку он может повторно использовать большую часть реализации list.

Я могу видеть аргумент в пользу связанного списка на таких языках, как С++, где удаление элемента из середины может быть сделано в O(1) с помощью указателя или итератора; однако python deque не имеет API для этого.

Ответ 1

Адаптирован из моего ответа в списке рассылки python-dev:

Первичная точка дека состоит в том, чтобы сделать popping и нажатие на обоих концах эффективным. Это то, что делает текущая реализация: наихудшее постоянное время на push или pop независимо от количества элементов в deque. Это превосходит "амортизацию O (1)" в малом и большом. Вот почему это было сделано таким образом.

Некоторые другие методы deque, следовательно, медленнее, чем для списков, но кому это нужно? Например, единственные индексы, которые я когда-либо использовал с deque, равны 0 и -1 (чтобы заглянуть на один конец или другой из deque), и реализация также делает доступ к этим конкретным индексам постоянным временем.

В самом деле, сообщение от Раймонда Хеттингера, на которое ссылается Джим Фасаракис Хиллиард в своем комментарии:

https://www.mail-archive.com/[email protected]/msg25024.html

подтверждает, что

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

Ответ 2

В дополнение к принятию ответа @TimPeters я хотел добавить пару дополнительных наблюдений, которые не вписываются в формат комментариев.

Давайте просто сосредоточимся на общем случае использования, когда deque используется как простая очередь FIFO.

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

Пока размер очереди растет, и круговой массив, и CPython нуждаются в памяти из кучи. CPython нуждается в простой malloc, в то время как для массива требуется (возможно, намного дороже) realloc (если дополнительное пространство не будет доступно на правом краю исходного блока памяти, ему необходимо освободить старую память и скопировать данных). Преимущество CPython.

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

Как указывал @TimPeters, стоимость каждой очереди FIFO put/get всегда O(1) для CPython, но только для амортизации O(1) для массива. Преимущество CPython.