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

Question

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

查找表的生成方式是第一个表中的元素指向第二个表中的元素，而第二个表中的元素指向第一个表中的元素，但这不是重点。

这是我目前所拥有的(有点慢，尤其是 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()和 std::iota() .

Answer 1

只需使用标准算法，特别是 std::shuffle()和 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;
}