我有很多SortedSet<Long>
结构:
1, 2, 5, 8, 10, 35, 77, ...
5, 9, 35, 50, 132, ...
2, 4, 8, 15, 17, 23, ...
... hundreds of thousands of such rows...
我需要找到一个数字,比如说,50
。在这个例子中(如果只有三组)它是77
. 集合的数量是巨大的 - 数十万。你会建议什么算法?
如果我理解正确,这是我的想法:
Collection<SortedSet<Long>> sets = //...
long minAfter50 = Long.MAX_VALUE;
for (SortedSet<Long> set : sets) {
final Long first = set.tailSet(51L).first();
minAfter50 = Math.min(minAfter50, first);
}
这是想法:
更新(基于@beerbajay评论):如果 SortedSet 实际上是 a TreeSet
,则以下代码可能会执行得更好。此外,我确保每组中都有任何大于 50 的值:
long minAfter50 = Long.MAX_VALUE;
for (TreeSet<Long> set : sets) {
final Long higher = set.higher(50L);
if (higher != null && higher < minAfter50) {
minAfter50 = higher;
}
}
如果这就是您允许的所有预计算,那么您唯一能做的就是在每个 SortedSet 上调用 tailSet 并找到最小值。
如果您允许一些额外的数据结构,最简单的做法是跟踪所有集合的并集,然后您只需调用 tailSet 即可。
我怀疑这也不是你想要的答案。也许您可以更好地描述您的限制条件?
set 实现为二叉搜索树,最大的数总是在最后。您可以更轻松地搜索大于 50 的数字,始终获得每组中大于 50 的第一个数字。