Какова вычислительная сложность MapReduce наверху
Учитывая, что сложность карты и уменьшает задачи, O(map)=f(n) и O(reduce)=g(n) кто-либо не торопился, чтобы записать, как Отображение/Уменьшение внутренних операций (сортировка, перестановка, отправка данных, и т.д.) увеличивает вычислительную сложность? Каковы издержки Отобразить/Уменьшить оркестровки?
Я знаю, что это - ерунда, когда Ваша проблема является достаточно большой, просто не заботьтесь о неэффективности, но для небольших проблем, которые могут работать в маленькой машине или нескольких машинах, я должен пройти боль разработки параллельных алгоритмов, когда у меня есть Отобразить/Уменьшить реализация уже под рукой?
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 - это также среда программирования, а не алгоритм сам по себе, и анализ сложности обычно зарезервирован для алгоритмов.
Наиболее близким к тому, что вы ищете, может быть анализ сложности многопоточных алгоритмов , который намного проще.