您正在分叉的某些任务尝试使用相同的数组来评估不同的组合。您可以通过为每个任务创建一个不同的数组或将并行性限制为那些已经拥有自己的数组的任务（即具有不同长度的任务）来解决该问题。
但还有另一种可能；根本不要使用数组。您可以将组合存储到int值，作为每个int值是位的组合。这不仅节省了大量内存，而且您还可以通过仅增加值来轻松迭代所有可能的组合，因为迭代所有int数字还会迭代所有可能的位组合。我们唯一需要实现的是为特定的字符串生成正确的字符串int通过根据位的位置将位解释为数字来获取值。
对于第一次尝试，我们可以采取简单的方法并使用已经存在的类：
public static void main(String[] args) {
long t0 = System.nanoTime();
combinations(10, 25);
long t1 = System.nanoTime();
System.out.println((t1 - t0)/1_000_000+" ms");
System.out.flush();
}
static void combinations(int start, int end) {
for(int i = 1, stop = (1 << (end - start)) - 1; i <= stop; i++) {
System.out.println(
BitSet.valueOf(new long[]{i}).stream()
.mapToObj(b -> String.valueOf(b + start))
.collect(Collectors.joining(", ", "[", "]"))
);
}
}
该方法使用独占结束，因此对于您的示例，您必须像这样调用它combinations(0, 3)它会打印
[0]
[1]
[0, 1]
[2]
[0, 2]
[1, 2]
[0, 1, 2]
3 ms
of course, timing may vary
For the combinations(10, 25)上面的例子，它打印所有组合，然后是3477 ms在我的机器上。这听起来像是一个优化的机会，但我们应该首先考虑哪些操作会产生哪些成本。
在这里，组合的迭代已被简化为一个微不足道的操作。创建字符串的成本要高一个数量级。但这与实际打印相比仍然不算什么，实际打印包括将数据传输到操作系统，并且根据系统的不同，实际渲染可能会增加我们的时间。由于这是在持有锁的情况下完成的PrintStream，同时尝试打印的所有线程都将被阻止，从而使其成为不可并行的操作。
让我们通过创建一个新的来确定成本的比例PrintStream，禁用换行符上的自动刷新并使用一个非常大的缓冲区，能够保存整个输出：
public static void main(String[] args) {
System.setOut(new PrintStream(
new BufferedOutputStream(new FileOutputStream(FileDescriptor.out),1<<20),false));
long t0 = System.nanoTime();
combinations(10, 25);
long t1 = System.nanoTime();
System.out.flush();
long t2 = System.nanoTime();
System.out.println((t1 - t0)/1_000_000+" ms");
System.out.println((t2 - t0)/1_000_000+" ms");
System.out.flush();
}
static void combinations(int start, int end) {
for(int i = 1, stop = (1 << (end - start)) - 1; i <= stop; i++) {
System.out.println(
BitSet.valueOf(new long[]{i}).stream()
.mapToObj(b -> String.valueOf(b + start))
.collect(Collectors.joining(", ", "[", "]"))
);
}
}
在我的机器上，它按以下顺序打印一些内容
93 ms
3340 ms
显示代码在不可并行打印上花费了超过三秒的时间，而在计算上只花费了约 100 毫秒。为了完整起见，以下代码降低了一个级别String一代：
static void combinations(int start, int end) {
for(int i = 1, stop = (1 << (end - start)) - 1; i <= stop; i++) {
System.out.println(bits(i, start));
}
}
static String bits(int bits, int offset) {
StringBuilder sb = new StringBuilder().append('[');
for(;;) {
int bit = Integer.lowestOneBit(bits), num = Integer.numberOfTrailingZeros(bit);
sb.append(num + offset);
bits -= bit;
if(bits == 0) break;
sb.append(", ");
}
return sb.append(']').toString();
}
这使我的机器上的计算时间减半，同时对总时间没有明显影响，现在这应该不足为奇。
但出于教育目的，忽略潜在加速的缺乏，让我们讨论如何并行化此操作。
顺序代码确实已经将任务转化为一种形式，该形式可以归结为从起始值到最终值的迭代。现在，我们将这段代码重写为ForkJoinTask（或合适的子类）表示具有开始值和结束值的迭代。然后，我们通过在中间分割范围来添加将此操作分割为两个的功能，这样我们就可以在范围的每一半上迭代两个任务。可以重复此操作，直到我们决定有足够的潜在并行作业并在本地执行当前迭代。在本地处理之后，我们必须等待我们拆分的任何任务的完成，以确保根任务的完成意味着所有子任务的完成。
public class Combinations extends RecursiveAction {
public static void main(String[] args) {
System.setOut(new PrintStream(new BufferedOutputStream(
new FileOutputStream(FileDescriptor.out),1<<20),false));
ForkJoinPool pool = (ForkJoinPool) Executors.newWorkStealingPool();
long t0 = System.nanoTime();
Combinations job = Combinations.get(10, 25);
pool.execute(job);
job.join();
long t1 = System.nanoTime();
System.out.flush();
long t2 = System.nanoTime();
System.out.println((t1 - t0)/1_000_000+" ms");
System.out.println((t2 - t0)/1_000_000+" ms");
System.out.flush();
}
public static Combinations get(int min, int max) {
return new Combinations(min, 1, (1 << (max - min)) - 1);
}
final int offset, from;
int to;
private Combinations(int offset, int from, int to) {
this.offset = offset;
this.from = from;
this.to = to;
}
@Override
protected void compute() {
ArrayDeque<Combinations> spawned = new ArrayDeque<>();
while(getSurplusQueuedTaskCount() < 2) {
int middle = (from + to) >>> 1;
if(middle == from) break;
Combinations forked = new Combinations(offset, middle, to);
forked.fork();
spawned.addLast(forked);
to = middle - 1;
}
performLocal();
for(;;) {
Combinations forked = spawned.pollLast();
if(forked == null) break;
if(forked.tryUnfork()) forked.performLocal(); else forked.join();
}
}
private void performLocal() {
for(int i = from, stop = to; i <= stop; i++) {
System.out.println(bits(i, offset));
}
}
static String bits(int bits, int offset) {
StringBuilder sb = new StringBuilder().append('[');
for(;;) {
int bit=Integer.lowestOneBit(bits), num=Integer.numberOfTrailingZeros(bit);
sb.append(num + offset);
bits -= bit;
if(bits == 0) break;
sb.append(", ");
}
return sb.append(']').toString();
}
}
The getSurplusQueuedTaskCount()为我们提供了有关工作线程饱和度的提示，换句话说，分叉更多作业是否可能有益。将返回的数字与阈值进行比较，该阈值通常是一个小数字，作业越异构，因此预期的工作负载，阈值就应该越高，以在作业比其他作业更早完成时允许更多的工作窃取。在我们的例子中，工作量预计会非常平衡。
分裂的方式有两种。示例通常创建两个或多个分叉子任务，然后将它们连接起来。这可能会导致大量任务只是等待其他任务。另一种方法是分叉子任务并更改当前任务，以代表另一个任务。这里，分叉任务代表[middle, to]范围，而当前任务被修改为代表[from, middle] range.
分叉足够多的任务后，剩余范围将在当前线程中本地处理。然后，该任务将等待所有分叉的子任务，并进行一项优化：try to unfork子任务，如果还没有其他工作线程窃取它们，则在本地处理它们。
这工作顺利，但不幸的是，正如预期的那样，它并没有加速操作，因为最昂贵的部分是打印。
1 使用int表示所有组合将支持的范围长度减少到 31，但请记住，这样的范围长度意味着2³¹ - 1组合，需要迭代很多。如果这仍然是一个限制，您可以更改代码以使用long反而。当时支持的范围长度为 63，换句话说2⁶³ - 1组合，足以让计算机一直忙碌到宇宙的尽头。
