分治和分支合并的区别

Question

在C++中，分治和分叉合并有什么区别？分叉和合并是分治的一个特定案例吗？因为分叉和合并只适用于并行计算？谢谢！

- munmunbb

---

两件事情：首先，请去掉“join”、“difference”和“divide”标签，因为它们的标签摘要非常清楚地定义了它们与您的问题无关。好吧，除了“divide”，那只是一个糟糕的标签。第二，这是特定于语言还是通用的？如果是后者，请明确说明。如果是前者，请添加相应语言的标签。 - anon

@QPaysTaxes：值得一提的是，还有一个[tag:language-agnostic]标签。 - eggyal

@eggyal 哦，我从来不知道。那么，楼主应该添加那个标签。 - anon

@eggyal 谢谢大家！第一次使用 :p - munmunbb

Answer 1

"分而治之"是一种通用的编程方法，用于将一个较大的问题分解为更易解决的子问题，分别解决它们（有时需要递归），最终通过组合子问题的答案来得出大问题的答案。这不是C++特有的思想。

"Fork"和"Join"是许多语言中可用的特定并行性原语的名称。 "Fork"会启动另一个执行线程； "Join"会导致当前线程等待另一个线程完成和同步。我相信C++14标准已经内置了这样的原语。许多其他语言没有内置此功能，但通常可以通过库获得（包括早期版本的C ++）。

人们可以使用"Fork"和"Join"来实现增强并行性的"分而治之"。在这种情况下，"fork"将线程发送到单独的子问题中，"join"是必要的步骤，以表示子问题的完成。但是，"join"并没有专门计算"大"问题的组合答案。您可能需要更多的代码而不仅仅是fork和join。

- Ira Baxter

Answer 2

基本上，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)。

- udit043