在短时间内生成随机数从1到100.000.000的表，没有任何双精度

Question

对于一个项目，我需要创建一个表，该表以随机顺序存储100.000.000个数字，没有任何双精度，然后保存为。csv文件。

void Anonym_Option::GenerateTable(){
ui->progressBar->setValue(0);
QList<int> l(100000000);
std::iota(l.begin(), l.end(), 0);
QVector<QList<int>::iterator> v(l.size());
std::iota(v.begin(), v.end(), l.begin());
ui->progressBar->setValue(10);
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
auto rng = std::default_random_engine {seed};
QCoreApplication::processEvents();
std::shuffle(v.begin(), v.end(), rng);
QString SortString;
QString CombinedString;
ui->progressBar->setValue(30);
for (auto z: v){
QCoreApplication::processEvents();
SortString += QString::number(*z) + "," + "n";
}
ui->progressBar->setValue(70);
CombinedString = SortString.replace(QString("n;"), QString("n"));
QString Table = "Generated ID; n" + CombinedString;
ui->progressBar->setValue(90);
QString Path = QDir::currentPath();
QFile file(Path + "/Table.csv");
if (!file.open(QFile::WriteOnly | QFile::Text)){
QMessageBox::warning(this, "ACHTUNG","ACHTUNG! Der Anonymisierungs-Table kann nicht generiert werden! Bitte Kontaktieren sie den Support.");
return;
}
else{
QTextStream stream(&file);
QCoreApplication::processEvents();
stream << Table;
ui->progressBar->setValue(100);
hide();
anonymisierung = new Anonymisierung();
QTimer::singleShot(1500,anonymisierung,SLOT(show()));
}
}

该表的目的是替换客户文件中的数字，以便它是匿名的。我的代码的问题是，如果我使用10.000.000个数字，它需要大约8分钟才能完成，但是当我使用100.000.000时，它似乎需要更多的RAM和时间，而不是实际的。我可以在这个函数

中进行本地化吗?

for (auto z: v){
QCoreApplication::processEvents();
SortString += QString::number(*z) + "," + "n";
}

的全部目的是添加"，"one_answers"; n"在每个数字之后，这样它就会被相应地分开，可以在以后使用。有什么办法来加快进度吗?

TL;DR我使用QT6希望范围，遗憾的是还没有实现，所以不是一个我可以使用的选项!

Answer 1

如果您正在存储密钥，那么shuffle也一样快。我尽量保持相似，但当洗牌时，一个std::linear_congruential_engine都没有意义，花了4倍的时间。

我包含了这两个方法，所以您可以注释掉并自己测试它们。虽然不是非常科学，但我的shell提示符显示了执行时间，两个方法都显示了10秒。我在WSL中执行存储在Windows-land中的文件。

编译器标志:clang++ -Wall -Wextra -O2 -std=c++17

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
int main() {
constexpr std::uint32_t upper = 100'000'000;
std::vector<std::uint32_t> rando(upper);
std::iota(rando.begin(), rando.end(), 1);
std::shuffle(rando.begin(), rando.end(),
std::mt19937(std::random_device{}()));
for (std::uint32_t i = 345; i < 355; ++i) {
std::cout << rando[i] << ' ';
}
std::cout << 'n';
}
// #include <iostream>
// #include <vector>
// int main()
// {
//     constexpr std::uint32_t upper = 100000000;
//     std::vector<std::uint32_t> rando;
//     rando.reserve(upper);
//     std::uint32_t I = 128;
//     for (std::uint32_t i = 0; i <= upper;){
//         I = 1664525 * I + 1013904223;
//         if (I <= upper){
//             rando.push_back(I);
//             ++i;
//         }
//     }
//     for (int i = 345; i < 355; ++i) {
//         std::cout << rando[i] << ' ';
//     }
//     std::cout << 'n';
// }

Answer 2

洗牌方法很可能需要将数组保存在连续的内存块中，这对于大量元素可能不可行。

然而，如果你的随机性程度不需要比rand()的典型实现更好，那么你可以使用线性同余生成器，它具有在周期性达到之前不会重复的属性，并且不包括范围外的数字。

下面的程序在我的机器上运行不到一秒钟，它将生成一个文件，其中包含了[0,100000000]范围内的所有数字，没有重复。

#include <iostream>
int main()
{
constexpr std::uint32_t upper = 100000000;
std::uint32_t I = 128;
for (std::uint32_t i = 0; i <= upper;){
I = 1664525 * I + 1013904223;
if (I <= upper){
std::cout << I << "n";
++i;
}
}
}

根据系统时钟选择I(种子)的初始值。

同余步骤中的神奇数字归功于杰出的科学程序员Donald Knuth。