有效随机地改组单词序列的位

Question

考虑C ++标准库中的以下算法：std::shuffle该算法具有以下签名：

template <class RandomIt, class URBG>
void shuffle(RandomIt first, RandomIt last, URBG&& g);

它对给定范围内的元素进行重新排序，以使[first, last)这些元素的每个可能排列具有相同的出现概率。

---

我正在尝试实现相同的算法，但是它在位级别起作用，随机地对输入序列的单词的位进行改组。考虑到64位字的序列，我正在尝试实现：

template <class URBG>
void bit_shuffle(std::uint64_t* first, std::uint64_t* last, URBG&& g)

---

问题：如何尽可能有效地做到这一点（必要时使用编译器内部函数）？我并不一定要寻找一个完整的实现，而是要寻找更多的建议/研究方向，因为对于我来说，实际上是否有效地实现它尚不明确。

Answer 1

很明显，渐近地，速度是O(N)，其中N是位数。我们的目标是改进其中涉及的常量。

免责声明：所提出的算法的描述是一个粗略的草图。需要添加很多东西，尤其是需要注意很多细节才能使其正常工作。不过，大致的执行时间不会与此处声明的不同。

基线算法

最明显的一种是教科书式的方法，它需要N操作，每个操作都涉及调用random_generator需要R毫秒的时间，并访问两个不同位的位值，并为它们设置新值总共4 * A毫秒（A是读/写的时间）一点）。假设数组查找操作需要C几毫秒。所以这个算法的总时间是N * (R + 4 * A + 2 * C)毫秒（大约）。假设随机数生成需要更多时间也是合理的，即R >> A == C。

提议的算法

假设位存储在字节存储器中，即我们将使用字节块。

unsigned char bit_field[field_size = N / 8];

首先，让我们计算一下1我们的位集中的位数。为此，我们可以使用查找表并以字节数组的形式遍历 bitset：

# Generate lookup-table, you may modify it with `constexpr`
# to make it run in compile time.
int bitcount_lookup[256];
for (int = 0; i < 256; ++i) {
  bitcount_lookup[i] = 0;
  for (int b = 0; b < 8; ++b)
    bitcount_lookup[i] += (i >> b) & 1;
}

我们可以将其视为预处理开销（因为它也可以在编译时计算）并说它需要0几毫秒。现在，计算1位数很容易（以下将花费(N / 8) * C几毫秒）：

int bitcount = 0;
for (auto *it = bit_field; it != bit_field + field_size; ++it)
  bitcount += bitcount_lookup[*it];

现在，我们随机生成N / 8数字（我们称之为结果数组gencnt[N / 8]），每个数字都在 范围内[0..8]，这样它们的总和为bitcount。这有点棘手，而且很难统一（与基线算法相比，生成均匀分布的“正确”算法相当慢）。一个非常统一但快速的解决方案大致是：

• gencnt[N / 8]用 values填充数组v = bitcount / (N / 8)。
• 随机选择N / 16“黑色”单元格。其余部分为“白色”。该算法类似于随机排列，但只是数组的一半。
• 生成N / 16范围内的随机数[0..v]。让我们打电话给他们tmp[N / 16]。
• 将“黑色”单元格增加tmp[i]值，将“白色”单元格减少tmp[i]. 这将确保总和为bitcount。

之后，我们将有一个uniform-ish random-ish数组gencnt[N / 8]，其值1是特定“单元格”中的字节数。这一切都是在：

(N / 8) * C   +  (N / 16) * (4 * C)  +  (N / 16) * (R + 2 * C)
^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^
filling step      random coloring              filling

毫秒（这个估计是通过我脑海中的具体实现完成的）。最后，我们可以有一个字节的查找表，其中指定的位数设置为1（可以编译开销，甚至在编译时为constexpr，因此我们假设这需要0几毫秒）：

(N / 8) * C   +  (N / 16) * (4 * C)  +  (N / 16) * (R + 2 * C)
^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^
filling step      random coloring              filling

然后，我们可以bit_field按如下方式填充我们的（大约需要(N / 8) * (R + 3 * C)几毫秒）：

std::vector<std::vector<unsigned char>> random_lookup(8);
for (int c = 0; c < 8; c++)
  random_lookup[c] = { /* numbers with `c` bits set to `1` */ };

总结一切，我们有总执行时间：

T = (N / 8) * C +
    (N / 8) * C + (N / 16) * (4 * C) + (N / 16) * (R + 2 * C) + 
    (N / 8) * (R + 3 * C)

  = N * (C + (3/16) * R)  <  N * (R + 4 * A + 2 * C)
    ^^^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^^
     proposed algorithm        naive baseline algo

虽然它不是真正均匀随机，但它确实相当均匀和随机地散布这些位，而且速度非常快，希望能在您的用例中完成工作。