更新:为了帮助阐明我要问的内容，我发布了一些 java 代码来理解这个想法。

前一段时间我问了一个question关于如何让算法分解一组数字，我的想法是给它一个数字列表 (1,2,3,4,5) 和一个总数(10 )，它会计算出每个数字的所有倍数加起来等于总数('1*10' or '1*1,1*2,1 *3,1*4' 或 '2*5' 等)。这是我做过的第一个编程练习，所以我花了一段时间才开始工作，但现在我想看看我是否可以扩展它。最初问题中的人说它是可扩展的，但我对如何去做有点困惑。递归部分是我坚持缩放结合所有结果的部分的区域(它所指的表不可缩放但应用缓存我能够使其快速)

我有以下算法(伪代码):

//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 得到processed 这很好，但是如果我需要包含 1 和 10 的结果怎么办？我试图修改表(变量 T)，所以只有我想要的子集在那里，但仍然不起作用，因为就像上面的解决方案一样，它做了一个子集，但无法处理需要更广泛范围的答案。

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

更新:我似乎仍然无法弄清楚如何将 RecursivelyListAllThatWork 变成一个可运行的(我在技术上知道如何去做，但我不明白如何更改 RecursivelyListAllThatWork 算法以便它可以并行运行。其他部分只是为了使示例工作，我只需要在 RecursivelyListAllThatWork 方法上实现可运行)。这是 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;
    }
} 

最佳答案

多线程的一般答案是通过堆栈(LIFO 或 FIFO)取消递归实现。在实现这样的算法时，线程数是算法的固定参数(例如内核数)。

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

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

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

我提出了一种混合方法，第一个线程递归地工作有限数量的 k 作为最大递归深度:示例中的小数据集为 2，但如果更大，我推荐 3。然后这第一部分将生成的中间上下文委托(delegate)给一个线程池，该线程池将使用非递归实现处理剩余的 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 和 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;
    }
}

关于java - 无法对可扩展方法进行多线程处理，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9882260/