存储"180位"(超过64位)整数的有效方法

Question

我使用位来表示一天发生的事件.例如,如果我存储4天的信息,我可以使用1011(从右到左凝视)将在第1,2天指示,并且发生4个事件(第1,2和4位设置).

我正在使用Long存储位的类型(在此示例中将存储数字11).现在Long我可以存储63天的事件(长最大尺寸是2 ^ 64 -1).

仅供参考:我稍后在我的一系列事件中选择一个,然后将其与另一组进行比较,以查看同一天发生了多少事件(我使用Long的bitcount方法来执行此操作).例如,1011 AND 1000 = 1事件发生在这两组中的同一天.

我面临的问题是:我现在需要存储超过63天的数据.我现在需要大约180天.我正面临着我的两个解决方案的性能问题,并且想知道是否有更有效的方法来实质上存储"180位"整数.

我的第一个解决方案是使用BigInteger,但这在运行时非常慢.我的另一个解决方案是将180位分解为3 Long秒,然后相应地进行比较,但显然这会产生3倍的工作量.

Answer 1

java.util.BitSet中

BitSet是标准库的一部分,适用于您的用例.但也许你应该看看下面的第二个选项是压缩的替代选择.这应该是更多的内存和性能效率.

使用标准库,您可以定义类似的东西

BitSet bits1 = new BitSet(180);

即使存储超过180位,您也可以随时调整大小.

如果你想将它与其他套装进行比较,你可以这样做:

BitSet bits1 = new BitSet(180);
BitSet bits2 = new BitSet(180);
// do something here to set events

// find events which happened on the same day in bits1 and bits2
bits1.and(bits2);

然后你可以使用像nextSetBit这样的东西来遍历集合.从Oracle文档的示例来遍历在其上发生在所有的事件bits1和bits2将则:

for (int i = bits1.nextSetBit(0); i >= 0; i = bits1.nextSetBit(i+1)) {
     // operate on index i here
}

压缩位集JavaEWAH

请参阅:javaewah的Github存储库

替代Java BitSet,用于一些大数据项目,如Apache Hive和Apache Spark.

JavaEWAH示例:

EWAHCompressedBitmap eventsBitmap1 = EWAHCompressedBitmap.bitmapOf(
    0,1,22,64,1<<30);
EWAHCompressedBitmap eventsBitmap2 = EWAHCompressedBitmap.bitmapOf(
    1,3,64,1<<30);
System.out.println("Events 1: "+eventsBitmap1);
System.out.println("Events 2: "+eventsBitmap2);

查找同一天发生的事件

EWAHCompressedBitmap bothEventsBitmap = eventsBitmap1.and(eventsBitmap2);
System.out.println("Days where both events took place: "+bothEventsBitmap);

进一步实施

• 咆哮位图,也是压缩位图实现.