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

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是位数。我们的目标是改进其中涉及的常量。

Disclaimer: the description proposed algorithm is a rough sketch. There are a lot of stuffs needs to be added and, especially, a lot of details that needs to be cared of in order to make it work correctly. The approximated execution time will not be different from what is claimed here though.

---

基线算法

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

---

提出的算法

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

unsigned char bit_field[field_size = N / 8];

首先，让我们计算位集中 1 位的数量。为此，我们可以使用查找表并将位集作为字节数组进行迭代:

# 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。这有点棘手，很难统一执行(与基线算法相比，生成均匀分布的“正确”算法相当慢)。一个相当统一但快速的解决方案大致是:

• 用值v = bitcount/(N/8)填充gencnt[N/8]数组。
• 随机选择 N/16 个“黑色”单元格。其余为“白色”。算法类似于random permutation , 但只有数组的一半。
• 在 [0..v] 范围内生成 N/16 个随机数。我们称它们为 tmp[N/16]。
• 将“黑色”单元格增加 tmp[i] 值，将“白色”单元格减少 tmp[i]。这将确保总和为 bitcount。

之后，我们将得到一个统一的随机数组gencnt[N/8]，其值是1字节数特别的“细胞”。全部生成于:

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

毫秒(这个估计是我脑子里具体实现的)。最后，我们可以将指定位数设置为 1 的字节查找表(可以在开销中编译，甚至在编译时作为 constexpr，所以让我们假设这需要 0 毫秒):

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` */ };

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

for (int i = 0; i < field_size; i++) {
  bit_field[i] = random_lookup[gencnt[i]][rand() % gencnt[i].size()];

Summing everything up, we have the total execution time:

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

Although it's not truly uniformly random, but it does spread the bits out quite evenly and randomly, and it's quite fast and hopefully gets the job done in your use-case.