Простое объяснение MapReduce?

Движение полностью вниз к основам для Карты и Уменьшает.

Карта является функцией, которая "преобразовывает" объекты в некоторый список к другому виду объекта и откладывает их в том же виде списка.

предполагают, что у меня есть список чисел: [1,2,3] и я хочу удвоить каждое число, в этом случае, функция для "удвоения каждого числа" является функцией x = x * 2. И без отображений, я мог записать простой цикл, сказать

A = [1, 2, 3]
foreach (item in A) A[item] = A[item] * 2

, и я буду иметь = [2, 4, 6], но вместо того, чтобы писать циклы, если у меня есть функция карты, я мог бы записать

A = [1, 2, 3].Map(x => x * 2)

, x => x * 2 является функцией, которая будет выполняться против элементов в [1,2,3]. То, что происходит, - то, что программа берет каждый объект, выполнитесь (x => x * 2) против него путем создания x, равняется каждому объекту, и произведите список результатов.

1 : 1 => 1 * 2 : 2  
2 : 2 => 2 * 2 : 4  
3 : 3 => 3 * 2 : 6  

поэтому после выполнения карты функционируют с (x => x * 2), Вы имели бы [2, 4, 6].

Уменьшают , функция, которая "собирает" объекты в списках, и выполните некоторое вычисление на весь из них, таким образом уменьшив их до единственного значения.

Нахождение суммы или нахождение средних чисел являются всеми экземплярами уменьшать функции. Такой, как будто у Вас есть список чисел, скажите [7, 8, 9], и Вы хотите их подведенный итог, Вы записали бы цикл как это

A = [7, 8, 9]
sum = 0
foreach (item in A) sum = sum + A[item]

, Но, если у Вас есть доступ к уменьшать функции, Вы могли бы записать его как это

A = [7, 8, 9]
sum = A.reduce( 0, (x, y) => x + y )

Теперь, это немного сбивает с толку, почему существует 2 аргумента (0, и функция с X и Y) передал. Для уменьшать функции, чтобы быть полезным, это должно быть в состоянии взять 2 объекта, вычислить что-то и "уменьшить" это 2 объекта всего до одного единственного значения, таким образом программа могла уменьшить каждую пару, пока у нас нет единственного значения.

выполнение было бы следовать:

result = 0
7 : result = result + 7 = 0 + 7 = 7
8 : result = result + 8 = 7 + 8 = 15
9 : result = result + 9 = 15 + 9 = 24

, Но Вы не хотите запускаться с, обнуляет все время, таким образом, первый аргумент там, чтобы позволить Вам определить, что семя оценивает конкретно значение в первом result = строка.

говорят, что Вы хотите суммировать 2 списка, это могло бы быть похожим на это:

A = [7, 8, 9]
B = [1, 2, 3]
sum = 0
sum = A.reduce( sum, (x, y) => x + y )
sum = B.reduce( sum, (x, y) => x + y )

или версия Вы были бы более вероятно для нахождения в реальном мире:

A = [7, 8, 9]
B = [1, 2, 3]

sum_func = (x, y) => x + y
sum = A.reduce( B.reduce( 0, sum_func ), sum_func )

хорошая вещь в программном обеспечении DB, потому что, с поддержкой Map\Reduce можно работать с базой данных, не будучи должен знать, как данные хранятся в DB для использования его, это - то, для чего механизм DB.

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

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

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

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

функция карты принимает данные и производит в большом количестве результат, который сохранен в барьере. Эта функция может работать параллельно с большим количеством того же задача карты . Набор данных может тогда быть , уменьшил до скалярной величины.

Поэтому, если Вы думаете о нем как SQL-оператор

SELECT SUM(salary)
FROM employees
WHERE salary > 1000
GROUP by deptname

, Мы можем использовать карта для получения нашего подмножества сотрудников с зарплатой> 1000, который карта испускает к барьеру в блоки размера группы.

Уменьшают , суммирует каждую из тех групп. Предоставление Вам Ваш набор результатов.

просто щипнул это от моего университет примечания исследования к документу Google

1. Берут набор данных
2. , Выполняют некоторое преобразование, которое преобразовывает каждую данную величину в другой вид данной величины
3. Объединение те новые данные в еще более простые данные

, Шаг 2 является Картой. Шаг 3, Уменьшают.

, Например,

1. Получают время между двумя импульсами на паре измерителей давления на дороге
2. Карта, те времена в скорости, основанные на расстоянии метров
3. , Уменьшают те скорости до средней скорости

причина, MapReduce разделяется между Картой, и Уменьшите, то, потому что различные части могут легко быть сделаны параллельно. (Особенно, если Уменьшают, имеет определенные математические свойства.)

Для сложного, но хорошего описания MapReduce, см.: Модель программирования MapReduce Google - Пересмотренный (PDF) .

Давайте возьмем пример от бумага Google . Цель MapReduce состоит в том, чтобы быть в состоянии использовать эффективно загрузку блоков обработки, работающих в параллелях на некоторые алгоритмы. exemple следующий: Вы хотите извлечь все слова и их количество в ряде документов.

Типичная реализация:

for each document
    for each word in the document
        get the counter associated to the word for the document
        increment that counter 
    end for
end for

реализация MapReduce:

Map phase (input: document key, document)
for each word in the document
    emit an event with the word as the key and the value "1"
end for

Reduce phase (input: key (a word), an iterator going through the emitted values)
for each value in the iterator
    sum up the value in a counter
end for

, Вокруг которого, у Вас будет основная программа, которая разделит набор документов в "разделениях", которые будут обработаны параллельно для фазы Карты. Испускаемые значения записаны рабочим в буфере, характерном для рабочего. Основная программа тогда делегирует других рабочих для выполнения Уменьшать фазы, как только это уведомляется, что буфер готов быть обработанным.

Каждый рабочий произвел (быть Картой, или Уменьшать рабочий) на самом деле файл, хранивший в распределенной файловой системе (GFS для Google) или в распределенной базе данных для CouchDB.

MAP и REDUCE - старые функции Lisp с того времени, когда человек убил последних динозавров.

Представьте, что у вас есть Список городов с информацией о названии, количестве людей, проживающих там, и размере города:

(defparameter *cities*
  '((a :people 100000 :size 200)
    (b :people 200000 :size 300)
    (c :people 150000 :size 210)))

Теперь вы можете найти город с самой высокой плотностью населения.

Сначала мы создадим список названий городов и Плотность населения с использованием MAP:

(map 'list
     (lambda (city)
         (list (first city)
               (/ (getf (rest city) :people)
                  (getf (rest city) :size))))
     *cities*)

=>   ((A 500) (B 2000/3) (C 5000/7))

Используя REDUCE, мы теперь можем найти город с наибольшей плотностью населения.

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        '((A 500) (B 2000/3) (C 5000/7)))

 =>   (C 5000/7)

Объединяя обе части, мы получаем следующий код:

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        (map 'list
             (lambda (city)
                (list (first city)
                   (/ (getf (rest city) :people)
                      (getf (rest city) :size))))
             *cities*))

Давайте введем функции:

(defun density (city)
   (list (first city)
         (/ (getf (rest city) :people)
            (getf (rest city) :size))))

(defun max-density (a b)
   (if (> (second a) (second b))
          a
          b))

Затем мы можем написать нашу MAP Сократить код как:

(reduce 'max-density
        (map 'list 'density *cities*))

 =>   (C 5000/7)

Он вызывает MAP и REDUCE (оценка наизнанку), поэтому он называется Карта уменьшения .