Взаимосвязь между картой Python Reduce и картой облачных вычислений / Reduce? - PullRequest
Новая
       23

Взаимосвязь между картой Python Reduce и картой облачных вычислений / Reduce?

6 голосов
/ 14 ноября 2011

Я новичок в Python,

Кто-нибудь знает, каковы взаимосвязи между функциями Python (и функциональных языков) map() / reduce() и концепцией MapReduce, относящимися к распределенным вычислениям?

Ответы [ 2 ]

8 голосов
/ 14 ноября 2011

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

Одним из важных соображений является то, что из-за распараллеливания функция reduce должна иметь возможность принимать объекты из функции map, а также объектыиз предыдущих reduce функций.Это имеет больше смысла, когда вы думаете о том, как идет распараллеливание.Многие машины будут свести свои данные к одному объекту, а затем эти объекты будут сведены к конечному результату.Конечно, это может происходить в более чем одном слое, если данных много.

Вот простой пример того, как вы можете использовать каркас карты / сокращения для подсчета слов в списке: 

list = ['a', 'foo', 'bar', 'foobar', 'foo', 'a', 'bar', 'bar', 'bar', 'bar', 'foo']
list2 = ['b', 'foo', 'foo', 'b', 'a', 'bar']

Функция карты будет выглядеть так: 

def wordToDict(word):
  return {word: 1}

И функция сокращения будет выглядеть так: 

def countReduce(d1, d2):
  out = d1.copy()
  for key in d2: 
    if key in out:
      out[key] += d2[key]
    else:
      out[key] = d2[key]
  return out

Тогда вы можете отобразить / уменьшить так: 

reduce(countReduce, map(wordToDict, list + list2))

>>> {'a': 3, 'foobar': 1, 'b': 2, 'bar': 6, 'foo': 5}

Но вы также можете сделать это следующим образом (именно это и сделает параллелизация): 

reduce(countReduce, [reduce(countReduce, map(wordToDict, list)), reduce(countReduce, map(wordToDict, list2))])

>>> {'a': 3, 'foobar': 1, 'b': 2, 'foo': 5, 'bar': 6}
2 голосов
/ 21 ноября 2011

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

В функциональном программировании (где Python позаимствовал эти функции):

  • map применяет некоторую функцию ко всем элементам списка и возвращает новый список
  • reduce применяет некоторую функцию для агрегирования всех значений в некотором списке для получения одного значения.

В распределенных вычислениях MapReduce:

  • мы всегда работаем с парами ключ-значение (ну, просто парами)
  • mapper берет список пар и создает другой список пар («ключ» ввода теряет свою семантику в этом контексте)
  • reducer получает ключ и список значений, соответствующих этому ключу (из выходных данных mapper) и создает некоторый список ключей и значений (единственное место, где «key» имеет семантику ключей, является вводом / отображением редуктора вывод: значения сгруппированы по ключу перед передачей в редуктор)
  • здесь также может быть разделитель и сумматор:)

Обратите внимание, что ни один преобразователь не всегда создает одну выходную пару для каждой входной пары, а редуктор не всегда сводит каждую (ключ, список значений) к одной выходной паре. Картограф и редуктор могут выводить все, что хотят. Например, mapper может использоваться для фильтрации пар - в этом случае он генерирует выходную пару для одних входных пар и игнорирует другие. Также нередко можно получить более одной пары для каждой входной пары преобразователя / редуктора (или для некоторых из них).

Но в большинстве случаев MapReduce может работать аналогично или почти аналогично reduce(reduce_function, map(map_function, list)) - mapper обычно выполняет некоторые вычисления для каждого входа, а редуктор обычно каким-то образом объединяет список значений. Для любых map_function и reduce_function это можно выразить в MapReduce, но не наоборот.

...