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

Question

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

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

Answer 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 также является структурой программирования, а не алгоритмом сам по себе, и анализ сложности обычно зарезервирован для алгоритмов.

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

Answer 2

Map-Reduce для машинного обучения в многоядерном режиме стоит посмотреть, сравнивая, как изменяется сложность различных хорошо известных алгоритмов машинного обучения при переходе на MR-дружественную форму.* Приветствие.

Answer 3

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

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

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

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

Второй подход состоит в том, чтобы «сосать это исм».