Зачем еще один урок про deque

В уроке 05 модуля 6 мы уже разбирали deque на уровне «гибрид массива и связного списка». Здесь мы посмотрим подробнее на анатомию реализации: как именно достигается O(1), что происходит при пересечении границы блока, какой trade-off на random access.

Это нужно junior DE, потому что:

• deque используется во множестве production-структур (asyncio.Queue, BFS, rate limiter, rolling window).
• Понимая её устройство, можно правильно выбирать deque vs другие структуры.
• Это пример хорошего инженерного дизайна: «не идеален во всём, идеален в главном».

Полная структура

В CPython 3.13 (Modules/_collectionsmodule.c):

#define BLOCKLEN 64

typedef struct BLOCK {
    PyObject *data[BLOCKLEN];
    struct BLOCK *leftlink;
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;     /* in range(BLOCKLEN) */
    Py_ssize_t rightindex;    /* in range(BLOCKLEN) */
    size_t state;             /* incremented on every rotation */
    Py_ssize_t maxlen;
    Py_ssize_t numfreeblocks;
    block *freeblocks[10];
} dequeobject;

Главные поля:

• leftblock / rightblock — указатели на блоки, где находятся крайние элементы.
• leftindex / rightindex — позиции в этих блоках. Самый левый элемент лежит в leftblock.data[leftindex], самый правый — в rightblock.data[rightindex].
• state — счётчик модификаций, используется для invalidate итераторов.
• maxlen — для ring buffer семантики.
• freeblocks — small pool освобождённых блоков для переиспользования (амортизация malloc).

Пример с цифрами

Создадим deque и положим в неё 5 элементов:

from collections import deque

dq = deque()
for i in range(5):
    dq.append(i * 10)

В памяти:

Теперь сделаем appendleft(99):

dq.appendleft(99)

leftindex был 0, и слева больше места нет. CPython создаёт новый блок Z слева:

Все эти манипуляции — несколько присваиваний указателей и одна аллокация блока (если нет свободного в freeblocks). O(1).

Что значит O(1) на push/pop с обоих концов

Каждая из четырёх операций (append, appendleft, pop, popleft) делает максимум:

1. Проверить, есть ли место в текущем rightblock / leftblock. Если есть — записать значение и обновить индекс.
2. Если места нет — взять блок из freeblocks или сделать malloc(sizeof(block)). Залинковать в цепочку.
3. Обновить leftblock или rightblock.

Все шаги O(1). Случай malloc — редкий: на каждые 64 операции один раз. Amortized совершенно ровный.

Random access: тут плохо

dq[i] требует найти i-й элемент. Алгоритм:

1. Определить, в каком блоке от leftblock лежит i-й элемент: block_idx = (leftindex + i) // BLOCKLEN.
2. Пройти block_idx шагов по цепочке rightlink.
3. Прочитать block.data[(leftindex + i) % BLOCKLEN].

Это O(i) — линейный обход блоков. На 1М элементов и индексе 500_000 — это 500_000/64 ≈ 7800 переходов по rightlink. На list — одна арифметика адресов.

import time
from collections import deque

N = 10_000_000
dq = deque(range(N))
lst = list(range(N))

# random access середины
i = N // 2

t0 = time.perf_counter()
for _ in range(1000):
    _ = lst[i]
t1 = time.perf_counter()
print(f"list[i]:  {(t1-t0)*1e6:.2f} us total")

t0 = time.perf_counter()
for _ in range(1000):
    _ = dq[i]
t1 = time.perf_counter()
print(f"deque[i]: {(t1-t0)*1e6:.2f} us total")

Получите что-то вроде list 50 us, deque 50000 us — в 1000 раз медленнее. Поэтому не используйте deque для random access.

Когда random access делает плохо

Внимание к одной типичной ошибке junior:

# плохо: deque не для случайного доступа
data = deque(range(1_000_000))
for i in random_indices:
    process(data[i])    # каждое — O(n)!

Если ваша задача — random access, переключайтесь на list или ndarray. Если задача — обход всех элементов плюс редкие push/pop с краёв — deque OK. Если задача — частые push/pop в середине — нужны другие структуры (linked list, B-tree, skip list).

rotate как уникальная фишка deque

У deque есть метод rotate(n) — циклический сдвиг:

from collections import deque
dq = deque([1, 2, 3, 4, 5])
dq.rotate(2)            # сдвиг на 2 вправо: правые два элемента переходят влево
print(list(dq))          # [4, 5, 1, 2, 3]

dq.rotate(-1)           # сдвиг на 1 влево
print(list(dq))          # [5, 1, 2, 3, 4]

Это O(|n|) — линейный по модулю сдвига, не по размеру deque. Внутри — просто перенастройка leftindex/rightindex и перемещение указателей блоков. Аналогичная операция на list была бы O(N) полным копированием.

Применение: round-robin scheduling, циклические буферы команд.

Сравнение со списком на разных задачах

Внутри блока: рост и реальные сценарии

Когда вы запускаете worker pool с очередью на 10М задач:

• В каждый момент в очереди обычно лежит ~1000 задач (producer и consumer балансируют).
• Это ~16 блоков. Один указатель на leftblock, один на rightblock, ~14 промежуточных.
• Total memory ~16 * 64 * 8 байт = 8 КБ для очереди + сами задачи.

Динамически deque растёт и уменьшается, освобождая блоки. numfreeblocks хранит до 10 свободных блоков для быстрого переиспользования. Это амортизирует malloc.

Если очередь очень большая (миллион), создаётся ~16k блоков. Это всё ещё дешёво по сравнению с миллионом отдельных Node-объектов в чистом linked list.

Попробуй сам

Замерьте rotate и сравните с эквивалентом на list:

import time
from collections import deque

N = 1_000_000
dq = deque(range(N))
lst = list(range(N))

# rotate в deque
t0 = time.perf_counter()
dq.rotate(N // 2)       # сдвиг на половину размера
t1 = time.perf_counter()
print(f"deque.rotate(N/2):  {(t1-t0)*1000:.2f} ms")

# rotate в list через slicing
t0 = time.perf_counter()
shift = N // 2
lst = lst[-shift:] + lst[:-shift]
t1 = time.perf_counter()
print(f"list rotate by slicing: {(t1-t0)*1000:.2f} ms")

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

deque.rotate(N/2):       3.20 ms        (O(N/2) переключений)
list rotate by slicing:  7.50 ms        (O(N) копирование указателей)

Деке быстрее, потому что внутри она только переставляет блоки и индексы. Для очень больших rotate (близко к N/2) разница составляет 2-3x.