我刚刚重写了大约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 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;

工作正常。

我希望我的困惑问题至少对寻求“一致抽样”的人有用。

我应该用番石榴 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();
}