Какова вычислительная сложность накладных расходов MapReduce

Учитывая, что сложность работы с картами и сокращение задач O(map)=f(n) и O(reduce)=g(n), кто-нибудь потратил время, чтобы записать, как внутренние операции Map/Reduce (сортировка, перетасовка, отправка данных и т.д.) увеличивает вычислительную сложность? Каковы накладные расходы на карту/сокращение оркестровки?

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

Ответы

Ответ 1

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

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

O(n log n * s * (1/p)) where:
 - n is the number of items
 - s is the number of nodes
 - p is the ping time between nodes (assuming equal ping times between all nodes in the network)

Это имеет смысл? Это действительно очень грязно. M/R также является основой программирования, а не самим алгоритмом, и анализ сложности обычно зарезервирован для алгоритмов.

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

Ответ 2

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

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

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

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

Второй подход - "сосать его и увидеть".