deque, heapq, bisect и array: что брать вместо list

Если ты знаешь, как устроены deque и heapq, почему insort квадратичен на потоке вставок и когда нужен array, листай до «Теперь сам».

Как думаешь, что быстрее

Нужна очередь с приоритетом: события приходят в случайном порядке, обрабатывать надо самое раннее. Два решения. Первое - держать список отсортированным: bisect.insort(a, x) находит место двоичным поиском и вставляет. Второе - куча: heapq.heappush(h, x). Оба выглядят как O(log n) на вставку. На двухстах тысячах вставок во сколько раз одно быстрее другого?

Ответь себе до чтения. Если «примерно одинаково» - разбор покажет 4,3 секунды против 20 миллисекунд.

На что это похоже

deque - поезд из вагонов по 64 места. Посадить пассажира в голову или в хвост - прицепил вагон, если крайний полон, и готово. А найти сотысячного пассажира - идти по вагонам от ближнего конца.

Куча - турнирная таблица, где каждый «начальник» меньше двух своих «подчинённых». Новичок встаёт в конец и поднимается, пока не упрётся в начальника меньше себя: путь - высота дерева, log₂ n шагов. А отсортированный список - очередь в кассу по росту: найти своё место легко, но всем, кто ниже, придётся сделать шаг назад.

Механизм: четыре устройства

deque (Modules/_collectionsmodule.c): блоки по 64 ссылки, связанные в обе стороны, плюс индексы первого и последнего занятого места. append, appendleft, pop, popleft трогают только крайний блок. d[i] идёт от ближнего конца, прыгая по блокам: min(i, n − i) / 64 переходов. maxlen включает вытеснение: лишнее вываливается с другого конца, устройство из блоков остаётся тем же.

heapq не заводит своего типа: функции работают с обычным списком, где h[0] - минимум, а дети ячейки i - 2i + 1 и 2i + 2, как в разделе про кучи. heapify - O(n), nsmallest(k, ...) держит кучу из k элементов - O(n log k).

bisect - двоичный поиск по отсортированному списку: bisect_left и bisect_right за O(log n). insort = поиск + list.insert, а вставка сдвигает хвост.

array хранит значения одного числового типа подряд, как массив в C: array('d') - 8 байт на число против 8 байт ссылки и 24 байт объекта у списка.

Правило

Очередь и стек с двух концов - deque (O(1) на краях, O(n) в середине). Минимум из меняющегося набора - heapq (O(log n) вставка и извлечение). Поиск в редко меняющемся отсортированном списке - bisect (O(log n)), но поток вставок через insort - O(n) на каждую. Много чисел одного типа - array или NumPy.

Разбор: insort против кучи - сравнения и сдвиги

Посчитаем на модели оба вида работы: сравнения (их log n у обоих) и сдвиги элементов.

import random

def insort(a, x):
    # двоичный поиск места, затем сдвиг хвоста на одну позицию
    lo = 0
    hi = len(a)
    sravnenij = 0
    while lo < hi:
        mid = (lo + hi) // 2
        sravnenij = sravnenij + 1
        if x < a[mid]:
            hi = mid
        else:
            lo = mid + 1
    a.append(x)
    sdvigov = 0
    i = len(a) - 1
    while i > lo:
        a[i] = a[i - 1]
        i = i - 1
        sdvigov = sdvigov + 1
    a[lo] = x
    return [sravnenij, sdvigov]

def heappush(h, x):
    # просеивание вверх: родитель ячейки i - (i - 1) // 2
    h.append(x)
    i = len(h) - 1
    sravnenij = 0
    sdvigov = 0
    while i > 0:
        p = (i - 1) // 2
        sravnenij = sravnenij + 1
        if h[p] <= x:
            break
        h[i] = h[p]
        sdvigov = sdvigov + 1
        i = p
    h[i] = x
    return [sravnenij, sdvigov]

random.seed(3)
for n in [100, 400]:
    x = []
    for k in range(n):
        x.append(random.randint(0, 10 ** 6))
    for imya in ["insort", "heappush"]:
        a = []
        itog = [0, 0]
        for v in x:
            if imya == "insort":
                r = insort(a, v)
            else:
                r = heappush(a, v)
            itog = [itog[0] + r[0], itog[1] + r[1]]
        print(n, imya, "сравнений", itog[0], "сдвигов", itog[1])

100 insort сравнений 536 сдвигов 2373
100 heappush сравнений 198 сдвигов 102
400 insort сравнений 2912 сдвигов 41016
400 heappush сравнений 909 сдвигов 518

Сравнений у insort даже больше, но дело не в них: сдвигов при вчетверо большем n стало в 17 раз больше - квадрат, в среднем полсписка на вставку. У кучи на случайных данных новичок почти сразу останавливается: меньше двух сдвигов на вставку. Тот же эффект на настоящем Python:

import bisect
import heapq
import random
import time
from collections import deque


def zamer(f):
    # лучшее из трёх, в миллисекундах
    luchshee = None
    for popytka in range(3):
        t = time.perf_counter()
        f()
        dt = (time.perf_counter() - t) * 1000
        if luchshee is None or dt < luchshee:
            luchshee = dt
    return luchshee


n = 1_000_000
spisok = list(range(n))
deka = deque(spisok)
a = zamer(lambda: [spisok[n // 2] for _ in range(1000)])
b = zamer(lambda: [deka[n // 2] for _ in range(1000)])
print(f"середина x 1000: list {a:.2f} мс, deque {b:.1f} мс")

random.seed(1)
x = [random.random() for _ in range(200_000)]


def cherez_insort():
    a = []
    for v in x:
        bisect.insort(a, v)


def cherez_heap():
    h = []
    for v in x:
        heapq.heappush(h, v)


print(f"200000 вставок: insort {zamer(cherez_insort):.0f} мс,",
      f"heappush {zamer(cherez_heap):.0f} мс")

середина x 1000: list 0.08 мс, deque 71.9 мс
200000 вставок: insort 4255 мс, heappush 20 мс

Двести тысяч вставок: 4,3 секунды против 20 миллисекунд, в двести раз. Сдвиг в C - быстрая операция memmove, но квадрат она не отменяет.

Разбор: где deque проигрывает списку

Тот же замер, первая строка: обращение к середине дека на миллион элементов почти в тысячу раз дольше, чем у списка, - около 72 микросекунд против десятой доли. До середины полмиллиона элементов, то есть около 7800 блоков, и каждый переход - чтение указателя из другого места памяти. Граница правила «deque - это улучшенный list»: он лучше на краях и хуже везде, где нужен индекс. Очередь задач, скользящее окно, история последних k событий (deque(maxlen=k)) - да. Массив с произвольным доступом - нет.

Что ломается без этого

Очередь с приоритетом на insort. На тестовых сотнях событий не видно ничего, на продовых сотнях тысяч - секунды на каждую порцию.

heapq с максимумом. Куча в heapq - только минимальная (так в Python 3.12; в 3.14 добавили heappush_max и heappop_max). Для максимума кладут -x или пару (-приоритет, порядковый_номер, задача): номер нужен, чтобы при равных приоритетах кортежи не дошли до сравнения самих задач, которые сравнивать нельзя.

Индекс в deque в цикле. for i in range(len(d)): d[i] - квадрат. Обходить дек надо самим циклом for x in d.

Зачем это в работе

Планировщик таймеров (asyncio держит отложенные вызовы в куче heapq), скользящее среднее за последние k замеров (deque(maxlen=k)), поиск интервала по отсортированным границам тарифов (bisect), буфер сэмплов на миллионы чисел (array или NumPy) - четыре задачи, четыре контейнера. Для отсортированного набора с частыми вставками в стандартной библиотеке ничего нет; сторонний sortedcontainers держит список коротких отсортированных списков, и вставка сдвигает только один короткий кусок.

Теперь сам

1. Нужно хранить последние 1000 запросов и регулярно спрашивать, сколько из них пришло с одного адреса. Какой контейнер под окно, какой - под счётчики?
2. Почему heapq.heapify(a) стоит O(n), а не O(n log n)?
3. Список из 10⁶ отсортированных чисел меняется раз в сутки, а поиск по нему идёт тысячи раз в секунду. bisect или set, если нужен ответ «есть ли число» и «сколько чисел меньше x»?