Различие между MapReduce и картой - уменьшает комбинацию в функциональном программировании
Я считал mapreduce по http://en.wikipedia.org/wiki/MapReduce, понял пример того, как получить количество "слова" во многих "документах". Однако я не понял следующую строку:
Таким образом платформа MapReduce преобразовывает список (ключ, значение) пары в список значений. Это поведение отличается от функционального программирования, отображают и уменьшают комбинацию, которая принимает список произвольных значений и возвращает одно единственное значение, которое комбинирует все значения, возвращенные картой.
Кто-то может уточнить различие снова (платформа MapReduce карта VS и уменьшить комбинацию)? Особенно, что делает уменьшать функциональное программирование, делают?
Благодарит много.
3 ответа
Основное отличие состоит в том, что MapReduce, по-видимому, патентоспособен. (Ничего не мог с собой поделать, извините ...)
Если говорить более серьезно, статья MapReduce, насколько я помню, описывает методологию выполнения вычислений с массовым распараллеливанием. Эта методология основана на конструкции map / reduce, которая была хорошо известна много лет назад, но выходит за рамки таких вопросов, как распространение данных и т. Д.Кроме того, некоторые ограничения налагаются на структуру данных, с которыми работают и возвращаются функциями, используемыми в map -like и reduce -подобных частях вычислений (вещь о данных входящие в списки пар ключ / значение), так что можно сказать, что MapReduce - это специализация , поддерживающая массовый параллелизм, комбинации map и reduce .
Что касается комментария Википедии о функции, отображаемой в конструкции map / reduce функционального программирования, производящей одно значение для каждого входа ... Ну, конечно, есть, но здесь нет никаких ограничений на тип указанного значения . В частности, это может быть сложная структура данных, например, список вещей, к которому вы снова примените преобразование map / reduce . Возвращаясь к примеру «подсчета слов», вы вполне могли бы иметь функцию, которая для заданной части текста создает структуру данных, отображающую слова в количество вхождений, карту , которая поверх ваших документов (или фрагментов документов, в зависимости от обстоятельств) и уменьшают результаты.
Фактически, именно это и происходит в этой статье Фила Хагельберга. Это забавный и в высшей степени короткий пример вычисления, подобного подсчету слов в MapReduce, реализованного в Clojure с map и чем-то эквивалентным reduce ( (apply + (merge- с участием ...)) бит - объединение с реализовано в терминах reduce в clojure.core). Единственное различие между этим примером и примером из Википедии состоит в том, что подсчитываемые объекты представляют собой URL-адреса, а не произвольные слова - кроме этого, у вас есть алгоритм подсчета слов, реализованный с помощью map и reduce , прямо здесь в стиле MapReduce. Причина, по которой он не может полностью квалифицироваться как экземпляр MapReduce, заключается в том, что в нем нет сложного распределения рабочих нагрузок. Все это происходит в одной коробке ... хотя и на всех процессорах, которые она предоставляет.
Подробное описание функции reduce - также известной как fold - см. В Учебнике Грэма Хаттона по универсальности и выразительности функции fold . Он основан на Haskell, но должен быть удобочитаемым, даже если вы не знаете языка, если вы готовы искать пару вещей на Haskell по ходу дела ... Такие вещи, как ++ = конкатенация списков, никакой глубокой магии Haskell.
Используя пример подсчета слов, оригинальная функциональная map() возьмет набор документов, опционально распределит подмножества этого набора, и для каждого документа выдаст одно значение, представляющее количество слов (или вхождения конкретного слова) в документе. Функциональный reduce() затем сложит глобальные подсчеты для всех документов, по одному для каждого документа. Таким образом, вы получаете общий подсчет (либо всех слов, либо определенного слова).
В MapReduce карта выдаст пару (слово, счет) для каждого слова в каждом документе . Затем MapReduce reduce() сложил бы количество каждого слова в каждом документе , не смешивая их в одну кучу. Таким образом, вы получите список слов в паре с их количеством.
MapReduce - это каркас, построенный вокруг расщепления вычисления в параллелизируемые материалы и редукторы. Он основан на знакомой идиоме карты и уменьшается - если вы можете структурировать свои задачи, такие, что они могут быть выполнены независимыми материалами и редукторами, то вы можете написать ее таким образом, что воспользуется каркасом Mapreatuce.
Представьте себе интерпретатор Python, который распознал задачи, которые могут быть вычислены независимо, и создали их на Mapper или редукторные узлы. Если вы пишете
reduce(lambda x, y: x+y, map(int, ['1', '2', '3']))
или
sum([int(x) for x in ['1', '2', '3']])
, вы будете использовать функциональную карту и уменьшить методы в рамках MapReduce. С текущими каркатами MapReduce участвуют намного больше сантехники, но это та же концепция.