创建位矩阵和扫描集列的有效方法
提问于 2013-05-12 12:28:31
这就是我目前的问题，我有一些布隆过滤器，我想把它们构建成一个矩阵，比如：
[0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
...
[1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0]每列都将从BitSet派生，除了循环所有行并比较每个索引之外，有没有更有效的方法来查找位设置为1的所有列？
有什么数据结构可以帮助我做到这一点吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-05-12 13:59:24
假设您正在查找哪些列包含1，现在每列包含多少个，循环遍历它们似乎是最好的想法。
如果您使用一些短路逻辑实现您的循环，那么您将获得更好的平均运行时间。
类似于：
for (int column = 0; column < width; column++) {
for (int row = 0; row < height; row++) {
if (array[column][row] == 1) {
list.append(column);
break; // move on to the next column because we don't care what's
// left in this column as we already found our '1'使用这段代码，您将获得n (n是bits的总数)的最坏情况(如果每个bit都是0)的运行时间，这是非常好的。
但是，除非您非常不幸，否则由于short-circuit逻辑，您将获得更好的运行时间。
上面的方法适用于位数组，但是，BitSets本身也有一些有用的功能。
BitSet包含以下函数：length()返回最高的索引，设置位为+1(如果没有设置位，则返回0 )和nextSetBit(index)，返回index -> end中下一个设置位的索引。
所以你的代码可能很容易是这样的：
int index = 0;
while (index < BitSet.length()) {
index = BitSet.nextSetBit(index);
list.append(index);
index++;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16507342
复制
![[日常] 腾讯云发送邮件失败问题](https://ask.qcloudimg.com/http-save/yehe-2504969/rjkvvvrpvm.png)
腾讯云开发者
