Это не может вписаться в одну работу Map / Reduce.Я на самом деле не думаю, что этот вариант использования хорошо подходит для парадигмы M / R в целом, так как он, кажется, плохо распараллеливает и включает в себя огромное количество данных, которые нужно перетасовать.
Радидля простоты я просто переведу ввод и оператор в более простые версии, сохранив их свойства без изменений.Вместо списков множеств и пересечений предположим, что у вас есть списки чисел и сумм (для нашей цели это должно быть эквивалентно).
Итак, вы хотите вычислить все возможные суммы чисел, выбранных из разных списков:
Ввод:
L1: [1, 2, 3]
L2: [4, 5]
L3: [6, 7]
Результаты:
[
1+4+6, 1+4+7, 1+5+6, 1+5+7,
2+4+6, 2+4+7, 2+5+6, 2+5+7,
3+4+6, 3+4+7, 3+5+6, 3+5+7
]
= [11, 12, 12, 13, 12, 13, 13, 14, 13, 14, 14, 15]
И после удаления дубликатов вы получите:
[11, 12, 13, 14, 15]
Контрольная точка: пожалуйста, подтвердите, что я правильно выполнил ваши требования.
Чтобы в итоге вычислить суммы в редукторе, каждый элемент в каждом списке должен быть выведен из картографа с помощью нескольких ключей, которыеравны длинам всех остальных списков, умноженных;и ключи должны позволять объединять все комбинации элементов из разных списков в редукторе.
Поскольку списки не обязательно имеют одинаковый размер, вы можете убедиться в том, что выше, только если вы знаете точную длину каждого другогосписок в наборе данных при оценке каждой записи списка.(Эти предварительные знания означают другое задание M / R для создания массива длин.) Затем вы можете вычислить ключ путем объединения всех возможных комбинаций индексов элементов.
В нашем примере значение '1' (который является индексом 0 в L1), будет генерироваться под следующими ключами: "000" (то есть 1+4+6), "001", "010", "011" (исследуя все возможные пути от '1' до остальныхсписки).Для значения «7» (индекс 1 в L3) у нас будет: "001", "011", "101", "111", "201", "211".
.это, в итоге вы получите редуктор с цифрами для суммирования по одному и тому же ключу (что именно то, что вы хотели, за исключением того, что на этом этапе у вас все еще есть дублирующиеся суммы):
"000" -> [1, 4, 6]
"001" -> [1, 4, 7]
...
"211" -> [3, 5, 7]
Ноэто довольно много данных, чтобы перемешать!Конечно, вы также можете использовать редуктор как объединитель, но все же: с N списками размера M вы будете генерировать элементы в каждом списке M ^ N раз.И я предполагаю, что N исчисляется миллионами (по крайней мере), иначе вы бы не рассматривали карту / уменьшение.Более того, каждый ключ, который вы выводите из карты, будет строкой длины N (количество списков в наборе данных).Таким образом, вы можете легко получить ключи размером в МБ (даже если вы переключитесь на более компактный двоичный формат).
И для этого вам понадобится предварительное задание, которое вычисляет массив размеров списков.и, наконец, дедупликации может потребоваться еще одна работа (если вы не пишете в какое-то хранилище, которое делает это за вас).
В заключение, должен быть лучший способ ... Если ваш набор данных подходитв памяти на одном узле, попробуйте.Пересечения, которые вы вычисляете, будут сужаться естественным образом (и, если вам повезет), большинство из них получится как пустой набор достаточно быстро.