MapReduce в The Farmer Was Replaced

MapReduce в The Farmer Was Replaced

Обсуждение кода. Часть I.

27 лет назад появился Google. Одной из ключевых идей был PageRank - оценка «доверия» к веб-странице (статья). Чтобы считать это быстро, нужна большая вычислительная мощность. Можно было строить специализированный суперкомпьютер, но Google пошел другим путем: массивы обычного железа, объединенные в сеть. Программы для такой платформы нужно очень аккуратно оркестрировать, и в те времена распределенные вычисления были почти магией.

В 2004 году началась новая эра распределенных вычислений - эпоха MapReduce (см. статью Дина и Гемавата). Идея проста: делим данные на части, запускаем одну и ту же map-функцию параллельно на множестве машин, затем объединяем (reduce) частичные результаты в итог.

Этот пост посвящен адаптации этого подхода к задаче по сбору подсолнухов в игре The Farmer Was Replaced.

Внутриигровая задача состоит из трех этапов: подготовить почву, посадить подсолнухи, собрать урожай. Мы хотим использовать бонус 5×, поэтому собираем подсолнухи в порядке значения measure(): от большего к меньшему. Речь о поздней стадии игры, когда есть поле 32×32 и 32 дрона, то есть можно назначить по одному дрону на каждый столбец или строку.

Мне нужна была крошечная «структура», позволяющая назначать задачи дронам и запускать их параллельно. Поскольку мы проводим измерения, нам также необходимо собирать данные с разных дронов и объединять их. Ядром этого фреймворка является функция drone_map_reduce из скрипта.

Функция drone_map_reduce принимает три параметра:

⌖ objects — элементы для обработки
⌖ f_map - функция, обрабатывающая пакет объектов
⌖ f_red - функция-редьюсер, объединяющая результаты пакетов в общий результат

GitHub reference

API дронов, на который мы полагаемся:

⌖ spawn_drone(f) — запускает дрон с функцией f и возвращает его идентификатор
⌖ дрон «исчезает», когда завершается f
⌖ wait_for(drone_id) - ждет завершения работы дрона и возвращает результат

Сначала создаем слоты для дронов и распределяем между ними задания:

def drone_map_reduce(objects, f_map, f_red):
    drone_jobs = []

    for _ in range(max_drones()):
        drone_jobs.append([])

    ind = 0
    for q in objects:
        drone_jobs[ind % len(drone_jobs)].append(q)
        ind += 1

Теперь каждый элемент в drone_jobs — это пакет работ для одного дрона (или для основного потока).

Затем запускаем дронов и также обрабатываем некоторые пакеты в основном потоке:

    results = []
    drones = []

    while drone_jobs:
        while drone_jobs and num_drones() < max_drones():
            current = drone_jobs.pop()
            drones.append(spawn_drone(f_map(current)))
        if drone_jobs:
            current = drone_jobs.pop()
            results.append(f_map(current)())

После этого собираем все результаты с дронов:

    for current_drone in drones:
        results.append(wait_for(current_drone))

И, наконец, объединяем все в один результат, используя f_red:

    reduced = None

    for r in results:
        if reduced is None:
            reduced = r
        else:
            reduced = f_red(reduced, r)

    return reduced

Несколько важных деталей:

⌖ Чтобы создать корректную задачу для дрона, f_map ожидает список элементов того же типа, что и элементы в objects.
⌖ Мы создаем до max_drones() пакетов, поэтому во внутреннем цикле просто спавним дронов, пока num_drones() не достигнет max_drones().
⌖ Код работает и когда задач меньше, чем дронов (например, при set_world_size(3)): часть пакетов будет пустой.
⌖ Если функция дрона ничего не возвращает (None) и результаты вам не нужны, можно передать фиктивный редьюсер, например no_reduce, который игнорирует аргументы. Или просто None в качестве редьюсера, если он никогда не будет вызываться.

В следующий раз: как построить настоящую игровую логику на базе этого инструмента.