确定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(在下面定义),根据一些有趣的标准返回一个最大的字符串,删除重复项,限制结果并使用番石榴收集它.所有步骤应该是恕我直言确定性和"有序",但我可能忽略了一些东西.另一种可能性是我的所有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;

工作良好.

我希望我困惑的问题对于寻找"一致采样"的人来说至少是有用的.它与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

错误的是你的决胜局实际上没有打破平局.我们应该选择s何时v > value,但我们会回归compareTo().这打破了比较对称性,使您的算法依赖于遭遇顺序.

作为奖励,这是一个重现错误的简单测试用例:

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

Answer 2

在selectOne你只想选择给定的String s最大等级.value = seed * s.hashCode();seed

问题在于"抢劫"线: if (s.compareTo(result) * seed < 0) continue;

它不是确定性的 - 对于不同的元素顺序,它忽略了不同的元素而不被检查,因此元素顺序的改变正在改变结果.

删除tiebreaking if,结果将对输入列表中元素的顺序不敏感.