与递归函数并行编程？

Question

问题的背景：我正在尝试编写一个难题解决方案算法，该算法利用多核处理器和并行处理的优势。但是，理想/最简单的解决方案是简单的递归函数。

分解解决方案以同时利用并行处理 和 递归函数的最佳方法是什么？

下面的代码是一种简单的难题解决算法的解决方案（它可以正常工作）。这个例子中的难题很简单-有14个插槽，编号为1-14。每个拼图都有一个唯一的ID，一个告诉您可以在哪里开始和停止的范围（例如6-8表示它
仅
适合6-8插槽）和一个价格。该算法尝试找到使解决方案的价格最大化的解决方案。一个插槽只能容纳1个，并且可以使用空插槽。该解决方案将告诉您使用了哪些部件以及总成本。（为简单起见，还假设必须填充插槽1）。

我尝试将并行性和递归相结合的解决方案是在下面使用的方法：为每个使用插槽1的部件创建一个Task，然后在Task中以递归方式查看其余部件，将它们分配到剩余空间中，同时使成本最大化。这是最好的解决方案（可能不是，这就是为什么我在这里）。如何改善？使用并行/递归解决方案时还有其他好的建议吗？

尽管简单的递归在这里可以很好地工作，但是我正在用一个具有200个插槽和5000个拼图的拼图来描述这种运行方式。

这也是此示例的解决方案：

ID=1 Price=10.0 Range=1-6
ID=12 Price=8.0 Range=9-14
ID=15 Price=3.0 Range=7-8


public class Puzzle
{

    public PuzzleSet calculateResults(PuzzleSet input) throws Exception
    {   
        System.out.println(System.currentTimeMillis());
        PuzzleSet results = getPriceMultithread((PuzzleSet)SerializationUtils.clone(input));
        System.out.println(System.currentTimeMillis());
        return results;
    }

    private PuzzleSet getPriceMultithread(PuzzleSet input) throws Exception
    {
        PuzzleSet initial = input.startsAtPoint(1);

        ExecutorService exec = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()+1);
        Collection<Callable<PuzzleSet>> tasks = new ArrayList<Callable<PuzzleSet>>();

        for (int i=0; i<initial.size(); i++)
        {
            final PuzzleData d = initial.get(i);
            final PuzzleSet start = input.higherThan(initial.get(i).rangeUpper);
            tasks.add(new Callable<PuzzleSet>() {
                public PuzzleSet call() {
                    PuzzleSet s = new PuzzleSet();
                    s.add(d);
                    s.addAll(getPrice(start));
                    return s;
                }
            });
        }

        List<Future<PuzzleSet>> results = exec.invokeAll(tasks);
        PuzzleSet max = new PuzzleSet();
        double maxD = 0.0;
        for (int i=0; i<results.size(); i++)
        {
            PuzzleSet temp = results.get(i).get();
            double sum = temp.sum();
            if (sum > maxD)
            {
                maxD = sum;
                max = temp;
            }
        }
        return max;
    }

    private PuzzleSet getPrice(PuzzleSet input)
    {
        if (input == null || input.size() == 0)  return new PuzzleSet();

        double maxD = 0.0;
        PuzzleSet max = new PuzzleSet();
        for (int i=0; i<input.size(); i++)
        {
            PuzzleSet vs = input.higherThan(input.get(i).rangeUpper);
            PuzzleSet s = getPrice(vs);
            double d = s.sum();
            double pTemp = input.get(i).price + d;
            if (pTemp > maxD)
            {
                maxD = pTemp;
                s.add(input.get(i));
                max = s;
            }
        }       
        return max;
    }

    public static void main(String arg[]) throws Exception
    {
        PuzzleSet s = new PuzzleSet();

        PuzzleData v1 = new PuzzleData();
        v1.rangeLower = 1;
        v1.rangeUpper = 6;
        v1.price = 10;
        v1.ID = 1;
        s.add(v1);

        PuzzleData v2 = new PuzzleData();
        v2.rangeLower = 7;
        v2.rangeUpper = 11;
        v2.price = 0;
        v2.ID = 2;
        s.add(v2);

        PuzzleData v3 = new PuzzleData();
        v3.rangeLower = 12;
        v3.rangeUpper = 14;
        v3.price = 7;
        v3.ID = 3;
        s.add(v3);

        PuzzleData v5 = new PuzzleData();
        v5.rangeLower = 7;
        v5.rangeUpper = 9;
        v5.price = 0;
        v5.ID = 4;
        s.add(v5);

        PuzzleData v6 = new PuzzleData();
        v6.rangeLower = 10;
        v6.rangeUpper = 14;
        v6.price = 5;
        v6.ID = 5;
        s.add(v6);

        PuzzleData v7 = new PuzzleData();
        v7.rangeLower = 1;
        v7.rangeUpper = 3;
        v7.price = 5;
        v7.ID = 6;
        s.add(v7);

        PuzzleData v8 = new PuzzleData();
        v8.rangeLower = 4;
        v8.rangeUpper = 9;
        v8.price = 0;
        v8.ID = 7;
        s.add(v8);

        PuzzleData v10 = new PuzzleData();
        v10.rangeLower = 1;
        v10.rangeUpper = 5;
        v10.price = 3;
        v10.ID = 8;
        s.add(v10);

        PuzzleData v11 = new PuzzleData();
        v11.rangeLower = 6;
        v11.rangeUpper = 11;
        v11.price = 2;
        v11.ID = 9;
        s.add(v11);

        PuzzleData v12 = new PuzzleData();
        v12.rangeLower = 12;
        v12.rangeUpper = 14;
        v12.price = 7;
        v12.ID = 10;
        s.add(v12);

        PuzzleData v14 = new PuzzleData();
        v14.rangeLower = 4;
        v14.rangeUpper = 8;
        v14.price = 1;
        v14.ID = 11;
        s.add(v14);

        PuzzleData v15 = new PuzzleData();
        v15.rangeLower = 9;
        v15.rangeUpper = 14;
        v15.price = 8;
        v15.ID = 12;
        s.add(v15);

        PuzzleData v16 = new PuzzleData();
        v16.rangeLower = 1;
        v16.rangeUpper = 5;
        v16.price = 3;
        v16.ID = 13;
        s.add(v16);

        PuzzleData v17 = new PuzzleData();
        v17.rangeLower = 6;
        v17.rangeUpper = 8;
        v17.price = 1;
        v17.ID = 14;
        s.add(v17);

        PuzzleData v18 = new PuzzleData();
        v18.rangeLower = 7;
        v18.rangeUpper = 8;
        v18.price = 3;
        v18.ID = 15;
        s.add(v18);

        PuzzleSet x = new Puzzle().calculateResults(s); 
        for (int i=0; i<x.size(); i++)
        {
            System.out.println(x.get(i));
        }

    }
}

public class PuzzleData implements Serializable
{
    public int rangeLower;
    public int rangeUpper;
    public int ID;
    public double price;

    public String toString()
    {
        return "ID=" + ID + " Price=" + price + " Range=" + rangeLower + "-" + rangeUpper;
    }
}

public class PuzzleSet extends ArrayList<PuzzleData> implements Serializable
{
    public PuzzleSet higherThan(int lowBound)
    {
        PuzzleSet s = new PuzzleSet();
        for (int i=0; i<size(); i++)
        {
           if (get(i).rangeLower > lowBound)
               s.add(get(i));
        }
        return s;
    }

    public PuzzleSet startsAtPoint(int point)
    {
        PuzzleSet s = new PuzzleSet();
        for (int i=0; i<size(); i++)
        {
           if (get(i).rangeLower == point)
               s.add(get(i));
        }
        return s;
    }

    public double sum()
    {
        double sum = 0.0;
        for (int i=0; i<size(); i++)
            sum += get(i).price;
        return sum;
    }

    public String toString()
    {
        StringBuffer b = new StringBuffer();
        for (int i=0; i<size(); i++)
        {
            b.append(get(i).toString());
        }
        return b.toString();
    }
}

Answer 1

JSR-166Y旨在通过关注线程协调来促进Java
7中并行递归的实现。您可能会发现他们的讨论，代码和论文（尤其是Doug Lea的论文A Java Fork / Join
Framework）很有用。