java - Bit Set 真的比 Sorted Set 操作快吗？

Question

我正在寻找交集和并集等位集操作的最佳算法，并且还发现了很多链接和类似的问题。

例如:Similar Question on Stack-Overflow

但是，我想了解的一件事是位设置在其中的位置。例如，Lucene 采用 BitSet 操作来提供高性能的集合操作，特别是因为它可以在较低级别工作。

但是，在我看来，随着元素数量的增加和集合的稀疏性，位集将开始执行缓慢和缓慢，假设集合有大约 10 个元素，其中元素的最大数量可以是 20 亿，因为那会调用不必要的匹配。你有什么建议？

Answer 1

位集对于密集集确实有意义，即覆盖域的很大一部分，因为它们代表每个可能的元素。空间和运行时间要求为 O(D) [D = 域大小 = 20 亿!]。

Sorted Set 操作仅表示给定集合中的元素，并且具有 O(E) 行为 [E = 元素数 = 10]，更合适。

位集速度很快，但效率不高。我的意思是他们的隐藏常数更小。它们对于小型集合(比如 D <= 1024)来说非常快，因为它们可以在一条 CPU 指令中处理 32/64 个元素。