разница разделяй и властвуй и разветвляйся и присоединяйся

В С++, в чем разница между разделяй и властвуй и разветвляй и присоединяйся? Является ли вилка и соединение особым случаем «разделяй и властвуй», потому что вилка и соединение применяются только в параллелизме? Спасибо!


c++ parallel-processing fork-join language-agnostic divide-and-conquer
person munmunbb    schedule 16.04.2015    source источник
comment
Две вещи: во-первых, пожалуйста, удалите теги join, difference и divide, так как выдержки из их тегов довольно четко определяют их как не имеющие отношения к вашей проблеме. Ну, кроме divide, а это просто плохой тег. Во-вторых, зависит ли это от языка или не зависит от языка? Если это последнее, пожалуйста, прямо укажите это. Если это первое, добавьте тег для языка.   -  person Fund Monica's Lawsuit    schedule 17.04.2015
comment
@QPaysTaxes: для чего это стоит, есть также тег язык-агностик.   -  person eggyal    schedule 17.04.2015
comment
@eggyal Ха. Я никогда этого не знал. Затем OP должен добавить этот тег.   -  person Fund Monica's Lawsuit    schedule 17.04.2015
comment
@eggyal Спасибо, ребята! Первый пользователь :p   -  person munmunbb    schedule 07.05.2015

Ответы (2)


arrow_upward
1
arrow_downward

По сути, Fork-Join разбивает задачу на мини-задачи до тех пор, пока мини-задача не станет достаточно простой, чтобы ее можно было решить без дальнейших разбивок. Это похоже на алгоритм «разделяй и властвуй». Одна важная концепция, которую следует отметить в этой структуре, заключается в том, что в идеале ни один рабочий поток не простаивает. Они реализуют алгоритм кражи работы, заключающийся в том, что бездействующие работники крадут работу у тех, кто занят.

  Result solve(Problem problem) 
  {
        if (problem is small)
            directly solve problem
        else 
             {
            split problem into independent parts
            fork new subtasks to solve each part
            join all subtasks
            compose result from subresults
          }
  }

В C++14 есть некоторые проблемы, связанные с fork & join , вы можете прочитать больше на этом сайте ( http://www.meetingcpp.com/index.php/br/items/a-look-at-c14-papers-part-2.html< /а> )

person udit043    schedule 07.05.2015

arrow_upward
2
arrow_downward

«Разделяй и властвуй» — это общий метод программирования для разбиения более крупной проблемы на более решаемые подзадачи, решения их по отдельности (а иногда и рекурсивно) и, наконец, получения ответа на большую проблему путем объединения ответов на подзадачи. Это идея, не относящаяся к C++.

«Разветвление» и «объединение» называют специфическими примитивами параллелизма, доступными на многих языках. "Fork" запускает другой поток выполнения; "join" заставляет текущий поток ожидать завершения и синхронизации другого потока. Я считаю, что стандарт С++ 14 имеет встроенные такие примитивы. Многие другие языки не имеют этого встроенного, но часто доступны через библиотеки (включая более ранние версии C++).

Можно использовать «Разветвление» и «Объединение» для реализации «Разделяй и властвуй», усиленного параллелизмом. При таком использовании «форк» отправляет потоки на отдельные подзадачи, а «объединение» необходимо как шаг, сигнализирующий о завершении подзадач. Но «объединение» специально не вычисляет комбинированный ответ на «большую» проблему. Вероятно, вам понадобится больше кода, чем просто разветвление и соединение.

person Ira Baxter    schedule 07.05.2015