Previous Entry Share Next Entry
Map-reduce
zhtw
Каждый раз, когда я с кем-то разговариваю на тему map-reduce, у меня складывается впечатление, что мы говорим на разных языках.

Поэтому я решил написать, что я понимаю под map-reduce, и, надеюсь, все, кто понимают под этим что-то другое, ткнут мне пальцем.


Итак, оператор map.

Вот один из вариантов его определения.

Даны множества X, и Y.

Map -- это оператор, отображающий пары (A, f) в B, где A ⊂ X, B ⊂ Y, f: X → Y, такие, что f(A) = B, а точнее B = { f(x) | x ∈ A }.

Пример 1. f(x) = 2x. map(f, {1, 2, 4}) = {2, 4, 8}.

Пример 2. f(x) = 3x mod 6, map(f, {3, 4, 0}) = { 3, 0 }.

Это лишь пример возможного определения. Когда map реалзуется в языках программирования, обычно делают некоторые отступления. Например, множества могут быть представлены в виде списков или массивов, и, раз уж массивы и списки могут содержать одинаковые элементы, и порядок играет роль, то тогда A и B -- кортежи с равным числом элементов из X и Y соответственно.

Классический вариант map в Лиспе для списков:


(define (map f l)
  (if (null? l)
    '()
    (cons (f (car l)) (map f (cdr l)))))


Или на Питоне для массивов (они же списки)


def map(f, l):
  return [f(x) for x in l]


(Для реализации через генераторы, нужно квадратные скобки заменить на круглые.)

Оператор reduce.

Даны множества X и Y. Reduce отображает тройку (x0, f, <x1, x1... xn>) в x, где

f: X×Y → X,
x, x0 ∈ X,
x1... xn ∈ Y, причем
x = f(...f(f(x0, x1), x2)...)

Пример 1.

f(a, b) = a + b
reduce(0, f, <1, 2, 3, 4, 5>) = 0 + 1 + 2 + 3 + 4 + 5 = 15.

Пример 2.
f(A, b) = A ∪ { b }.
reduce(∅, f, <1, 2, 3, 2, 4>) = { 1, 2, 3, 4 }.

Когда reduce реализуют в языках программирования, кортеж представляют в виде списка, массива или отложенной последовательности.
Классический вариант reduce на Лиспе для списков:


(def (reduce x0 f l)
  (if (null? l)
    x0
    (reduce (f x0 (car l)) f (cdr l)))


На Питоне:

def reduce(x0, f, l)
  res = x0
  for x in l:
    res = f(res, x)
  return res


Reduce очень универсальная операция. Через нее легко определить очень много операций. С первого взгляда неочевидно, но через reduce можно даже определить реверс списка.

Пример на Лиспе:


(def (reverse l)
  (reduce '() (lambda (a b) (cons b a)) l))


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

Map и reduce в сочетании дают очень мощный механизм написания алгоритмов работы с последовательностями.

На самом деле reduce -- это лишь одна из двух симметричных операция folding'а: rfold и lfold. Rfold -- это reduce, а lfold получается, если в f поменять аргументы местами, и определить x так:

x = f(x1, f(x2, ...f(xn, x0)...))

Но это не очень важно.

Так вот, map и reduce -- простейшие операции, известные миллион лет, определены в библиотеках всех известных языков программирования.

А интересны они стали в последнее время исходя и того простого факта, что map легко паралеллится. Reduce тоже паралеллится, но только в частном случае, когда f ассоциативна. В общем же случае, это не так.

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

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

Различные реализации того, что сейчас называют распределенной моделью вычислений map-reduce, вводят и другие ограничения на элементы, чтобы предоставить всякие удобства для программиста. Например, кроме ключа можно еще ввести подключ, и предоставить возможность сортировки каждого из отрезков по подключу, перед тем, как выполнять reduce над ними. Map может принимать в качестве f многозначную функцию и пр.

Как бы то ни было. Чтобы иметь общее представление о том, какие алгоритмы «ложатся» на модель map-reduce, важно помнить что такое базоыве map и reduce.

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

  • 1
Привет!

Просто под map-reduce, скорее всего, когда вы разговариваете на разных языках, другой человек имеет ввиду не операторы [функциональных] языков, а модель распределенных вычислений предложенную Гуглом, кажется, в 2004 году на OSDI (которая была просто "инспирирована" этими операторами ФЯП). За 9 лет много воды утекло и сейчас оригинальная простая модель сильно усложнилась и концептуально и "реальной жизнью", конкретными реализациями для практических задач, всякими Hadoop, MongoDB и пр. А люди по-прежнему для обобщения кластеров и систем хранения с операторами типа map/reduce (разделить, посчитать и смержить) говорят просто "map-reduce".

Как-то так...

Edited at 2013-05-06 08:07 pm (UTC)

Да. Но название модели map-reduce пошло именно от названия операторов map и reduce.

Пример 2. f(x) = 3x mod 6, map(f, {3, 4, 0}) = { 3, 0 }.

map(lambda x: 3*x%6, [3,4,0])
[3, 0, 0]

Кажется 0 не хватает в списке.


PS: хорошая статья ) больше половины даже понятно =)

Edited at 2013-07-31 02:44 pm (UTC)

Re: Опечатка?

Нет, как раз в этом примере, map был определен как оператор над множеством.

  • 1
?

Log in