Класс "Комбинер" в задании mapreduce

Комбинер запускается после Mapper и до Reducer, он будет принимать в качестве входных данных все данные, испускаемые экземплярами Mapper, в заданном node. затем выдает выходные данные редукторам.

И также, если функция сокращения является как коммутативной и ассоциативной, тогда она может использоваться как Комбинер.

Мой вопрос: что означает в этой ситуации выражение " коммутативный и ассоциативный?

Ответы

Ответ 1

Предположим, у вас есть список номеров, 1 2 3 4 5 6.

Ассоциативный означает, что вы можете выполнить свою операцию и применить ее к любой подгруппе, затем применить ее к результату и получить тот же ответ:

(1) + (2 + 3) + (4 + 5 + 6)
  ==
(1 + 2) + (3 + 4) + (5) + (6)
  ==
...

Подумайте о скобках здесь как выполнении объединителя.

Коммутативный означает, что порядок не имеет значения, поэтому:

1 + 2 + 3 + 4 + 5 + 6
  ==
2 + 4 + 6 + 1 + 2 + 3
  ==
...

Например, добавление, соответствует этому свойству, как видно ранее. "Максимум" соответствует этому свойству выше, так как максимум maxs является максимальным. max (a, b) == max (b, a).

Медиана - пример, который не работает: медиана медианов не является истинной медианной.

Не забывайте другое важное свойство объединителя: типы ввода для ключа/значения и типы вывода ключа/значения должны быть одинаковыми. Например, вы не можете взять строку: int и вернуть строку: float.

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

Ответ 2

Для коммутативности, допустим, ваш редуктор может быть представлен функцией (в математическом терминах), называемой f(). Тогда ваш редуктор коммутативен, если f (a, b) = f (b, a) Например:

sum (A, B) совпадает с суммой (B, A)
xor (A, B) совпадает с xor (B, A)
concat (A, B) не совпадает с concat (B, A)

Для ассоциативности свойство состоит в том, что f (f (a, b), c) = f (a, f (b, c)). Например:

(A + B) + C совпадает с A + (B + C)
(A - B) - C не совпадает с A - (B - C)

Итак, в контексте Map/Reduce ваш редуктор должен уважать эти 2 свойства. Например, если ваш редуктор выполняет только сумму() или max(), он учитывает оба свойства, но что-то вроде mean() или median() не делает, и поэтому вы не можете использовать его в качестве объединителя.

Я лично вижу комбинаторы как мини-редукторы, которые запускаются в памяти после фазы карты как оптимизация для снижения сетевого трафика, и коммутативность/ассоциативность действительно имеет смысл, если вы видите карту/уменьшите этот путь: