Какова вычислительная сложность накладных расходов 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. Затем подставляйте значения для переменных размера проблемы, количества узлов и т.д. Сложно, хотя вы можете пройти с оценками для определенных частей функции стоимости.
Второй подход - "сосать его и увидеть".
Ответ 3
"Map-Reduce для машинного обучения на многоядерном компьютере" стоит посмотреть, сравнивая, как изменяется сложность различных известных алгоритмов машинного обучения при изменении на MR - "дружественная" форма.
Приветствия.