Java 8 个流的确定性

Question

动机

我刚刚重写了大约 30 个主要是微不足道的解析器，我需要新版本的行为与旧版本完全一样。因此，我存储了他们的示例输入文件和旧解析器生成的输出的一些签名，以便与新解析器进行比较。此签名包含成功解析项目的计数、一些哈希码的总和以及最多 10 个伪随机选择的项目。

我认为这是个好主意，因为哈希码总和的相等性在某种程度上保证了输出完全相同，样本让我可以看到问题所在。我只使用样本，否则它会变得非常大。

问题

基本上，给定一个无序的字符串集合，我想得到一个最多包含 10 个字符串的列表，这样当集合稍有变化时，我仍然会在相同的位置（输入是无序的，但输出是一个列表）。当缺少某些东西时，这也应该起作用，所以像取第 100 个最小元素这样的想法不起作用。

ImmutableList<String> selectSome(Collection<String> list) {
        if (list.isEmpty()) return ImmutableList.of();
        return IntStream.range(1, 20)
            .mapToObj(seed -> selectOne(list, seed))
            .distinct()
            .limit(10)
            .collect(ImmutableList.toImmutableList());
    }

所以我从 1 到 20 的数字开始（这样在 distinct 之后我仍然很可能有 10 个样本），调用无状态确定性函数 selectOne（定义如下）返回一个字符串根据一些有趣的标准，这是最大的，删除重复项，限制结果并使用番石榴收集它。所有步骤都应该是恕我直言的确定性和 "ordered"，但我可能忽略了一些东西。另一种可能性是我所有的 30 个新解析器都是错误的，但考虑到哈希是正确的，这是不可能的。而且，解析的结果看起来是正确的。

String selectOne(Collection<String> list, int seed) {
    // some boring mixing, definitely deterministic
    for (int i=0; i<10; ++i) {
        seed *= 123456789;
        seed = Integer.rotateLeft(seed, 16);
    }
    // ensure seed is odd
    seed = 2*seed + 1;

    // first element is the candidate result
    String result = list.iterator().next();
    // the value is the hash code multiplied by the seed
    // overflow is fine
    int value = seed * result.hashCode();

    // looking for s maximizing seed * s.hashCode()
    for (final String s : list) {
        final int v = seed * s.hashCode();
        if (v < value) continue;
        // tiebreaking by taking the bigger or smaller s
        // this is needed for determinism
        if (s.compareTo(result) * seed < 0) continue;
        result = s;
        value = v;
    }
    return result;
}

这个采样似乎不起作用。我得到一个像

这样的序列

"9224000", "9225000", "4165000", "9200000", "7923000", "8806000", ...

使用一个旧的解析器和

"9224000", "9225000", "4165000", "3030000", "1731000", "8806000", ...

有了新的。这两个结果都是完全可重复的。对于其他解析器，它看起来非常相似。

我对流的使用有误吗？我必须添加 .sequential() 或类似的吗？

更新

对输入集合进行排序已解决问题：

ImmutableList<String> selectSome(Collection<String> collection) {
    final List<String> list = Lists.newArrayList(collection);
    Collections.sort(list);
    .... as before
}

仍然缺少的是原因的解释。

解释

正如答案中所述，我的决胜局是一个全能决胜局，因为我没有检查平局。像

if (v==value && s.compareTo(result) < 0) continue;

工作正常。

我希望我的困惑问题至少对寻找 "consistent sampling" 的人有用。 这与 Java 8 无关。

我应该使用 Guava ComparisonChain 或更好的 Java 8 arg max 来避免我的愚蠢错误：

String selectOne(Collection<String> list, int seed) {
    .... as before
    final int multiplier = 2*seed + 1;
    return list.stream()
          .max(Comparator.comparingInt(s -> multiplier * s.hashCode())
          .thenComparing(s -> s)) // <--- FOOL-PROOF TIEBREAKER
          .get();
}

Answer 1

在 selectOne 中，您只想 select String s 给定 seed.

的最高排名 value = seed * s.hashCode();

问题出在 "tiebreaking" 行： if (s.compareTo(result) * seed < 0) continue;

它不是确定性的 - 对于不同的元素顺序，它会忽略不同的元素而不进行检查，因此改变元素的顺序会改变结果。

删除平局if，结果将对输入列表中元素的顺序不敏感。

Answer 2

错误在于你的决胜局实际上并不是打破平局。我们应该在 v > value 时选择 s，但我们会退回到 compareTo()。这打破了比较对称性，使您的算法依赖于遇到顺序。

作为奖励，这里有一个重现错误的简单测试用例：

System.out.println(selectOne(Arrays.asList("1", "2"), 4));  // 1
System.out.println(selectOne(Arrays.asList("2", "1"), 4));  // 2

Java 8 个流的确定性

Determinism of Java 8 streams

java

java-8

java-stream

deterministic

动机

问题

更新

解释