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

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;
}