c - 从整数子集中均匀随机选择一个数的算法

Question

假设 int 数组 a[i]=i, i=0, 1, 2, ..., N-1。现在假设每个整数都与一个位相关联。我需要一种算法从整数子集中随机选择一个整数，其关联位为 0。假设相关位为 0 的整数的总数已经在变量 T 中给出。

我有一个直接的解决方案是生成 r=rand() % T，然后找到关联位为 0 的第 r 个整数(通过测试 i =0,1,...)。但是，我想知道这样做会有什么体面的算法吗？另外，如果说关联位存储在一些 long int 变量中(在我的例子中是这样)，找到第 r 个关联位为 0 的整数将不是一件容易的事。

感谢您的投入。

Answer 1

如果关联的位是不规则的，即不能从 i 的值中推导出来通过一个简单的公式，那么就不可能找到 r-th '0'位而不枚举前面的那些，除非允许预处理。

一个好的解决方案是预先计算一个表来存储 '0' 的索引。连续位条目，并在该表中查找 r-th入口。 (除了索引表，您还可以仅使用子集中的元素填充另一个数组。)

---

索引压缩位数组并不是什么大问题。假设 64 位 long ints ，索引位 i由表达式找到

(PackedBits[i >> 6] >> (i & 63)) & 1

(6 因为64 == (1 << 6) 。)

万一你真的想找到 r-th '0'按顺序，您可以通过预先计算 '0's 的数量来稍微加快搜索速度 (x 64)在每个 long int 中，这样您就可以一次跳过 64 个条目。

如果您真的不想预先计算任何东西，您仍然可以通过使用将每个字节值(在 256 中)与数​​字相关联的静态表来处理 8 位 8 位来加快搜索速度的 '0'其中的位。 (如果您负担得起使用 65536 数字的表格，甚至可以是 16 x 16。)