Бюджет хода: сколько шагов есть у сервера

Если ты привык делить бюджет времени между модулями до того, как выбрать алгоритм, листай до «Теперь сам».

Как думаешь, сколько поисков пути

Восемь игроков, у каждого 25 отрядов, и все 200 отрядов идут штурмовать одну крепость в центре карты. Каждый отряд должен знать, куда шагнуть в этот ход. Сколько поисков пути нужно сделать серверу?

Ответь себе до чтения. Первое, что приходит в голову, - 200: у каждого отряда свой старт, значит, свой поиск. Но цель у всех одна. Если пройти обходом в ширину не от отряда к крепости, а от крепости по всей карте, то у каждой клетки окажется расстояние до крепости, и каждый отряд просто шагает в соседнюю клетку с меньшим неотрицательным числом - горы и недостижимые клетки с −1 в поле не годятся. Один поиск вместо двухсот - и это не оптимизация кода, а другая модель задачи. Обход в ширину считает ходы; если цена хода зависит от местности, то же поле от цели строит Дейкстра. Идёт она по рёбрам в обратную сторону, и цена обратного шага - цена той клетки, в которую в прямом направлении входят, то есть клетки, ИЗ которой обратный шаг выходит.

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

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

Механизм: бюджет, оценка, распределение

Бюджет хода считается так же, как бюджет задачи в разделе 26: время на ответ, умноженное на скорость. 100 мс на Python - 0,1 · 1,5 · 10⁷ = 1,5 · 10⁶ простых операций. Это на ВЕСЬ ход, а модулей десяток, поэтому каждому достаётся доля, и считать её надо до кода.

Оценки «треть карты» и «25 сравнений» взяты из замеров ниже: отряд, ищущий путь сам, обходит в среднем около трети клеток, пока не встретит цель, а наивный поиск слова в сообщении сравнивает около 25 символов. Это типичный случай, а не худший: если цель за дальним краем карты, каждый поиск обойдёт её почти целиком, и двести поисков дадут около 200 · 16 384 · 4 ≈ 1,3 · 10⁷ проверок. Стоимость «проверки» больше одной операции - внутри и сравнение, и обращение к списку, - поэтому всё, что в таблице вышло дороже бюджета, не пройдёт заведомо, а всё, что вышло в процентах, пройдёт с запасом, даже если проверка стоит пять-десять операций.

Правило

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

Разбор: поле расстояний вместо двухсот поисков

Карта 24 × 24, на ней горы, сорок отрядов и крепость в центре. Клетка хранится одним числом r · N + c - так соседей легко посчитать, а словарь не нужен. Сравниваем два способа и считаем проверки соседей.

import random

random.seed(27)
N = 24                                  # карта N × N
gora = set()
for i in range(110):                    # горы непроходимы
    gora.add(random.randint(0, N * N - 1))
krepost = N * N // 2 + N // 2           # цель всех отрядов - центр
gora.discard(krepost)
otryady = []
while len(otryady) < 40:
    k = random.randint(0, N * N - 1)
    if k not in gora and k != krepost:
        otryady.append(k)
proverok = [0]

def sosedi(k):
    # клетка - одно число r * N + c; соседи по четырём сторонам
    out = []
    r = k // N
    c = k % N
    if r > 0:
        out.append(k - N)
    if r < N - 1:
        out.append(k + N)
    if c > 0:
        out.append(k - 1)
    if c < N - 1:
        out.append(k + 1)
    return out

def bfs(start, stop):
    # обход в ширину; stop = -1 - обойти всю карту
    dist = [-1] * (N * N)
    dist[start] = 0
    och = [start]
    golova = 0
    while golova < len(och):
        v = och[golova]
        golova = golova + 1
        if v == stop:
            break
        for s in sosedi(v):
            proverok[0] = proverok[0] + 1
            if dist[s] == -1 and s not in gora:
                dist[s] = dist[v] + 1
                och.append(s)
    return dist

# способ 1: каждый отряд ищет путь к крепости сам
proverok[0] = 0
dliny1 = []
for o in otryady:
    dliny1.append(bfs(o, krepost)[krepost])
p1 = proverok[0]

# способ 2: один обход ОТ крепости - поле расстояний для всех сразу
proverok[0] = 0
pole = bfs(krepost, -1)
dliny2 = []
for o in otryady:
    dliny2.append(pole[o])
p2 = proverok[0]

print("пути совпали:", dliny1 == dliny2, "| самый длинный:", max(dliny1))
print("каждый сам:  ", p1, "проверок соседей")
print("поле от цели:", p2, "проверок соседей")

пути совпали: True | самый длинный: 20
каждый сам:   21937 проверок соседей
поле от цели: 1838 проверок соседей

Длины путей совпали - на карте, где из любой клетки в соседнюю идут в обе стороны, путь от крепости до отряда той же длины, что от отряда до крепости. Сорок поисков сделали 21 937 проверок, в среднем 548 на отряд: каждый обошёл около трети карты, прежде чем наткнулся на крепость. Поле обошло карту один раз - 1838 проверок. На настоящей карте 128 × 128 с двумястами отрядами разница вырастает до десятков раз, и именно она отделяет «не проходит» от «4% бюджета».

Граница правила: поле работает, когда у многих отрядов одна цель. Если у каждого своя, поле на цель одно на отряд, и выигрыша нет - тогда спасают направленный поиск A* из раздела 11, который обходит клетки в сторону цели, и кеш путей между частыми точками. А если по карте можно ходить только в одну сторону (течение реки), поле от цели считается по обратным рёбрам.

Разбор: бюджет решает спор о толковании

Модератор просит: «не пропускать в чат запрещённые слова». Двадцать сообщений по двенадцать слов, 25 запрещённых слов. Два толкования - и две цены.

import random

random.seed(5)
slogi = ["ka", "ro", "mi", "lu", "ten", "vor", "pa", "zu", "dri", "os"]

def slovo(slogov):
    w = ""
    for i in range(slogov):
        w = w + slogi[random.randint(0, 9)]
    return w

zapret = set()
while len(zapret) < 25:             # запрещено 25 слов из двух слогов
    zapret.add(slovo(2))
soobshcheniya = []
for i in range(20):                     # 20 сообщений по 12 слов
    s = []
    for j in range(12):
        s.append(slovo(random.randint(2, 4)))
    soobshcheniya.append(" ".join(s))
sravnenij = [0]

def est_podstroka(tekst, obrazec):
    # наивный поиск: каждое начало, сравнение до первого различия
    for i in range(len(tekst) - len(obrazec) + 1):
        j = 0
        while j < len(obrazec):
            sravnenij[0] = sravnenij[0] + 1
            if tekst[i + j] != obrazec[j]:
                break
            j = j + 1
        if j == len(obrazec):
            return True
    return False

# толкование 1: запрещённое слово - любая ПОДСТРОКА сообщения
plohih1 = 0
for s in soobshcheniya:
    for z in sorted(zapret):
        if est_podstroka(s, z):
            plohih1 = plohih1 + 1
            break
p1 = sravnenij[0]

# толкование 2: запрещено только ЦЕЛОЕ слово - хватит множества
sravnenij[0] = 0
plohih2 = 0
for s in soobshcheniya:
    for w in s.split(" "):
        sravnenij[0] = sravnenij[0] + 1
        if w in zapret:
            plohih2 = plohih2 + 1
            break
p2 = sravnenij[0]
print("подстрокой:  ", plohih1, "сообщений из 20 |", p1, "сравнений")
print("целым словом:", plohih2, "сообщений из 20 |", p2, "проверок")

подстрокой:   20 сообщений из 20 | 12301 сравнений
целым словом: 11 сообщений из 20 | 160 проверок

Подстроками отклонены все двадцать сообщений: запрещённое двухслоговое слово прячется внутри длинных невинных слов - та же беда, что у фильтров, запрещающих названия городов за «плохой» кусок внутри. Целым словом - одиннадцать, и проверка стоит один поиск в множестве на слово. Цена различается в 77 раз. В замере на пару «сообщение, запрещённое слово» приходится около 25 сравнений (12 301 / (20 · 25)) - оценка снизу: поиск останавливался на первой находке, и часть пар не проверялась вовсе; при 2000 запрещённых словах и пяти сообщениях за ход это 2,5 · 10⁵ сравнений, а каждое с циклом вокруг - несколько операций: наивный поиск подстрок съедает почти весь бюджет хода. Бюджет не выбирает толкование, но ставит вопрос заказчику остро: если нужны подстроки, наивный поиск не годится - нужен автомат Ахо-Корасик из раздела 17, который читает сообщение один раз при любом числе слов.

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

Ход длиннее 100 мс. Каждый модуль по отдельности «быстрый», а вместе они не помещаются, и игроки видят рывки. Бюджет не делили - его съел тот, кто считал первым.

Сервер падает в пик. На тестовой карте 32 × 32 с десятком отрядов всё летает. На 128 × 128 с двумястами - в шестнадцать раз больше клеток и в двадцать раз больше поисков, и квадратичный по сути способ ломается.

Оптимизируют не то. Неделю ускоряют внутренний цикл поиска пути вдвое, хотя замена двухсот поисков одним полем дала бы в десятки раз.

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

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

Теперь сам

1. Карта 128 × 128, 8 крепостей, к каждой идёт по 25 отрядов. Сколько проверок соседей потребуют поля расстояний? Пройдёт ли бюджет 1,5 · 10⁶?
2. Ход сервера сократили до 50 мс. Сколько простых операций теперь на ход?
3. Почему поле расстояний на карте с односторонними переходами нельзя считать обычным обходом от цели?