Зачем гибрид

Мы видели два экстремума:

• Динамический массив: отличный cache, O(1) random access, но O(n) push_front/pop_front.
• Linked list: O(1) на любых концах, но pointer chasing убивает cache.

collections.deque берёт лучшее из обоих миров через гибрид: block-linked list. Это doubly linked список блоков, где каждый блок — небольшой массив указателей.

deque:  [block A] <-> [block B] <-> [block C]
           |             |             |
       [items 0..63] [items 64..127] [items 128..191]

В CPython 3.13 каждый блок (BLOCKLEN) — 64 указателя (Modules/_collectionsmodule.c). На 1М значений — это 15625 блоков. Связи между блоками: 15625 next-указателей. Внутри блока — обычный массив, отличный кэш.

Структура в исходниках

Псевдокод того, что в _collectionsmodule.c:

typedef struct BLOCK {
    PyObject *data[BLOCKLEN];   // BLOCKLEN = 64
    struct BLOCK *leftlink;     // prev block
    struct BLOCK *rightlink;    // next block
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;           // ptr на блок с левым концом
    block *rightblock;          // ptr на блок с правым концом
    Py_ssize_t leftindex;       // позиция в leftblock (0..63)
    Py_ssize_t rightindex;      // позиция в rightblock (0..63)
    Py_ssize_t state;
    Py_ssize_t maxlen;
    /* ... */
} dequeobject;

• leftblock / rightblock — указатели на крайние блоки.
• leftindex / rightindex — позиции в крайних блоках. Когда leftindex доходит до 0, нужен новый блок слева.
• data[64] — массив указателей внутри блока.

Как работает append/appendleft

from collections import deque

dq = deque()
dq.append(10)        # rightindex=0, data[0]=10
dq.append(20)        # rightindex=1, data[1]=20
dq.append(30)        # rightindex=2, data[2]=30
...
dq.append(item64)    # rightindex=63, блок полон
dq.append(item65)    # создаётся новый блок справа, rightblock=*new, rightindex=0

Сравните с appendleft:

dq.appendleft(0)     # leftindex=-1? нет: cначала leftindex был 0, потом если он 0 — создаётся блок слева

В реальной реализации индексы могут идти в обе стороны от центра. Когда индекс выходит за границу блока — создаётся новый блок и линкуется. Это всё O(1).

popleft симметрично: декрементит leftindex или удаляет пустой блок, если опустошился.

Сложности операций

Бенчмарк: deque vs list для FIFO

Очередь FIFO: производитель кладёт справа, потребитель забирает слева. Классическая структура.

import time
from collections import deque

N = 100_000

# list версия — O(n) на каждый popleft
lst = list(range(N))
t0 = time.perf_counter()
while lst:
    lst.pop(0)
t1 = time.perf_counter()
print(f"list FIFO:  {(t1-t0)*1000:>8.2f} ms")

# deque версия — O(1) на каждый popleft
dq = deque(range(N))
t0 = time.perf_counter()
while dq:
    dq.popleft()
t1 = time.perf_counter()
print(f"deque FIFO: {(t1-t0)*1000:>8.2f} ms")

Типовой результат:

list FIFO:    1620.50 ms
deque FIFO:      4.20 ms       # в 400 раз быстрее

В 400 раз. Это разница между O(n^2) и O(n). На миллион элементов разрыв был бы x40000 — list просто не отработал бы за разумное время.

maxlen — ring buffer бесплатно

У deque есть параметр maxlen. Когда заполнен — старые элементы выкидываются автоматически:

from collections import deque

last_10 = deque(maxlen=10)
for i in range(100):
    last_10.append(i)
print(list(last_10))   # [90, 91, 92, ..., 99]

Это готовый ring buffer: для трекинга «последних N событий», скользящих окон, hot/cold метрик. Не нужно писать circular buffer руками — есть в стандартной библиотеке.

Под капотом: при достижении maxlen append сначала делает popleft (выкидывает старое), потом добавляет новое. Обе операции O(1).

Почему BLOCKLEN = 64

Авторы CPython выбрали 64 как баланс:

• Слишком маленький блок (например, 4) — почти как linked list, много pointer chasing между блоками. Cache miss часто.
• Слишком большой блок (например, 4096) — большой блок = много памяти при маленьком deque. Создание/удаление блока — медленное.
• 64 — типичная кэш-линия процессора. 64 указателя * 8 байт = 512 байт = 8 cache lines. Получается «вес блока» хорошо помещается в L1 и L2 при типичном использовании.

Кроме того, 64 = 2^6, индексирование через сдвиг и битмаску — быстро.

Cache miss profile

На 1М элементов:

• list[int] итерация: pointer chasing к каждому PyLongObject (1М потенциальных miss). Но prefetcher отлично работает на буфере указателей.
• deque[int] итерация: pointer chasing внутри блока (плотный массив) + переходы между блоками (15625 раз). Соседние блоки часто близки в куче (Python pool аллокатора), поэтому миссов меньше.
• self-linked list: 1М миссов гарантировано — каждый узел отдельный объект.

В реальных бенчмарках deque iter ~37 ms vs self-linked ~140 ms, на python overhead-е разница частично размывается, но в 4 раза быстрее всё равно.

Применения в DE

1. Скользящие окна (rolling window): deque(maxlen=N) — последние N значений всегда под рукой.
2. BFS обход графа: deque как очередь вершин для обработки.
3. Streaming buffer: producer-consumer паттерн в asyncio.
4. History trim: undo-redo с лимитом глубины (как Vim u-r).
5. Rate limiting через временное окно: deque меток с popleft когда устаревают.

Попробуй сам

Реализуйте rolling average через deque(maxlen=N):

from collections import deque

class RollingAverage:
    def __init__(self, window_size):
        self.window = deque(maxlen=window_size)
        self.sum = 0.0

    def add(self, value):
        if len(self.window) == self.window.maxlen:
            # окно заполнено, при добавлении самый старый будет выкинут
            self.sum -= self.window[0]
        self.window.append(value)
        self.sum += value

    def average(self):
        return self.sum / len(self.window) if self.window else 0.0


ra = RollingAverage(5)
for x in [10, 20, 30, 40, 50, 60, 70]:
    ra.add(x)
    print(f"add {x}: window={list(ra.window)}, avg={ra.average():.2f}")

Все операции — O(1). Окно автоматически держит только последние 5 значений. Сумма поддерживается инкрементально — никаких полных пересчётов.