12

我知道在设置并行处理时存在开销，Stream如果项目很少或每个项目的处理速度很快，单线程中的处理速度会更快。

但是，是否有类似的阈值trySplit()，将问题分解成更小的块会适得其反？我通过类比来思考合并排序切换到最小块的插入排序。

如果是这样，阈值是否取决于在过程中的相对成本trySplit()和消费项目tryAdvance()？考虑一个比推进数组索引复杂得多的拆分操作——例如拆分一个按词法排序的多集排列。是否有约定让客户端在创建并行流时根据其使用者的复杂性指定拆分的下限？Spliterator可以用来估计下限本身的启发式方法吗？

或者，让 a 的下限为Spliterator1 并让工作窃取算法负责选择是否继续拆分是否总是安全的？

4

1 回答 1

5

一般来说，您不知道传递给tryAdvanceor的消费者完成了多少工作forEachRemaining。流管道和 FJP 都不知道这一点，因为它取决于用户提供的代码。它可以比拆分过程快得多或慢得多。例如，您可能有两个元素的输入，但每个元素的处理需要一个小时，因此拆分此输入是非常合理的。

我通常尽可能多地拆分输入。可以使用三个技巧来改进拆分：

  1. 如果很难平均拆分，但您可以跟踪（或至少粗略估计）每个子部分的大小，请随意拆分不均匀。流实现将对更大的部分进行更多的进一步拆分。不要忘记SIZED和SUBSIZED特点。

  2. 将拆分的困难部分移至下一个tryAdvance/forEachRemaining调用。例如，假设您有已知数量的排列，并且trySplit您将跳到其他排列。像这样的东西：

    public class MySpliterator implements Spliterator<String> {
    private long position;
    private String currentPermutation;
    private final long limit;

    MySpliterator(long position, long limit, String currentPermutation) {
        this.position = position;
        this.limit = limit;
        this.currentPermutation = currentPermutation;
    }

    @Override
    public Spliterator<String> trySplit() {
        if(limit - position <= 1)
            return null;
        long newPosition = (position+limit)>>>1;
        Spliterator<String> prefix = 
                 new MySpliterator(position, newPosition, currentPermutation);
        this.position = newPosition;
        this.currentPermutation = calculatePermutation(newPosition); // hard part
        return prefix;
    }

    ...
}

    将困难的部分移至下一个tryAdvance调用，如下所示：

    @Override
public Spliterator<String> trySplit() {
    if(limit - position <= 1)
        return null;
    long newPosition = (position+limit)>>>1;
    Spliterator<String> prefix = 
             new MySpliterator(position, newPosition, currentPermutation);
    this.position = newPosition;
    this.currentPermutation = null;
    return prefix;
}

@Override
public boolean tryAdvance(Consumer<? super String> action) {
    if(currentPermutation == null)
        currentPermutation = calculatePermutation(position); // hard part
    ...
}

    这样，硬部分也将与前缀处理并行执行。

  3. 如果当前拆分器中剩下的元素不多（例如，少于 10 个）并且已请求拆分，那么最好将一半的元素收集到数组中，然后创建一个基于数组的拆分器这个前缀（类似于它在 中的做法AbstractSpliterator.trySplit()）。在这里您可以控制所有代码，因此您可以提前测量正常trySplit的速度比tryAdvance何时应该切换到基于数组的拆分慢并估计阈值。

于 2015-08-17T08:37:22.817 回答