具有无序终端操作的 Stream.skip 行为

我已经阅读了这个这个问题,但仍然怀疑观察到的行为是否是JDK作者的意图。Stream.skip

让我们有一个简单的数字1..20输入:

List<Integer> input = IntStream.rangeClosed(1, 20).boxed().collect(Collectors.toList());

现在,让我们创建一个并行流,以不同的方式组合 with 并收集结果:unordered()skip()

System.out.println("skip-skip-unordered-toList: "
        + input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .skip(1)
            .unordered()
            .collect(Collectors.toList()));
System.out.println("skip-unordered-skip-toList: "
        + input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .unordered()
            .skip(1)
            .collect(Collectors.toList()));
System.out.println("unordered-skip-skip-toList: "
        + input.parallelStream().filter(x -> x > 0)
            .unordered()
            .skip(1)
            .skip(1)
            .collect(Collectors.toList()));

过滤步骤在这里基本上没有任何作用,但为流引擎增加了更多的难度:现在它不知道输出的确切大小,因此关闭了一些优化。我有以下结果:

skip-skip-unordered-toList: [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
// absent values: 1, 2
skip-unordered-skip-toList: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20]
// absent values: 1, 15
unordered-skip-skip-toList: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20]
// absent values: 7, 18

结果完全没问题,一切都按预期工作。在第一种情况下,我要求跳过前两个元素,然后收集以不特定的顺序列出。在第二种情况下,我要求跳过第一个元素,然后变成无序并跳过另一个元素(我不在乎哪一个)。在第三种情况下,我首先进入无序模式,然后跳过两个任意元素。

让我们跳过一个元素,以无序模式收集到自定义集合。我们的定制系列将是:HashSet

System.out.println("skip-toCollection: "
        + input.parallelStream().filter(x -> x > 0)
        .skip(1)
        .unordered()
        .collect(Collectors.toCollection(HashSet::new)));

输出令人满意:

skip-toCollection: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
// 1 is skipped

所以一般来说,我希望只要流是有序的,就跳过第一个元素,否则它会跳过任意元素。skip()

但是,让我们使用等效的无序终端操作:collect(Collectors.toSet())

System.out.println("skip-toSet: "
        + input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .unordered()
            .collect(Collectors.toSet()));

现在输出是:

skip-toSet: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20]
// 13 is skipped

使用任何其他无序终端操作(如 、 、 等)可以实现相同的结果。在这种情况下,删除步骤不会更改任何内容。似乎虽然 step 正确地使流从当前操作开始无序,但无序终端操作使整个流从最开始无序,尽管这可能会影响使用的结果。这对我来说似乎完全具有误导性:我希望使用无序收集器与在终端操作之前将流转换为无序模式并使用等效的有序收集器相同。forEachfindAnyanyMatchunordered()unordered()skip()

所以我的问题是:

  1. 此行为是有意为之,还是 Bug?
  2. 如果是,它是否记录在某个地方?我读过 Stream.skip() 文档:它没有说任何关于无序终端操作的内容。此外,特征。未排序的文档不是很理解,并没有说整个流的排序将丢失。最后,包摘要中的“排序”部分也不涵盖这种情况。可能我错过了什么?
  3. 如果无序终端操作的目的是使整个流无序,为什么 step 只从这一点起就使它无序呢?我可以依赖此行为吗?或者我只是很幸运,我的第一个测试工作得很好?unordered()

答案 1

回想一标志(有序、排序、大小、不同)的目标是启用操作以避免执行不必要的工作。涉及流标志的优化示例包括:

  • 如果我们知道流已经排序,那么就是一个no-op;sorted()
  • 如果我们知道流的大小,我们可以在 中预先分配一个正确大小的数组,避免复制;toArray()
  • 如果我们知道输入没有有意义的遭遇顺序,我们不需要采取额外的步骤来保持遭遇顺序。

管道的每个阶段都有一组流标志。中间操作可以注入、保留或清除流标志。例如,过滤保留了排序性/独特性,但不保留了大小;映射保留大小,但不保留排序性或可区分性。排序注入排序性。中间操作的标志处理相当简单,因为所有决策都是本地的。

终端操作的标志处理更加微妙。ORDER 是与终端操作最相关的标志。如果终端操作是无序的,那么我们确实向后传播无序性。

我们为什么要这样做?好吧,考虑一下这个管道:

set.stream()
   .sorted()
   .forEach(System.out::println);

由于不受按顺序操作的限制,因此对列表进行排序的工作完全浪费了精力。因此,我们向后传播此信息(直到我们遇到短路操作,例如),以免失去此优化机会。同样,我们可以在无序流上使用 的优化实现。forEachlimitdistinct

此行为是有意为之,还是 Bug?

是 :)反向传播是有意的,因为它是一种有用的优化,不应产生不正确的结果。但是,bug部分是我们正在传播过去的前一个,我们不应该这样做。因此,无序标志的反向传播过于激进,这是一个错误。我们将发布一个错误。skip

如果是,它是否记录在某个地方?

它应该只是一个实现细节;如果它被正确实现,你不会注意到(除了你的流更快。


答案 2

@Ruben,你可能不明白我的问题。大致的问题是:为什么unordered().collect(toCollection(HashSet::new))的行为与collect(toSet())不同。当然,我知道 toSet() 是无序的。

也许,但是,无论如何,我会再试一次。

看看收集器的Javadocs toSet和toCollection,我们可以看到toSet提供了一个无序的收集器。

这是一个 {@link收集器。特征#无序无序} 收集器。

即,具有无序特征的收集器实例。看看 Collector.Features#UNORDERED 的 Javadoc,我们可以阅读:

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

在 Collector 的 Javadocs 中,我们还可以看到:

对于并发收集器,实现可以自由地(但不是必须)同时实现约简。并发减少是指使用同一个并发可修改的结果容器从多个线程并发调用累加器函数,而不是在累积期间隔离结果。仅当收集器具有 {@link 特征#UNORDERED} 特征或原始数据未排序时,才应应用并发约简

对我来说,这意味着,如果我们设置UNORDERED特征,我们根本不关心流的元素传递到累加器的顺序,因此,元素可以按任何顺序从管道中提取。

顺便说一句,如果您在示例中省略了无序(),您将获得相同的行为:

    System.out.println("skip-toSet: "
            + input.parallelStream().filter(x -> x > 0)
                .skip(1)
                .collect(Collectors.toSet()));

此外,Stream 中的 skip() 方法为我们提供了一个提示:

虽然 {@code skip()} 在顺序流管道上通常是一种廉价操作,但在有序并行管道上可能非常昂贵

使用无序流源(例如 {@link #generate(供应商)})或使用 {@link #unordered()} 删除排序约束可能会导致显著的加速

使用时

Collectors.toCollection(HashSet::new)

您正在创建一个正常的“有序”收集器(没有无序特征的收集器),对我来说意味着您确实关心排序,因此,元素被按顺序提取并且您获得了预期的行为。


推荐