Map/Reduce: какие-либо теоретические основы, кроме как?

Некоторое время я думал, что вам просто нужна карта для моноида, а затем сокращение будет выполнять сокращение в соответствии с умножением моноида.

Во-первых, это не совсем так, как работают моноиды, а во-вторых, это не совсем то, как map/reduce работает на практике.

А именно, возьмем вездесущий пример «счета». Если считать нечего, любой движок map/reduce вернет пустой набор данных, а не нейтральный элемент. облом.

Кроме того, в моноиде операция определена для двух элементов. Мы можем легко распространить его на конечные последовательности или, благодаря ассоциативности, на конечные упорядоченные множества. Но нет никакого способа распространить его на произвольные «коллекции», если только у нас нет -алгебры. .

Итак, какова теория? Я пытался понять это, но не смог; и я попытался пойти Google, но ничего не нашел.


mapreduce math
person Vlad Patryshev    schedule 17.12.2011    source источник
comment
Возможно, это представляет интерес MapReduce как монада.   -  person Peteris    schedule 18.12.2011
comment
Я запутался в вашем комментарии по сигма-алгебре. Поскольку каждый механизм сокращения карт, который я когда-либо видел, работает с исчисляемыми коллекциями (!), если вы выбираете порядок в коллекции, ассоциативность достаточна для определения результата. Сигма-алгебры используются в теории меры, когда у вас есть (как минимум) несчетные множества, с которыми нужно иметь дело.   -  person Rupert Swarbrick    schedule 21.08.2012
comment
@RupertSwarbrick Причина появления -алгебры заключается в том, что если у вас нет канонического порядка и бинарной операции, у вас есть четко определенная последовательность. Но если у вас нет такого порядка (и поскольку мы говорим о явных алгоритмах, мы не используем аксиому выбора), вы не получите четко определенного выражения для ответа. Структура алгебры позволяет определить один, подчиняя оценку индуцированной топологии.   -  person eh9    schedule 08.11.2012

Ответы (1)


arrow_upward
0
arrow_downward

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

person eh9    schedule 08.11.2012