将Java BigInteger用于巨大的位掩码的性能影响 [英] Performance implications of using Java BigInteger for a huge bitmask

问题描述

我们面临着一个有趣的挑战.我们必须控制对驻留在箱"中的数据的访问.可能会有成千上万的垃圾箱".对每个垃圾箱的访问都是单独控制的，但限制可能并且可能会重叠.我们正在考虑为每个bin分配一个位掩码(1、2、3、4等)中的位置.

然后，当用户登录系统时，我们将查看其安全属性，并确定允许他查看哪些垃圾箱.利用该信息，我们为该用户构造了一个位掩码，其中设置"位对应于他允许看到的容器的标识符.因此，如果他可以看到垃圾箱1、3和4，那么他的位掩码将是1101.

因此，当用户搜索数据时，我们可以查看返回行的bin索引，并查看该位是否在其位掩码上设置.如果他的位掩码设置了该位，我们让他看到该行.我们计划将位掩码存储为Java中的BigInteger.

我的问题是:假设索引号没有变得比Integer.MAX_INT大，BigInteger位掩码是否可以缩放成千上万个位?在n可能很大的地方(例如874,837)运行BigInteger.isBitSet(n)是否需要永远?创建这样的BigInteger是否需要永远?

其次:如果您有其他选择，我很想听听.

解决方案

如果您不经常更改BigInteger，它应该很快.

一个更明显的选择是 BitSet 专为这种事情而设计.对于查找位，我怀疑性能是相似的.对于创建/修改，使用BitSet更为有效.

注意:PaulG表示区别在于令人印象深刻"，而BitSet更快.

We have an interesting challenge. We have to control access to data that reside in "bins". There will be, potentially, hundreds of thousands of "bins". Access to each bin is controlled individually but the restrictions can, and probably will, overlap. We are thinking of assigning each bin a position in a bitmask (1,2,3,4, etc..).

Then when a user logs into the system, we look at his security attributes and determine which bins he's allowed to see. With that info we construct a bitmask for this user where the "set" bits correspond to the identifier of the bins he's allowed to see. So if he can see bins 1, 3 and 4, his bit mask would be 1101.

So when a user searches the data, we can look at the bin index of the returned row and see if that bit is set on his bitmask. If his bitmask has that bit set we let him see that row. We are planning for the bitmask to be stored as a BigInteger in Java.

My question is: Assuming the index number doesn't get bigger that Integer.MAX_INT, is a BigInteger bitmask going to scale for hundreds of thousands of bit positions? Would it take forever to run BigInteger.isBitSet(n) where n could be huge (e.g. 874,837)? Would it take forever to create such a BigInteger?

And secondly: If you have an alternative approach, I'd love to hear it.

解决方案

BigInteger should be fast if you don't change it often.

A more obvious choice would be BitSet which is designed for this sort of thing. For looking up bits, I suspect the performance is similar. For creating/modifying it would be more efficient to use a BitSet.

Note: PaulG has commented the difference is "impressive" and BitSet is faster.

这篇关于将Java BigInteger用于巨大的位掩码的性能影响的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！