动机
我刚刚重新编写了大约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
(如下定义)返回符合一些有趣标准的最大字符串,去除重复项,限制结果并使用Guava进行收集。所有步骤应该是IMHO确定性和“有序”的,但我可能忽略了某些东西。另一种可能性是我的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();
}
list
)是无序的,那么list.iterator().next()
如何保证是确定性的? - shmoselselectSome
的输入。我的问题可能是由我在这里发布的代码引起的,也可能是由其他地方的某些难以解释的错误引起的... 如果我没有三重检查所有内容,我就不会问这个非常长的问题。 - maaartinus