以随机可再现顺序生成非重复字节的快速方法

Question

我需要一种快速生成 256 行的方法，每行有 256 个随机字节且没有重复。

查找 table 的生成方式是第一个 table 中的元素指向第二个 table 中指向第一个 [=] 中的元素的元素26=]，但这不是重点。

这是我目前所拥有的（有点慢，尤其是 while (random_int >= (int)unused.size()) 部分） :

unsigned char lookup_table[256 * 256];
unsigned char lookup_table_inverted[256 * 256];

std::vector<unsigned char> unused;
std::mt19937_64 rng(seed);
std::uniform_int_distribution<int> dist(0, 255);
int random_int;

for (int i = 0; i < 256; ++i)
{
    for (int j = 0; j < 256; ++j)
    {
        unused.push_back((unsigned char)j);
    }

    for (int j = 0; j < 256; ++j)
    {
        random_int = dist(rng);
        while (random_int >= (int)unused.size())
        {
            random_int = dist(rng);
        }

        lookup_table[(i * 256) + j] = unused[random_int];
        lookup_table_inverted[(i * 256) + unused[random_int]] = (unsigned char)j;
        unused.erase(unused.begin() + random_int);
    }
}

已解决：使用 std::shuffle() and std::iota()。

Answer 1

我会使用 std::shuffle 可能是这样的：

std::array<unsigned char, 256> get_random_bytes(int seed = 0)
{
    thread_local static std::mt19937 mt{std::random_device{}()};

    if(seed)
        mt.seed(seed);

    std::array<unsigned char, 256> bytes;

    // fill with the full range of values
    std::iota(std::begin(bytes), std::end(bytes), 0);
    std::shuffle(std::begin(bytes), std::end(bytes), mt); // randomly shuffle them

    return bytes;
}

如果您为该函数提供一个非零参数，它将用于为 PRNG 播种，从而使结果可重现。

Answer 2

只需使用标准算法，特别是 std::shuffle() and std::iota。
不要尝试自己烘焙，这很容易出错，而且效率可能很低。

unsigned char lookup_table[256 * 256];
unsigned char lookup_table_inverted[256 * 256];
for (int i = 0; i < 256; ++i) {
     auto start = lookup_table + 256 * i;
     std::iota(start, start + 256, 0);
     std::shuffle(start, start + 256, rng);
     auto rev = lookup_table_inverted + 256 * i;
     for (int c = 0; c < 256; ++c)
         rev[start[c]] = c;
}

以随机可再现顺序生成非重复字节的快速方法

Fast way of generating non-repeating bytes in a random reproducible order

c++

arrays

random

lookup

vector