blu*_*l2k 13 java concurrency multithreading
问题的背景:我正在尝试编写一个利用多核处理器和并行处理的拼图解算法.但是,理想/最简单的解决方案是简单的递归功能.
什么是分解解决方案以利用并行处理和递归函数的最佳方法？
下面的代码是一个简单的解谜算法的解决方案(它正常工作).这个例子中的谜题很简单 - 有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();
}
}
JSR-166Y旨在通过处理线程协调来简化Java 7中并行递归的实现.您可能会发现他们的讨论,代码和论文(特别是Doug Lea的论文A Java Fork/Join Framework)很有用.
问题的类型让我想起了遗传算法。您已经有了适应度函数（成本），并且问题的布局似乎适合交叉和变异。您可以使用可用的 GA 引擎之一并并行运行多个池/代。GA 倾向于很快找到好的解决方案，尽管不能保证找到绝对的最佳解决方案。另一方面，我相信您描述的难题无论如何都不一定有一个最佳解决方案。GA 解决方案通常用于日程安排（例如创建教师、教室和班级名册）。找到的解决方案通常是“稳健的”，因为通常可以通过最少的更改找到满足约束变化的合理解决方案。
至于并行化给定的递归算法。我最近为 n-Queens 问题尝试了这个（使用 Terracotta），并做了一些与您所描述的类似的事情。第一行皇后被放置在每个可能的列中以创建 n 个子问题。有一个工作线程池。作业调度程序检查池中是否有空闲的工作线程可用，并为其分配一个子问题。工作线程处理子问题，输出所有找到的解决方案，并返回空闲状态。因为通常工作线程比子问题少得多，所以如果子问题不花费相等的时间来解决也不是什么大问题。
我很想听听其他想法。