java - 使用递归函数进行并行编程？

Question

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

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

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

我尝试结合并行和递归的解决方案是下面使用的:为每个使用插槽 1 的部分创建一个任务，然后在任务中递归地查看其余部分，将它们插入剩余空间，同时最大化成本。这是最好的解决方案吗(可能不是，这就是我来这里的原因)。如何改进？使用并行/递归解决方案时还有其他好的建议吗？

虽然简单的递归在这里可以很好地工作，但我正在想象这个运行有 200 个插槽和 5000 block 的 Puzzle。

下面也是这个例子的解决方案:

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 )很有用。