Рекурсивные вычисления с использованием Mapreduce

Question

Я работаю над программой сокращения карт и думал о разработке вычислений в форме, где a1, b1 - это значения, связанные с ключом

  a1/b1, a1+a2/b1+b2, a1+a2+a3/b1+b2+b3 ...

Так что на каждой ступени редуктора мне потребовались бы предыдущие значения. Как можно уменьшить это как карту, так как на каждом этапе могут быть прочитаны только значения, связанные с определенным ключом.

Если вы чувствуете, что вопрос неясен, можете ли вы привести меня к этому общему вопросу?

Более общий вопрос: как можно развить ряд Фибоначчи с использованием рекурсии в карте?

EDIT

Можете ли вы помочь мне с моим измененным дизайном

 key1, V1,V2,V3
 Key2, V4,V5,V6

Выход Mapper

  Key1_X V1
  Key1_Y V2
  Key2_X V4
  Key2_Y V5

Выход редуктора

  Key1_X {V1,.....}
  Key1_Y {V2,.....}

аналогично, теперь на следующей стадии отображения. Могу ли я создать список следующим образом:

   key1 {V1,....} {V2,....}
   Key2 {V4,....} {V5,....}

Моя причина сделать это, чтобы выполнить:

   Key1 {V1/V2, V1+V6/V2+V7, V1+V6+..../V2+V7+.. , .........}

Возможно ли это сделать? Поскольку набор данных очень большой, поэтому я думаю, что будет лучше использовать карту Reduce.

Поможет ли изменение дизайна сделать его более эффективным?

Answer 1

Основная проблема с Фибоначчи (и, как вы указали в своей конкретной задаче) - это зависимость между всеми слагаемыми в ряду.Вы не можете рассчитать более поздние условия без предварительного вычисления более ранних условий.

MapReduce очень хорош, если вы можете разделить свою работу на независимые части.

Я не вижу простого способа сделать это.

Таким образом, любая конструкция, «заставляющая» MapReduce решить эту проблему, сломает преимущества масштабируемости.Следовательно, простой высоко оптимизированный цикл на вашем любимом языке программирования превзойдет любой алгоритм MapReduce.

Answer 2

Напишите свой картограф / редуктор, чтобы вычислить эти три вещи:

the sum of a_i
the sum of b_i
their ratio