使用递归函数进行并行编程？ [英] Parallel Programming With Recursive Functions?
问题描述
问题的背景：我正在尝试编写一个利用多核处理器和并行处理的拼图解算法。但是，理想/最简单的解决方案是简单的递归功能。
Background of the Problem: I'm trying to write a puzzle solution algorithm that takes advantage of multi-core processors and parallel processing. However, the ideal/easiest solution is a simple recursive function.
分解解决方案的最佳方法是利用并行处理 AND 递归函数？
What's the best way to break down the solution to both take advantage of parallel processing AND the recursive function?
下面的代码是一个简单的解谜算法的解决方案（它可以正常工作）。这个例子中的谜题很简单 - 有14个插槽编号为1-14。每个拼图都有一个唯一的ID，一个范围告诉你它可以在哪里开始和停止（例如6-8意味着只适合插槽6-8）和价格。该算法试图找到最大化解决方案价格的解决方案。只有1个可以占用一个插槽，空插槽是可以接受的。解决方案会告诉您使用了哪些部件以及总成本。 （为了简单起见，还要假设插槽1必须填充）。
The code below is a solution for a simple puzzle solving algorithm (it works correctly). The puzzle in this example is straightforward - there are 14 slots numbered 1-14. Each puzzle piece has a unique ID, a range that tells you where it can start and stop (e.g. 6-8 means it only fits in slots 6-8), and a price. The algorithm attempts to find the solution that maximizes the price of the solution. Only 1 piece can occupy a slot, and empty slots are acceptable. The solution would tell you which pieces are used and the total cost. (To keep things simple, assume also that slot 1 MUST be filled).
我尝试的并行和递归组合解决方案如下所示：为每个创建一个Task使用插槽1，然后在任务内递归查看其余部分，将它们插入剩余空间，同时最大化成本。这是最好的解决方案（可能不是，这就是为什么我在这里）。怎么改进？使用并行/递归解决方案时还有其他好的建议吗？
My attempted solution to combine parallelism and recursion is what is used below: create a Task for each piece that uses slot 1, then within the Task recursively look through the rest of the pieces, slotting them into the remaining spaces while maximizing the cost. Is this the best solution (probably not, which is why I'm here). How can it be improved? Any other good recommendations when using parallel/recursive solutions?
虽然简单的递归在这里运行良好，但我想象一下这个有200个插槽和5000个拼图的拼图。
While the simple recursion would work well here, I'm picturing this running with a Puzzle that has 200 slots and 5000 pieces.
以下是此示例的解决方案：
Here's the solution to this example as well:
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();
}
}
推荐答案
< a href =http://artisans-serverintellect-com.si-eioswww6.com/default.asp?W9\"rel =noreferrer> JSR-166Y 旨在简化Java中并行递归的实现7通过照顾线程协调。您可以找到他们的讨论，代码和论文（特别是Doug Lea的论文 Java Fork /加入框架）很有用。
JSR-166Y is intended to facilate the implementation of parallel recursion in Java 7 by taking care of thread coordination. You may find their discussions, code, and papers (especially Doug Lea's paper A Java Fork/Join Framework) useful.
这篇关于使用递归函数进行并行编程？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
