Java Bitset的替代方案,具有类似性能的数组？

Question

我正在寻找Java Bitset实现的替代方案.我正在实现一个高性能算法,似乎使用Bitset对象正在扼杀它的性能.有任何想法吗？

Answer 1

有人在这里已经比较boolean[]来BitSet得出的结论有:

BitSet比boolean[]非常小的尺寸更节省内存.boolean数组中的每个都需要一个字节.来自的数字runtime.freeMemory()有点混乱BitSet,但更少.

boolean[]除了非常大的尺寸之外,它们的CPU效率更高,它们大致均匀.例如,对于100万的大小,boolean[]大约快4倍(例如6ms对27ms),对于10亿和1亿大约是偶数.

如果你是Google,你也可以找到一些替代实现,比如Apache Hive,Apache Spark和Eclipse JGit使用的JavaEWAH.它声称:

字对齐压缩的目标不是实现最佳压缩,而是改善查询处理时间.因此,我们尝试节省CPU周期,可能以存储为代价.但是,我们实现的EWAH方案在存储方面总是比在BitSet类中实现的未压缩位图更有效.与某些替代方案不同,javaewah不依赖于专利方案.

Answer 2

查看Javolution FastBitSet:与集合框架集成的高性能bitset作为一组索引,并遵循FastSet.size()(cardinality)或FastCollection.equals(java.lang.Object)等方法的集合语义(相同)一组指数).

另请参阅http://code.google.com/p/guava-libraries/issues/detail?id=724#c3.

Answer 3

在搜索单个字节比较和多个布尔比较的问题的答案时,我找到了OpenBitSet

他们声称比Java BitSet更快,并且可以直接访问存储位的字数组.

我肯定会试试.看它是否也能解决你的目的.