Разделение проблемы на более мелкие до тех пор, пока отдельные проблемы не могут быть решены независимо, а затем объединение их для ответа на исходный вопрос, известно как методика построения алгоритма « разделяй и властвуй» . [См .: Введение в алгоритмы по CLR]
В последнее время этот подход для решения вычислительных задач, особенно в области очень больших наборов данных, упоминается как MapReduce, а не «разделяй и властвуй».
Мой вопрос заключается в следующем: является ли MapReduce чем-то большим, чем проприетарная структура, основанная на подходе «разделяй и властвуй», или есть детали, которые делают ее уникальной в некотором отношении?
algorithms
эфирное масло
источник
источник
Ответы:
Если вы спрашиваете об архитектуре MapReduce, то это просто техника « разделяй и властвуй» . Однако любая полезная архитектура MapReduce будет иметь множество других инфраструктур для эффективного «разделения», «завоевания» и, наконец, «уменьшения» поставленной проблемы. При большом развертывании MapReduce (1000 вычислительных узлов) эти шаги по разделению работы, вычислению чего-либо и, наконец, получению всех результатов, нетривиальны. Такие вещи, как балансировка нагрузки, обнаружение мертвых узлов, сохранение промежуточного состояния (для длительных проблем), сами по себе являются сложными проблемами.
источник
MapReduce - это структура для реализации алгоритмов «разделяй и властвуй» с чрезвычайно масштабируемым способом , автоматически распределяя единицы работы между узлами в произвольно большом кластере компьютеров и автоматически обрабатывая сбои отдельных узлов путем перераспределения единицы работы. в другой узел.
Это не сверхсложная концепция, а очень полезная часть инфраструктуры.
источник
MapReduce отличается от большинства систем «разделяй и властвуй» довольно фундаментально, но это настолько просто, что многие люди почти упускают это. Настоящий гений в том, чтобы пометить промежуточные результаты.
В типичной (предыдущей) системе «разделяй и властвуй» вы разделяете работу последовательно, выполняете рабочие пакеты параллельно, а затем снова последовательно объединяете результаты этой работы.
В MapReduce вы разделяете работу последовательно, выполняете рабочие пакеты параллельно и помечаете результаты, чтобы указать, какие результаты соответствуют каким другим. Затем объединение выполняется последовательно для всех результатов с одним и тем же тегом, но может выполняться параллельно для результатов с разными тегами.
В большинстве предыдущих систем этап слияния стал узким местом для всех, кроме самых поистине тривиальных задач. С MapReduce все еще может быть, если природа задач требует, чтобы все слияния выполнялись последовательно. Если, однако, задача допускает некоторую степень параллельного объединения результатов, то MapReduce предоставляет простой способ воспользоваться этой возможностью. Большинство других систем выполняют одно из двух: либо выполняют все слияния последовательно только потому, что это может быть необходимо для некоторых задач, либо статически определяют параллельное слияние для конкретной задачи. MapReduce предоставляет вам достаточно данных на этапе слияния, чтобы автоматически планировать как можно большее количество параллелей, при этом гарантируя (при условии, что вы не допустили ошибок на этапе сопоставления), что согласованность сохраняется.
Также обратите внимание, что в MapReduce подразумевается, что все шаги могут быть рекурсивными, поэтому у меня может быть начальный шаг отображения, который разбивает большую задачу на 5 меньших задач, которые могут выполняться параллельно - но каждая из них может (в включите) привязаться к ряду других меньших параллельных задач и так далее.
Это приводит к древовидной структуре как на картографической, так и на сокращающей сторонах, что позволяет быстро разбить большую задачу на достаточное количество частей, чтобы воспользоваться преимуществами множества машин.
источник
MapReduce - это не просто техника «разделяй и властвуй», хотя во многих примерах это выглядит так.
На этапе отображения вы можете и часто хотите установить отношение один ко многим. Таким образом, вы не просто делитесь на случаи.
Между картой и уменьшением есть (в зависимости от реализации) этап сортировки или хеширования. Эффективность этой операции чрезвычайно важна для общих потребностей в ресурсах. Его детали не видны программисту приложения, но этот шаг является сердцем фреймворка.
Операция сокращения - это тип слияния. Который может рассматриваться как победитель, но на практике это, как правило, «выброс данных для последующего использования» или «сохранение данных в хранилище данных». (Обратите внимание: если у вас большие наборы данных, вы действительно хотите, чтобы все было распределено, включая ввод и конечные результаты. Поэтому распределенное хранилище ключей / значений имеет смысл как в качестве места для получения ввода, так и для хранения вывода.)
источник