性能Java位集：高效地查找所有真实位？

Question

假设使用了来自^{}的BitSet。目标是快速找到设置为true的所有位值。这些值没有顺序，也没有特定的模式。BitSet的最大索引将为2^31 - 48。将被设置为true的总位数为(2^31 - 48)/2。换句话说，有20亿位可以是true/false，我如何有效地找到所有true位

每次将位设置为true，都需要运行以访问BitSet中的所有true位。你可以看到为什么每次循环所有的2^31 - 48位在性能方面没有那么有效

这里有一个不符合我需要的解决方案：创建一个大小为(2^31 - 48)/2的int[] indices，每次将一个位i设置为true，将值i存储在indices的下一个可用插槽中。虽然这有助于实现请求，但它会将大约32 * (2^31 - 48)/2位添加到大约4.3Gb的内存中

重点在于性能和重复计算。不需要使用输入/输出文件或BitSet以外的其他东西

达到预期行为的最快方法是什么？或什么是一种使用更少内存的足够快的方法

Answer 1

What is the fastest approach to achieve the desired behaviour?

如果您将自己限制为位集API，那么我认为您需要一个重复调用BitSet.nextSetBit的循环。是的，需要2^30个电话。但是我认为它和使用BitSetAPI一样好

如果你想要更快的速度，你要么需要发明自己的数据结构来实现这一点（我没有任何真正好的想法），要么改变问题

观察：无论你怎么做，每次检查2^30位的变化都会带来巨大的计算开销

如果这是我的问题，我会首先寻找一个更聪明的解决方案，完全避免这样做。如果没有智能解决方案，我可能会使用int数组而不是BitSet，并找到一种方法，在8/16/32个核上并行扫描¹。（但这也取决于你需要为true的每一位做什么。）

---

^{1-这假设您有空闲的内核/电源/冷却来解决这个问题}

---

Or... what is a sufficiently quick approach that also uses significantly less memory?

顺便说一句，你不能用比O(2^N)位更好的方式来表示2^N随机真/假值。你唯一的希望是，如果比特模式是非随机且易于压缩的。即使这样，压缩/解压的CPU成本，以及有效更新压缩位序列中的位的问题也会出现。这是否可行取决于比特流的性质