无法对可扩展方法进行多线程处理

更新：为了帮助澄清我的要求，我发布了一些java代码来表达这个想法。

前段时间我问了一个question https://stackoverflow.com/questions/7265576/can-brute-force-algorithms-scale/7265593#7265593关于如何获得一种算法来分解一组数字，我们的想法是给它一个数字列表(1,2,3,4,5)和总计（10）并且它会计算出每个数字的所有倍数，加起来等于总数（'1*10' or '1*1,1*2,1*3,1*4' or '2*5'，ETC..）。这是我做过的第一个编程练习，所以我花了一段时间才让它工作，但现在我想尝试看看是否可以扩展它。最初问题中的人说它是可扩展的，但我对如何做到这一点有点困惑。递归部分是我坚持缩放组合所有结果的部分的区域（它引用的表不可扩展，但应用缓存我能够使其快速）

我有以下算法（伪代码）：

//generates table
for i = 1 to k
    for z = 0 to sum:
        for c = 1 to z / x_i:
            if T[z - c * x_i][i - 1] is true:
                set T[z][i] to true

//uses table to bring all the parts together
function RecursivelyListAllThatWork(k, sum) // Using last k variables, make sum
    /* Base case: If we've assigned all the variables correctly, list this
     * solution.
     */
    if k == 0:
        print what we have so far
        return

    /* Recursive step: Try all coefficients, but only if they work. */
    for c = 0 to sum / x_k:
       if T[sum - c * x_k][k - 1] is true:
           mark the coefficient of x_k to be c
           call RecursivelyListAllThatWork(k - 1, sum - c * x_k)
           unmark the coefficient of x_k

我真的不知道如何线程/多重处理 RecursivelyListAllThatWork 函数。我知道如果我向它发送一个较小的 K（它是列表中项目总数的整数），它将处理该子集，但我不知道如何组合子集中的结果。例如，如果列表是[1,2,3,4,5,6,7,8,9,10]我发送 K=3 然后只处理 1,2,3 这很好，但是如果我需要包含 1 和 10 的结果怎么办？我试图修改表（变量 T），所以只有我想要的子集在那里，但仍然不起作用，因为，像上面的解决方案一样，它做了一个子集，但无法处理需要更广泛范围的答案。

如果有人可以解释如何从概念上打破这个递归步骤以便可以使用其他核心/机器，我不需要任何代码。

更新：我似乎仍然不知道如何将 RecursivelyListAllThatWork 变成可运行的（我在技术上知道如何做到这一点，但我不明白如何更改 RecursivelyListAllThatWork 算法以便它可以并行运行。其他部分只是为了让示例工作，我只需要在 RecursivelyListAllThatWork 方法上实现 runnable ）。这是java代码：

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class main
{
    public static void main(String[] args)
    {
        System.out.println("starting..");
        int target_sum = 100;
        int[] data = new int[] { 10, 5, 50, 20, 25, 40 };
        List T = tableGeneator(target_sum, data);
        List<Integer> coeff = create_coeff(data.length);
        RecursivelyListAllThatWork(data.length, target_sum, T, coeff, data);
    }

    private static List<Integer> create_coeff(int i) {
        // TODO Auto-generated method stub
        Integer[] integers = new Integer[i];
        Arrays.fill(integers, 0);
        List<Integer> integerList = Arrays.asList(integers);
        return integerList;
    }


    private static void RecursivelyListAllThatWork(int k, int sum, List T, List<Integer> coeff, int[] data) {
        // TODO Auto-generated method stub
        if (k == 0) {
            //# print what we have so far
            for (int i = 0; i < coeff.size(); i++) {
                System.out.println(data[i] + " = " + coeff.get(i));
            }

            System.out.println("*******************");
            return;
        }

        Integer x_k = data[k-1];
        //  Recursive step: Try all coefficients, but only if they work. 
        for (int c = 0; c <= sum/x_k; c++) { //the c variable caps the percent
            if (T.contains(new Point((sum - c * x_k), (k-1))))
            {
                    // mark the coefficient of x_k to be c
                    coeff.set((k-1), c);
                    RecursivelyListAllThatWork((k - 1), (sum - c * x_k), T, coeff, data);
                    // unmark the coefficient of x_k
                    coeff.set((k-1), 0);
            }

        }

    }

    public static List tableGeneator(int target_sum, int[] data) {
        List T = new ArrayList();
        T.add(new Point(0, 0));

        float max_percent = 1;
        int R = (int) (target_sum * max_percent * data.length);
        for (int i = 0; i < data.length; i++)
        {
            for (int s = -R; s < R + 1; s++)
            {
                int max_value = (int) Math.abs((target_sum * max_percent)
                        / data[i]);
                for (int c = 0; c < max_value + 1; c++)
                {
                    if (T.contains(new Point(s - c * data[i], i)))
                    {
                        Point p = new Point(s, i + 1);
                        if (!T.contains(p))
                        {
                            T.add(p);
                        }
                    }
                }
            }
        }
        return T;
    }
} 

多线程的一般答案是通过堆栈（后进先出或先入先出）来取消递归实现。当实现这样的算法时，线程的数量是算法的固定参数（例如核心的数量）。

为了实现它，当测试条件结束递归时，语言调用堆栈被替换为存储最后上下文作为检查点的堆栈。在你的情况下是k=0 or coeff值与目标总和匹配。

去递归之后，第一个实现是运行多个线程来消耗堆栈，但堆栈访问成为争用点，因为它可能需要同步。

更好的可扩展解决方案是为每个线程专用一个堆栈，但需要在堆栈中初始生成上下文。

我提出了一种混合方法，其中第一个线程递归地工作有限数量的线程k作为最大递归深度：示例中的小数据集为 2，但如果较大，我建议使用 3。然后，第一部分将生成的中间上下文委托给一个线程池，该线程池将处理剩余的内容k具有非递归实现。该代码不是基于您使用的复杂算法，而是基于相当“基本”的实现：

import java.util.Arrays;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class MixedParallel
{
    // pre-requisite: sorted values !!
    private static final int[] data = new int[] { 5, 10, 20, 25, 40, 50 };

    // Context to store intermediate computation or a solution
    static class Context {
        int k;
        int sum;
        int[] coeff;
        Context(int k, int sum, int[] coeff) {
            this.k = k;
            this.sum = sum;
            this.coeff = coeff;
        }
    }

    // Thread pool for parallel execution
    private static ExecutorService executor;
    // Queue to collect solutions
    private static Queue<Context> solutions;

    static {
        final int numberOfThreads = 2;
        executor =
            new ThreadPoolExecutor(numberOfThreads, numberOfThreads, 1000, TimeUnit.SECONDS,
                                   new LinkedBlockingDeque<Runnable>());
        // concurrent because of multi-threaded insertions
        solutions = new ConcurrentLinkedQueue<Context>();
    }


    public static void main(String[] args)
    {
        int target_sum = 100;
        // result vector, init to 0
        int[] coeff = new int[data.length];
        Arrays.fill(coeff, 0);
        mixedPartialSum(data.length - 1, target_sum, coeff);

        executor.shutdown();
        // System.out.println("Over. Dumping results");
        while(!solutions.isEmpty()) {
            Context s = solutions.poll();
            printResult(s.coeff);
        }
    }

    private static void printResult(int[] coeff) {
        StringBuffer sb = new StringBuffer();
        for (int i = coeff.length - 1; i >= 0; i--) {
            if (coeff[i] > 0) {
                sb.append(data[i]).append(" * ").append(coeff[i]).append("   ");
            }
        }
        System.out.println(sb.append("from ").append(Thread.currentThread()));
    }

    private static void mixedPartialSum(int k, int sum, int[] coeff) {
        int x_k = data[k];
        for (int c = sum / x_k; c >= 0; c--) {
            coeff[k] = c;
            int[] newcoeff = Arrays.copyOf(coeff, coeff.length);
            if (c * x_k == sum) {
                //printResult(newcoeff);
                solutions.add(new Context(0, 0, newcoeff));
                continue;
            } else if (k > 0) {
                if (data.length - k < 2) {
                    mixedPartialSum(k - 1, sum - c * x_k, newcoeff);
                    // for loop on "c" goes on with previous coeff content
                } else {
                    // no longer recursive. delegate to thread pool
                    executor.submit(new ComputePartialSum(new Context(k - 1, sum - c * x_k, newcoeff)));
                }
            }
        }
    }

    static class ComputePartialSum implements Callable<Void> {
        // queue with contexts to process
        private Queue<Context> contexts;

        ComputePartialSum(Context request) {
            contexts = new ArrayDeque<Context>();
            contexts.add(request);
        }

        public Void call() {
            while(!contexts.isEmpty()) {
                Context current = contexts.poll();
                int x_k = data[current.k];
                for (int c = current.sum / x_k; c >= 0; c--) {
                    current.coeff[current.k] = c;
                    int[] newcoeff = Arrays.copyOf(current.coeff, current.coeff.length);
                    if (c * x_k == current.sum) {
                        //printResult(newcoeff);
                        solutions.add(new Context(0, 0, newcoeff));
                        continue;
                    } else if (current.k > 0) {
                        contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff));
                    }
                }
            }
            return null;
        }
    }
}

您可以检查哪个线程找到了输出结果，并检查所有涉及的线程：递归模式下的主线程和上下文堆栈模式下池中的两个线程。

现在这个实现是可扩展的data.length高：

• 最大递归深度限制在低级别的主线程
• 池中的每个线程都使用自己的上下文堆栈，不会与其他线程争用
• 现在要调整的参数是numberOfThreads and maxRecursionDepth

所以答案是肯定的，你的算法可以并行化。这是基于您的代码的完全递归实现：

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class OriginalParallel
{
    static final int numberOfThreads = 2;
    static final int maxRecursionDepth = 3;

    public static void main(String[] args)
    {
        int target_sum = 100;
        int[] data = new int[] { 50, 40, 25, 20, 10, 5 };
        List T = tableGeneator(target_sum, data);
        int[] coeff = new int[data.length];
        Arrays.fill(coeff, 0);
        RecursivelyListAllThatWork(data.length, target_sum, T, coeff, data);
        executor.shutdown();
    }

    private static void printResult(int[] coeff, int[] data) {
        StringBuffer sb = new StringBuffer();
        for (int i = coeff.length - 1; i >= 0; i--) {
            if (coeff[i] > 0) {
                sb.append(data[i]).append(" * ").append(coeff[i]).append("   ");
            }
        }
        System.out.println(sb.append("from ").append(Thread.currentThread()));
    }

    // Thread pool for parallel execution
    private static ExecutorService executor;
    static {
        executor =
            new ThreadPoolExecutor(numberOfThreads, numberOfThreads, 1000, TimeUnit.SECONDS,
                                   new LinkedBlockingDeque<Runnable>());
    }

    private static void RecursivelyListAllThatWork(int k, int sum, List T, int[] coeff, int[] data) {
        if (k == 0) {
            printResult(coeff, data);
            return;
        }
        Integer x_k = data[k-1];
        //  Recursive step: Try all coefficients, but only if they work. 
        for (int c = 0; c <= sum/x_k; c++) { //the c variable caps the percent
            if (T.contains(new Point((sum - c * x_k), (k-1)))) {
                    // mark the coefficient of x_k to be c
                    coeff[k-1] = c;
                    if (data.length - k != maxRecursionDepth) {
                        RecursivelyListAllThatWork((k - 1), (sum - c * x_k), T, coeff, data);
                    } else {
                        // delegate to thread pool when reaching depth 3
                        int[] newcoeff = Arrays.copyOf(coeff, coeff.length);
                        executor.submit(new RecursiveThread(k - 1, sum - c * x_k, T, newcoeff, data)); 
                    }
                    // unmark the coefficient of x_k
                    coeff[k-1] = 0;
            }
        }
    }

    static class RecursiveThread implements Callable<Void> {
        int k;
        int sum;
        int[] coeff;
        int[] data;
        List T;

        RecursiveThread(int k, int sum, List T, int[] coeff, int[] data) {
            this.k = k;
            this.sum = sum;
            this.T = T;
            this.coeff = coeff;
            this.data = data;
            System.out.println("New job for k=" + k);
        }

        public Void call() {
            RecursivelyListAllThatWork(k, sum, T, coeff, data);
            return null;
        }
    }

    public static List tableGeneator(int target_sum, int[] data) {
        List T = new ArrayList();
        T.add(new Point(0, 0));

        float max_percent = 1;
        int R = (int) (target_sum * max_percent * data.length);
        for (int i = 0; i < data.length; i++) {
            for (int s = -R; s < R + 1; s++) {
                int max_value = (int) Math.abs((target_sum * max_percent) / data[i]);
                for (int c = 0; c < max_value + 1; c++) {
                    if (T.contains(new Point(s - c * data[i], i))) {
                        Point p = new Point(s, i + 1);
                        if (!T.contains(p)) {
                            T.add(p);
                        }
                    }
                }
            }
        }
        return T;
    }
}