Структуры под операции: что спрашивают чаще всего

Если ты выбираешь структуру по списку операций с частотами, а не по названию объекта, листай до «Теперь сам».

Как думаешь, где хранить события

В игре всё происходит «через сколько-то ходов»: стройка закончится на 17-м, караван придёт на 12-м, отряд вылечится на 9-м. Каждый ход сервер добавляет новые события и выполняет все, чей ход настал, по порядку. Событий в очереди - сотни. Список, отсортированный по ходу, или что-то другое?

Ответь себе до чтения. Отсортированный список хорош для чтения: первое событие всегда в начале. Но каждая вставка в середину сдвигает хвост, а снятие первого элемента pop(0) сдвигает весь список. Операции здесь ровно две - «добавить» и «взять самое раннее», - и обе часты. Это описание очереди с приоритетом из раздела 9, а она живёт в куче: обе операции за log n.

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

Кухня ресторана. Повар не раскладывает заказы по столу в идеальном порядке - ему важно одно: какое блюдо готовить следующим. Заказы приходят всё время, а уходят по одному, самый срочный. Держать идеальный порядок всех заказов - лишняя работа; достаточно всегда знать самый срочный, и куча делает ровно это.

Механизм: таблица операций игры

Для каждого модуля выписываются операции, частота за ход и размер - и по ним структура.

Строка таблицы читается так: если операции не те - структура не та. Словарь не умеет «самый ранний», куча не умеет «найти по ключу», список умеет всё, но дорого. Двух одинаковых строк в таблице нет, и это нормально: одна игра - много разных структур.

Правило

Выбирай структуру по операциям и их частоте, а не по названию объекта. Выпиши для модуля, что с данными делают каждый ход и сколько раз, найди в курсе структуру, где частые операции дешёвые, - и проверь, на каких данных её гарантия ломается.

Разбор: очередь событий - список против кучи

Четыреста событий, очередь держится около ста: как только в ней больше ста, самое раннее выполняется. Это модель нагрузки, а не ход сервера: настоящий сервер берёт из очереди события, чей ход настал, - но операции те же, «добавить» и «взять самое раннее», и их цену модель меряет честно. Ключ события - одно число ход · 10000 + номер: «сначала по ходу, при равенстве по номеру» тогда сравнивается одним <. В обычном Python для этого берут пару (кортеж) - здесь одно число, и это тот же порядок, пока номеров меньше десяти тысяч.

import random

random.seed(3)
# событие - одно число: ход * 10000 + номер. Так порядок «сначала по
# ходу, при равенстве по номеру» сравнивается одним «<», без пары чисел
sobytiya = []
for nomer in range(400):
    hod = random.randint(1, 40) + nomer // 30     # события копятся
    sobytiya.append(hod * 10000 + nomer)
rabota = [0, 0]                    # [сдвигов в списке, обменов в куче]

def v_spisok(spisok, x):
    # вставка в отсортированный список: всё, что больше x, сдвигается
    spisok.append(x)
    i = len(spisok) - 1
    while i > 0 and spisok[i - 1] > x:
        spisok[i] = spisok[i - 1]
        rabota[0] = rabota[0] + 1
        i = i - 1
    spisok[i] = x

def v_kuchu(k, x):
    # двоичная куча (раздел 9): новый элемент всплывает
    k.append(x)
    i = len(k) - 1
    while i > 0 and k[(i - 1) // 2] > k[i]:
        k[i], k[(i - 1) // 2] = k[(i - 1) // 2], k[i]
        rabota[1] = rabota[1] + 1
        i = (i - 1) // 2

def iz_kuchi(k):
    # минимум уходит, последний элемент тонет на его место
    verh = k[0]
    k[0] = k[len(k) - 1]
    k.pop()
    i = 0
    while True:
        m = i
        for d in [2 * i + 1, 2 * i + 2]:
            if d < len(k) and k[d] < k[m]:
                m = d
        if m == i:
            return verh
        k[i], k[m] = k[m], k[i]
        rabota[1] = rabota[1] + 1
        i = m

spisok = []
kucha = []
po_spisku = []
po_kuche = []
for x in sobytiya:
    v_spisok(spisok, x)
    v_kuchu(kucha, x)
    if len(spisok) > 100:          # очередь держится около 100 событий
        po_spisku.append(spisok[0])
        spisok.pop(0)
        # pop(0) сдвигает весь хвост списка
        rabota[0] = rabota[0] + len(spisok)
        po_kuche.append(iz_kuchi(kucha))
print("порядок совпал:", po_spisku == po_kuche, "| событий:",
      len(po_kuche))
print("отсортированный список:", rabota[0], "сдвигов")
print("куча:                  ", rabota[1], "обменов")

порядок совпал: True | событий: 300
отсортированный список: 52860 сдвигов
куча:                   2530 обменов

Порядок выполнения одинаковый - обе структуры верны. Работа расходится в двадцать раз: список платит за каждую вставку длиной хвоста, который больше нового события, и за каждое pop(0) - длиной всего списка. Куча платит высотой дерева, log₂ 100 ≈ 7 обменов на операцию в худшем случае, а в среднем меньше. Граница правила: если событий всегда единицы, список проще и не медленнее. Куча выигрывает с ростом очереди, и на сотнях событий действий у неё уже в двадцать раз меньше.

Разбор: кто рядом - пары против корзин

Сто отрядов на карте 128 × 128; отряд замечает врага не дальше 4 клеток по большей из осей. Сравниваем перебор всех пар с корзинами: карта делится на квадраты 8 × 8, и соседей ищут только в своём квадрате и восьми соседних - дальше 4 клеток от отряда там никого быть не может, раз сторона квадрата не меньше 4.

import random

N = 128                     # карта 128 × 128
R = 4                       # отряд видит врага не дальше 4 клеток
K = 8                       # корзина - квадрат 8 × 8 клеток, K >= R

def ryadom(a, b):
    # расстояние по большей из осей: квадрат обзора
    return max(abs(a[0] - b[0]), abs(a[1] - b[1])) <= R

def vse_pary(otryady):
    proverok = 0
    par = 0
    for i in range(len(otryady)):
        for j in range(i + 1, len(otryady)):
            proverok = proverok + 1
            if ryadom(otryady[i], otryady[j]):
                par = par + 1
    return [par, proverok]

def korziny(otryady):
    # отряд кладётся в корзину своего квадрата; соседей ищем только в
    # своей и восьми соседних корзинах - дальше R не бывает, раз K >= R
    kor = {}
    for i in range(len(otryady)):
        k = str(otryady[i][0] // K) + ":" + str(otryady[i][1] // K)
        if k not in kor:
            kor[k] = []
        kor[k].append(i)
    proverok = 0
    par = 0
    for i in range(len(otryady)):
        r = otryady[i][0] // K
        c = otryady[i][1] // K
        for dr in [-1, 0, 1]:
            for dc in [-1, 0, 1]:
                k = str(r + dr) + ":" + str(c + dc)
                if k in kor:
                    for j in kor[k]:
                        if j > i:
                            proverok = proverok + 1
                            if ryadom(otryady[i], otryady[j]):
                                par = par + 1
    return [par, proverok]

random.seed(8)
po_karte = []
for i in range(100):
    po_karte.append([random.randint(0, N - 1), random.randint(0, N - 1)])
v_kuche = []
for i in range(100):         # все отряды сбились у одной крепости
    v_kuche.append([random.randint(60, 67), random.randint(60, 67)])
for imya, o in [["по всей карте", po_karte],
                ["у одной крепости", v_kuche]]:
    a = vse_pary(o)
    b = korziny(o)
    print(imya + ":", "пар рядом", a[0], b[0], "| проверок",
          a[1], "против", b[1])

по всей карте: пар рядом 23 23 | проверок 4950 против 173
у одной крепости: пар рядом 3403 3403 | проверок 4950 против 4950

Когда отряды раскиданы по карте, корзины проверили 173 пары вместо 4950 и нашли те же 23. Когда все сто отрядов сбились у одной крепости - в четырёх соседних корзинах, по две на каждой оси, - корзины проверили те же 4950 пар. Рядом из них 3403: отряды в квадрате 8 × 8, и далеко друг от друга не бывают. Это граница правила, и она про данные, а не про код. Гарантия корзин держится на том, что в каждой корзине мало отрядов; в осаде крепости это не так, и там пар много по существу - сам ответ квадратичен, как «все пары» в разделе 26.

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

Структура по названию объекта. «События - это список событий» - и на тысяче событий сервер тратит ход на сдвиги, хотя нужен только самый ранний.

Структура без проверки распределения. Корзины прошли тесты на равномерной карте, а в первой же большой битве все отряды в одной корзине - и ход длится секунду.

Копия мира на каждую отмену. Отмену хода сделали копией всей карты - 16 384 клетки на каждый ход, хотя за ход меняется сотня; журнал изменений стоит сотню.

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

Любая система с повторяющимися запросами - очередь задач, кеш, планировщик, индекс в базе - выбирает структуру ровно так: какие запросы, как часто, на каком объёме. Таблица операций на модуль за полчаса заменяет недели споров «а давайте возьмём дерево» и сразу показывает, на каком распределении данных выбранная структура перестанет спасать.

Теперь сам

1. Модуль «торговый журнал»: сделки только добавляются, раз в ход нужна сумма сделок за любой отрезок ходов [a, b]. Какая структура?
2. Модуль «кто владеет клеткой»: 16 384 клетки, каждый ход меняются десятки, запрос «чья клетка» - сотни раз. Что выбрать?
3. В очереди событий всегда не больше трёх событий. Стоит ли писать кучу?