无法多线程一个可扩展的方法 [英] Unable to multi-thread a scalable method
问题描述
更新：为了澄清我在问什么我已经发布了一个小的Java code横跨有想法
前段时间我问了一个<一个href="http://stackoverflow.com/questions/7265576/can-brute-force-algorithms-scale/7265593#7265593">question如何获得一个算法，打破了一组数字，当时的想法是给它一个数字列表（1,2,3,4,5）和总（ 10 ），它会找出每个号码的所有倍数，多达会增加总（1·10或 1 * 1,1 * 2,1 * 3,1 * 4 或 2 * 5 等）。这是我这辈子就这样，我花了一段时间的第一个编程练习，我得到了它的工作，但现在我想试试，看看我是否可以扩展它。该人在原来的问题说，这是可扩展的，但我有点困惑，在如何做到这一点。递归部分是我卡在扩展，结合所有的结果部分的区域（该表是指不具备可伸缩性，但申请缓存我能使其快速）
我有以下的算法（伪code）：
//生成表
对于i = 1至k
针对z = 0总结：
对于C = 1到z / x_i：
如果T [Z - C * x_i] [我 - 1]是正确的：
设置T [Z] [I]为真
//使用表把所有的部分组合在一起
功能RecursivelyListAllThatWork（K，和）//使用最后K个变量，使之和
/ *基例：如果我们正确地分配所有的变量，列出此
* 解。
* /
如果k == 0：
打印的内容我们至今
返回
/ *递归步骤：尝试所有系数，但前提是他们的工作。 * /
对于C = 0总结/ x_k：
如果T [总和 - C * x_k] [K - 1]是正确的：
纪念x_k系数为c
调用RecursivelyListAllThatWork（K - 1，总和 - C * x_k）
取消标记x_k系数
我真的很茫然，在如何线程/多进程的RecursivelyListAllThatWork功能。我知道，如果我发送一个较小的K（这是int类型列表中的项目总数的），它会处理该子集，但我不知道该怎么做的人，结合跨子集的结果。例如，如果列表是 [1,2,3,4,5,6,7,8,9,10] ，我把它K = 3，那么只有1,2,3得到处理这是好的，但怎么样，如果我需要的结果，包括1和10？我试图修改表（变量T），所以只有我想在那里，但仍然无法正常工作，因为，像上面的解决方案，它的一个子集，但无法处理，需要更广泛的答案的一部分。
我不需要任何code只是如果有人能解释如何从概念上突破，以使其他核心/机器可以用这个递归步骤。
更新：我仍似乎无法弄清楚如何把RecursivelyListAllThatWork成一个可运行的（我知道在技术上如何做到这一点，但我不知道如何改变RecursivelyListAllThatWork算法，因此它可以运行在平行。其他的部分就在这里，使这个例子的工作，我只需要实现可运行在RecursivelyListAllThatWork法）。下面是java的code：
进口java.awt.Point中;
进口的java.util.ArrayList;
进口java.util.Arrays中;
进口的java.util.List;
公共类主
{
公共静态无效的主要（字串[] args）
{
的System.out.println（开始..）;
INT target_sum = 100;
INT []数据=新INT [] {10，5，50，20，25，40};
名单T = tableGeneator（target_sum，数据）;
名单＆LT;整数GT; COEFF = create_coeff（data.length）;
RecursivelyListAllThatWork（data.length，target_sum，T，COEFF，数据）;
}
私有静态列表＆LT;整数GT; create_coeff（int i）以{
// TODO自动生成方法存根
整数[]整数=新的整数[I]
Arrays.fill（整数，0）;
名单＆LT;整数GT; integerList = Arrays.asList（整数）;
返回integerList;
}
私有静态无效RecursivelyListAllThatWork（INT K，INT总和，列表T，名单，其中，整数GT; COEFF，INT []数据）{
// TODO自动生成方法存根
如果（K == 0）{
//＃打印什么我们至今
的for（int i = 0; I＆LT; coeff.size（）;我++）{
的System.out.println（数据[I] +=+ coeff.get（ⅰ））;
}
的System.out.println（*******************）;
返回;
}
整数x_k =数据[K-1];
//递归步骤：尝试所有系数，但前提是他们的工作。
对于（INT C = 0; C＆LT; = SUM / x_k; C ++）{//变量C帽的百分比
如果（T.contains（新点（（总和 - C * x_k），（K-1））））
{
//纪念x_k系数为c
coeff.set（（K-1）中，c）;
RecursivelyListAllThatWork（（K - 1），（和 - C * x_k），T，COEFF，数据）;
x_k的//取消标记系数
coeff.set（（K-1），0）;
}
}
}
公共静态列表tableGeneator（INT target_sum，INT []数据）{
名单T =新的ArrayList（）;
T.add（新点（0,0））;
浮动最大百分比= 1;
INT R =（INT）（target_sum *最大百分比* data.length）;
的for（int i = 0; I＆LT; data.length;我++）
{
对于（int类型= -R; S＆LT; R + 1; S ++）
{
INT MAX_VALUE =（INT）Math.abs（（target_sum *最大百分比）
/数据[I]）;
对于（INT C = 0;℃下MAX_VALUE + 1; C ++）
{
如果（T.contains（新点（S - C *数据[I]，I）））
{
点P =新的点（S，I + 1）;
如果（！T.contains（P））
{
T.add（对）;
}
}
}
}
}
返回笔;
}
}
一般的答案多线程是去recursivate一个递归实现得益于栈（LIFO或FIFO）。当实现这样的算法，线程的数量是用于所述算法（芯例如数）的固定参数。
要实现它，语言调用堆栈被替换堆栈存储最后上下文检查点时，被测试的条件结束递归。在你的情况下，它可以是 K = 0 或 COEFF 值配衬有针对性的总和。
在去recursivation，第一个实现是运行多个线程消耗堆栈，但堆栈连接成为一个争论点，因为它可能需要同步。
有一个更好的可扩展性的解决方案是专用的堆栈为每个线程，但环境中的堆栈是必需的初始生产。
我建议与第一线程工作递归为有限数量的混合方法 K 为最大递归深度：2的小的数据的例子中设置的，但我如果大推荐3。然后，第一部分代表所产生的中间上下文来将处理剩下的 K 与非递归实现线程池。这code不是基于复杂的算法，您使用，但在一个相当基本执行：
进口java.util.Arrays中;
进口java.util.ArrayDeque;
进口java.util.Queue中;
进口java.util.concurrent.ConcurrentLinkedQueue中;
进口java.util.concurrent.LinkedBlockingDeque中;
进口java.util.concurrent.Callable;
进口java.util.concurrent.ExecutorService中;
进口java.util.concurrent.ThreadPoolExecutor中;
进口java.util.concurrent.TimeUnit中;
公共类MixedParallel
{
// pre-条件：排序的值！
私有静态最终诠释[]数据=新的INT [] {5，10，20，25，40，50};
//上下文来存储中间计算或解决方案
静态类上下文{
INT K表;
INT总和;
INT [] COEFF;
上下文（INT K，INT总和，INT [] COEFF）{
this.k = K;
this.sum =总和;
this.coeff = COEFF;
}
}
//并行执行线程池
私有静态ExecutorService的执行者;
//队列收集解决方案
私有静态队列＆LT;语境GT;解决方案;
静态{
最终诠释numberOfThreads = 2;
遗嘱执行人=
新的ThreadPoolExecutor（numberOfThreads，numberOfThreads，1000，TimeUnit.SECONDS，
新LinkedBlockingDeque＆其中;可运行＆GT;（））;
//由于多线程插入的并发
解决方案=新的ConcurrentLinkedQueue＆LT;语境＆GT;（）;
}
公共静态无效的主要（字串[] args）
{
INT target_sum = 100;
//结果向量，初始化为0
INT [] COEFF =新INT [data.length]
Arrays.fill（COEFF，0）;
mixedPartialSum（data.length - 1，target_sum，COEFF）;
executor.shutdown（）;
//的System.out.println（在倾销的结果。）;
而（！solutions.isEmpty（））{
语境S = solutions.poll（）;
printResult（s.coeff）;
}
}
私有静态无效printResult（INT [] COEFF）{
StringBuffer的SB =新的StringBuffer（）;
的for（int i = coeff.length - 1; I＆GT; = 0;我 - ）{
如果（COEFF [I] 0）{
。sb.append（数据[I]）追加（*）.append（COEFF [I]）追加（）。
}
}
的System.out.println（sb.append（从）.append（Thread.currentThread（）））;
}
私有静态无效mixedPartialSum（INT K，INT总和，INT [] COEFF）{
INT x_k =数据[K]
对于（INT C =总和/ x_k; C＆GT; = 0; C--）{
COEFF [K] = C;
INT [] newcoeff = Arrays.copyOf（COEFF，coeff.length）;
如果（C * x_k ==总和）{
// printResult（newcoeff）;
solutions.add（新的上下文（0，0，newcoeff））;
继续;
}否则如果（K＆0）{
如果（data.length - K 2）{
mixedPartialSum（K - 1，总和 - C * x_k，newcoeff）;
// for循环的C继续使用previous COEFF内容
} 其他 {
//不再递归。授人以线程池
executor.submit（新ComputePartialSum（新语境（K - 1，总和 - C * x_k，newcoeff）））;
}
}
}
}
静态类ComputePartialSum实现可赎回＆LT;太虚＆GT; {
//队列上下文处理
专用队列和LT;语境GT;环境;
ComputePartialSum（上下文请求）{
上下文=新ArrayDeque＆LT;语境＆GT;（）;
contexts.add（要求）;
}
公共无效调用（）{
而（！contexts.isEmpty（））{
上下文电流= contexts.poll（）;
INT x_k =数据[current.k]
对于（INT C = current.sum / x_k; C＆GT; = 0; C--）{
current.coeff [current.k] = C;
INT [] newcoeff = Arrays.copyOf（current.coeff，current.coeff.length）;
如果（C * x_k == current.sum）{
// printResult（newcoeff）;
solutions.add（新的上下文（0，0，newcoeff））;
继续;
}否则如果（current.k大于0）{
contexts.add（新上下文（current.k - 1，current.sum - C * x_k，newcoeff））;
}
}
}
返回null;
}
}
}
您可以检查哪些线程发现输出结果，并检查所有的involed：在递归模式的主线程，并从上下文堆栈模式池中的两个线程
。现在该实现的可扩展性，当 data.length 高：
- 最大递归深度在低水平限于主线程
- 从池中的每个线程都拥有自己的上下文堆栈不争别人
- 的参数调整现在
numberOfThreads和maxRecursionDepth
因此，答案是肯定的，你的算法可以并行。这是根据你的code完全递归实现：
进口java.awt.Point中;
进口的java.util.ArrayList;
进口java.util.Arrays中;
进口的java.util.List;
进口java.util.ArrayDeque;
进口java.util.Queue中;
进口java.util.concurrent.ConcurrentLinkedQueue中;
进口java.util.concurrent.LinkedBlockingDeque中;
进口java.util.concurrent.Callable;
进口java.util.concurrent.ExecutorService中;
进口java.util.concurrent.ThreadPoolExecutor中;
进口java.util.concurrent.TimeUnit中;
公共类OriginalParallel
{
静态最终诠释numberOfThreads = 2;
静态最终诠释maxRecursionDepth = 3;
公共静态无效的主要（字串[] args）
{
INT target_sum = 100;
INT []数据=新INT [] {50，40，25，20，10，5};
名单T = tableGeneator（target_sum，数据）;
INT [] COEFF =新INT [data.length]
Arrays.fill（COEFF，0）;
RecursivelyListAllThatWork（data.length，target_sum，T，COEFF，数据）;
executor.shutdown（）;
}
私有静态无效printResult（INT [] COEFF，INT []数据）{
StringBuffer的SB =新的StringBuffer（）;
的for（int i = coeff.length - 1; I＆GT; = 0;我 - ）{
如果（COEFF [I] 0）{
。sb.append（数据[I]）追加（*）.append（COEFF [I]）追加（）。
}
}
的System.out.println（sb.append（从）.append（Thread.currentThread（）））;
}
//并行执行线程池
私有静态ExecutorService的执行者;
静态{
遗嘱执行人=
新的ThreadPoolExecutor（numberOfThreads，numberOfThreads，1000，TimeUnit.SECONDS，
新LinkedBlockingDeque＆其中;可运行＆GT;（））;
}
私有静态无效RecursivelyListAllThatWork（INT K，INT总和，列表T，INT [] COEFF，INT []数据）{
如果（K == 0）{
printResult（COEFF，数据）;
返回;
}
整数x_k =数据[K-1];
//递归步骤：尝试所有系数，但前提是他们的工作。
对于（INT C = 0; C＆LT; = SUM / x_k; C ++）{//变量C帽的百分比
如果（T.contains（新点（（总和 - C * x_k），（K-1））））{
//纪念x_k系数为c
COEFF [K-1] = C;
如果（data.length - ！K = maxRecursionDepth）{
RecursivelyListAllThatWork（（K - 1），（和 - C * x_k），T，COEFF，数据）;
} 其他 {
//代表达成深度3时，线程池
INT [] newcoeff = Arrays.copyOf（COEFF，coeff.length）;
executor.submit（新RecursiveThread（K - 1，总和 - C * x_k，T，newcoeff，数据））;
}
x_k的//取消标记系数
COEFF [K-1] = 0;
}
}
}
静态类RecursiveThread实现可赎回＆LT;太虚＆GT; {
INT K表;
INT总和;
INT [] COEFF;
INT []的数据;
表笔;
RecursiveThread（INT K，INT总和，列表T，INT [] COEFF，INT []数据）{
this.k = K;
this.sum =总和;
this.T = T;
this.coeff = COEFF;
this.data =数据;
的System.out.println（对于k新的工作=+ K）;
}
公共无效调用（）{
RecursivelyListAllThatWork（K，总之，T，COEFF，数据）;
返回null;
}
}
公共静态列表tableGeneator（INT target_sum，INT []数据）{
名单T =新的ArrayList（）;
T.add（新点（0,0））;
浮动最大百分比= 1;
INT R =（INT）（target_sum *最大百分比* data.length）;
的for（int i = 0; I＆LT; data.length;我++）{
对于（int类型= -R; S＆LT; R + 1; S ++）{
INT MAX_VALUE =（INT）Math.abs（（target_sum *最大百分比）/数据[I]）;
对于（INT C = 0;℃下MAX_VALUE + 1; C ++）{
如果（T.contains（新点（S - C *数据[I]，I）））{
点P =新的点（S，I + 1）;
如果（！T.contains（P））{
T.add（对）;
}
}
}
}
}
返回笔;
}
}
UPDATE: To help clarify what I'm asking I have posted a little java code that gets the idea across.
A while ago I asked a question on how to get an algorithm to break down a set of numbers, the idea was to give it a list of numbers (1,2,3,4,5) and a total(10) and it would figure out all the multiples of each number that would add up to the total('1*10' or '1*1,1*2,1*3,1*4' or '2*5',etc..). It was the first programming exercise I ever did so it took me a while and I got it working but now I want to try to see if I can scale it. The person in the original question said it was scalable but I'm a bit confused at how to do it. The recursive part is the area I'm stuck at scaling the part that combines all the results(the table it is referring to is not scalable but applying caching I am able to make it fast)
I have the following algorithm(pseudo code):
//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
I'm really at a loss at how to thread/multiprocess the RecursivelyListAllThatWork function. I know if I send it a smaller K( which is int of total number of items in list) it will process that subset but I don't know how to do ones that combine results across the subset. For example, if list is [1,2,3,4,5,6,7,8,9,10] and I send it K=3 then only the 1,2,3 get processed which is fine but what about if I need results that include 1 and 10? I have tried to modify the table(variable T) so only the subset I want are there but still doesn't work because, like the solution above, it does a subset but cannot process answers that require a wider range.
I don't need any code just if someone can explain how to conceptually break this recursive step to so other cores/machines can be used.
UPDATE: I still can't seem to figure out how to turn RecursivelyListAllThatWork into a runnable(I know technically how to do it, but I don't understand how to change the RecursivelyListAllThatWork algorithm so it can be ran in parallel. The other parts are just here to make the example work, I only need to implement runnable on RecursivelyListAllThatWork method). Here's the java code:
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;
}
}
The general answer to multi-threading is to de-recursivate a recursive implementation thanks to a stack (LIFO or FIFO). When implementing such an algorithm, the number of threads is a fixed parameter for the algorithm (number of cores for instance).
To implement it, the language call stack is replaced by a stack storing last context as a checkpoint when the tested condition ends the recursivity. In your case it is either k=0 or coeff values matchs targeted sum.
After de-recursivation, a first implementation is to run multiple threads to consume the stack BUT the stack access becomes a contention point because it may require synchronization.
A better scalable solution is to dedicate a stack for each thread but an initial production of contexts in the stack is required.
I propose a mix approach with a first thread working recursively for a limited number of k as a maximum recursion depth: 2 for the small data set in example, but I recommend 3 if larger. Then this first part delegates the generated intermediate contexts to a pool of threads which will process remaining k with a non-recursive implementation. This code is not based on the complex algorithm you use but on a rather "basic" implementation:
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;
}
}
}
You can check which thread has found outputted result and check all are involed: the main thread in recursive mode and the two thread from the pool in context stack mode.
Now this implementation is scalable when data.length is high:
- the maximum recursion depth is limited to the main thread at a low level
- each thread from the pool works with its own context stack without contention with others
- the parameters to tune now are
numberOfThreadsandmaxRecursionDepth
So the answer is yes, your algorithm can be parallelized. Here is a fully recursive implementation based on your code:
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;
}
}
这篇关于无法多线程一个可扩展的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
