GrPPI
0.3.1
Generic and Reusable Parallel Pattern Interface
|
The divide/conquer pattern splits a problem into two or more independent subproblems until a base case is reached. The base case is solved directly and the results of the subproblems are combined until the final solution of the original problem is obtained.
The interface to the Divide&Conquer pattern is provided by function grppi::divide_conquer()
. As all functions in GrPPI, this function takes as its first argument an execution policy.
There is a single variant:
The key elements of the divide/conquer pattern are: a Divider operation that divides a problem into subproblems, a Solver operation that is used to solve a subproblem, and a Combiner operation that is used to merge results of subproblems.
A Divider is any C++ callable entity that takes a problem and returns a collection of subproblems. The returned collection of subproblems must be iterable. This allows returning any standard C++ sequence container, or even a plain array. When a problem cannot be divided into subproblems, the divider returns a collection with a single subproblem.
The Solver is any C++ callable entity that takes a problem and turns it into a solution. The signature of the solver takes as argument a problem and returns the corresponding solution.
The Combiner is any C++ callable entity capable to combine two solutions. The signature of the combiner takes two solutions and returns a new combined solution.
The divide/conquer pattern takes an input problem and generates an output problem.
Example: Merge sort of an array.