MapReduce в The Farmer Was Replaced

MapReduce в The Farmer Was Replaced

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

В предыдущем посте мы обсуждали код, который использует подход MapReduce для выращивания подсолнечника. Мы рассмотрели функцию drone_map_reduce(objects, f_map, f_red) построчно и поняли, что:
👉🏻 objects — массив описаний задач
👉🏻 f_map — фабричная функция, создающая задачу по ее описанию.
👉🏻 f_red — функция редуктора, при необходимости объединяет результаты в один большой результат

Сегодня мы обсудим, как эта структура применяется для решения трех задач по подсолнечнику: обработать все поле, посадить подсолнухи, собрать урожай подсолнухов с бонусом х5.

Обработка поля

def till_field():
 columns = []

 for x in range(get_world_size()):
  columns.append(x)

 def till_column(columns):
  def g():
   for q in columns:
    for p in range(get_world_size()):
     nav(q, p)
     till_soil()
  return g

 drone_map_reduce(columns, till_column, no_reduce)

Разберем код. Сначала готовим список столбцов для обработки. Затем определяем фабричную функцию till_column, которая принимает список столбцов и возвращает функцию обработки этих столбцов. Внутри используются nav для навигации и till_soil для обработки почвы (обратного переключения почвы здесь нет). Ключевой трюк — вложенная функция g внутри till_column: она замыкает переменную columns и поэтому вызывается без параметров. Именно эту функцию мы передаем в spawn_drone, чтобы задать действия и время жизни дрона.

Посадить подсолнухи

def plant_sunflowers():
  drone_jobs = []

  for q in range(get_world_size()):
    drone_jobs.append(q)

  def drone_job(columns):
    def g():
      heights = dict()
      for q in columns:
        for p in range(get_world_size()):
          nav(q, p)
          plant(Entities.Sunflower)
          heights[(q, p)] = measure()
      return heights
    return g

  def reduce_hights(h1, h2):
    for k in h2:
      h1[k] = h2[k]
    return h1

  return drone_map_reduce(drone_jobs, drone_job, reduce_hights)

Первая часть вполне знакома — формирование списка столбцов для обработки. Функция drone_job снова представляет собой фабрику функций. Опять же, эти функции очень похожи на предыдущие функции till_column. Но теперь у нас есть интересная деталь. У каждого подсолнуха есть свое количество лепестков, и по этим лепесткам мы должны определить, какой подсолнух собирать первым. Итак, после посадки подсолнуха мы вызываем функцию measure() и помещаем ее результат в словарь:

heights[(q, p)] = measure()

Ключами этого словаря являются кортежи координат, а значениями — номера лепестков.

И последняя, но не менее важная деталь: функция reduce_hights. Она принимает два словаря, обновляет первый значениями из второго и возвращает первый словарь. Логика выглядит чуть менее «чистой», но это сделано осознанно. В первой версии я каждый раз создавал новый словарь и сливал в него оба аргумента. На практике это приводило к заметным паузам, потому что цена «чистоты» оказалась квадратичной сложностью. Поэтому вариант с обновлением на месте быстрее.

Я не уверен, что один пост может содержать столько кода, поэтому давайте использовать ссылки на github. Начиная с этой строки, я преобразую словарь из формата (x,y) -> h в h -> [(x1, y1), (x2, y2), ...]. Для каждой высоты подсолнуха теперь у нас есть список ячеек с подсолнухами данной высоты в этих ячейках.

Наконец используем наш подход map-reduce, чтобы собрать все подсолнухи в правильном порядке. gather_all — фабричная функция для этой задачи.