Java 8 Collector UNORDERED特性是什么意思？

Question

在官方文档中,您可以阅读:

UNORDERED 指示集合操作不承诺保留输入元素的遭遇顺序.

没有任何例子,这没有太大帮助.

我的问题是,UNORDERED特征究竟意味着什么？我应该使用减少收集器,如min或sum,还是只适用于收集器？

在OpenJDK看起来像减少操作(min,sum,avg)具有空特征.我预计至少发现有CONCURRENT和UNORDERED.

Answer 1

在没有特殊请求的情况下,流操作必须表现得就像在源的遭遇顺序中处理元素一样.对于某些操作 - 例如使用关联操作进行简化 - 可以遵守此约束并仍然可以获得有效的并行执行.但是对于其他人来说,这种约束是非常有限的.并且,对于某些问题,此约束对用户没有意义.考虑以下流管道:

people.stream()
      .collect(groupingBy(Person::getLastName, 
                          mapping(Person::getFirstName));

与"Smith"关联的名字列表按照它们出现在初始流中的顺序出现在地图中是否重要？对于某些问题,是的,对于某些问题 - 我们不希望流库为我们猜测.一个有序的收集器说,可以将一个名字插入到列表中,其顺序与Smith姓氏人在输入源中出现的顺序不一致.通过放宽此约束,有时(并非总是),流库可以提供更高效的执行.

例如,如果您不关心此订单保留,则可以将其执行为:

people.parallelStream()
      .collect(groupingByConcurrent(Person::getLastName, 
                                    mapping(Person::getFirstName));

并发收集器是无序的,这允许优化共享底层ConcurrentMap,而不是具有O(log n)映射合并步骤.放宽排序约束可以实现真正的算法优势 - 但我们不能假设约束无关紧要,我们需要用户告诉我们这一点.使用UNORDERED收集器是告诉流库这些优化是公平游戏的一种方法.

Answer 2

UNORDERED 实质上意味着收集器既是关联的(规范要求)又可交换的(不是必需的).

关联性允许将计算分成子部分,然后将它们组合成完整的结果,但需要严格排序组合步骤.从文档中检查此代码段:

 A a2 = supplier.get();
 accumulator.accept(a2, t1);
 A a3 = supplier.get();
 accumulator.accept(a3, t2);
 R r2 = finisher.apply(combiner.apply(a2, a3));  // result with splitting

在最后一步中,combiner.apply(a2, a3)参数必须以此顺序出现,这意味着整个计算管道必须跟踪顺序并最终尊重它.

另一种说法是,必须对从递归拆分中获得的树进行排序.

另一方面,如果组合操作是可交换的,我们可以将任何子部分与任何其他子部分组合,而不是特定的顺序,并且总是获得相同的结果.显然,这会在空间和时间方面带来许多优化机会.

应该注意的是UNORDERED,JDK 中有收集器不能保证交换性.主要类别是由其他下游收集者组成的"高阶"收藏家,但他们不对其强制执行UNORDERED财产.