Разница между MapReduce и комбинацией Map-Reduce в функциональном программировании

Question

Я прочитал mapreduce на http://en.wikipedia.org/wiki/MapReduce, понял пример того, как получить счетчик «слова» во многих «документах». Однако я не понял следующую строку:

Таким образом, инфраструктура MapReduce преобразует список пар (ключ, значение) в список значений. Это поведение отличается от функциональной карты программирования и комбинации сокращений, которая принимает список произвольных значений и возвращает одно единственное значение, которое объединяет все значения, возвращаемые картой.

Может ли кто-нибудь еще раз уточнить разницу (MapReduce framework VS map и уменьшить комбинацию)? Особенно, что делает редуцирующее функциональное программирование?

Большое спасибо.

Answer 1

Основным отличием будет то, что MapReduce, очевидно, патентоспособен. (ничего не могу с собой поделать, извините ...)

На более серьезном замечании статья MapReduce, насколько я помню, описывает методологию выполнения вычислений в широком распараллеливании. Эта методология основана на конструкции map / lower, которая была хорошо известна много лет назад, но выходит за рамки таких вопросов, как распределение данных и т. Д. Кроме того, на структуру данных, которые обрабатываются и возвращаются функциями, используемыми в map -подобные и reduce -подобные части вычислений (вещь о данных, поступающих в списках пар ключ / значение), так что вы можете сказать, что MapReduce является дружественной для массивного параллелизма специализацией из комбинации map & reduce.

Что касается комментария из Википедии о функции, отображаемой в конструкции функционального программирования map / reduce, выдающей одно значение на вход ... Хорошо, конечно, но здесь ограничений вообще нет по типу указанного значения . В частности, это может быть сложная структура данных, например, список вещей, к которым вы снова примените преобразование map / reduce. Возвращаясь к примеру «подсчета слов», вы вполне могли бы иметь функцию, которая для данной части текста генерирует структуру данных, отображающую слова в счетчики вхождений, map, которые поверх ваших документов (или кусков документов, как случай может быть) и reduce результаты.

На самом деле, именно это и происходит в этой статье Фила Хагельберга. Это забавный и в высшей степени короткий пример вычисления, подобного подсчету слов в MapReduce, реализованного в Clojure с map и эквивалентного reduce (бит (apply + (merge-with ...)) - merge-with реализован в терминах reduce в clojure.core). Единственное различие между этим и примером из Википедии состоит в том, что подсчитываемые объекты являются URL-адресами, а не произвольными словами - кроме этого, у вас есть алгоритм подсчета слов, реализованный с map и reduce, стиль MapReduce, верно там. Причина, по которой он может не полностью квалифицироваться как экземпляр MapReduce, заключается в том, что здесь нет сложного распределения рабочих нагрузок. Все это происходит в одном блоке ... хотя и на всех процессорах, которые предоставляет блок.

Подробное описание функции reduce - также известной как fold - см. В руководстве Грэма Хаттона , посвященном универсальности и выразительности складки . Это основано на Haskell, но должно быть читабельным, даже если вы не знаете язык, если вы готовы посмотреть на Haskell или два на ходу ... Такие вещи, как ++ = конкатенация списков, не глубокая Магия Хаскелла.

Answer 2

MapReduce - это фреймворк, построенный на разделении вычислений на распараллеливаемые преобразователи и преобразователи. Он основан на знакомом идиоме map и Reduce - если вы можете структурировать свои задачи так, чтобы они могли выполняться независимыми преобразователями и преобразователями, то вы можете написать это способом, который использует преимущества инфраструктуры MapReduce.

Представьте себе интерпретатор Python, который распознает задачи, которые могут быть вычислены независимо, и направляет их на узлы отображения или редуктора. Если вы написали

reduce(lambda x, y: x+y, map(int, ['1', '2', '3']))

или

sum([int(x) for x in ['1', '2', '3']])

вы будете использовать функциональную карту и сокращать методы в среде MapReduce. В современных инфраструктурах MapReduce задействовано гораздо больше сантехники, но это та же концепция.

Answer 3

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

В MapReduce карта будет выдавать пару (слово, количество) для каждое слово в каждый документ . Затем MapReduce reduce() будет складывать количество каждого слова в каждого документа , не смешивая их в одну стопку. Таким образом, вы получите список слов в паре с их количеством.