我正在尝试在我的TSP生成器上做一些opt-3交换以获得欧几里德距离,并且由于我在很多情况下有超过500个节点,我需要随机选择我想尝试交换的3个节点中的至少1个.
所以基本上我需要一个快速的随机数函数.(正常的rand()太慢了)它不一定非常好,只是足够好.
编辑:我忘了提,我坐在一个环境,除了标准语言库(如STL,iostream等),我无法添加任何库.所以没有提升= /
C++11 通过该库支持伪随机数生成<random>。
我看过多本书籍，其中提到持续构建和销毁std::random_device, std::uniform_int_distribution<>,std::uniform_real_distribution<>对象的成本非常高，并且他们建议在应用程序中保留这些对象的单个副本。
为什么创建/销毁这些对象的成本很高？这里的贵到底是什么意思呢？就执行速度、可执行文件大小或其他方面而言，它是否昂贵？
有人可以提供一些解释吗？
在查看英特尔数字随机数发生器(DRNG)软件实施指南之后,我对RDRAND调用时生成器的内部状态会发生什么问题提出了一些问题.不幸的是,答案似乎不在指南中.
根据该指南,在DRNG内部有四个128位缓冲器,用于提供随机位以RDRAND进行漏极.RDRAND本身将提供16位,32位或64位随机数据,具体取决于目标寄存器的宽度:
rdrand ax ; put 16 random bits in ax
rdrand eax ; put 32 random bits in eax
rdrand rax ; put 64 random bits in rax
使用更大的目标寄存器会更快地清空这些128位缓冲区吗？例如,如果我只需要2位随机性,那么我是否应该经历在64位寄存器上使用16位寄存器的麻烦？这会对DRNG的吞吐量产生任何影响吗？我想避免消耗比必要更多的随机性.
指南说执行后将设置进位标志RDRAND:
CF = 1 Destination register valid. Non-zero random value
available at time of execution. Result placed in register.
CF = 0 Destination register all zeros. Random value not available
at time of execution. May be retried.
"不可用"是什么意思？随机数据是否可用,因为RDRAND调用过快地耗尽了这些128位缓冲区？或者不可用意味着DRNG未通过健康检查而无法生成任何新数据？基本上,我试图理解CF …
我正在研究在格子中移动的粒子的随机游走模拟.出于这个原因,我必须创建大量的随机数,大约10 ^ 12及以上.目前我正在使用C++ 11提供的可能性<random>.在分析我的程序时,我发现花了大量的时间<random>.绝大多数这些数字在0到1之间,均匀分布.在这里,我需要一个二项分布的数字.但重点在于0..1数字.
问题是:我可以做些什么来减少生成这些数字所需的CPU时间以及对其质量的影响？
正如您所看到的,我尝试了不同的引擎,但这对CPU时间没有太大影响.此外,我uniform01(gen)和generate_canonical<double,numeric_limits<double>::digits>(gen)无论如何有什么区别？
编辑:通过阅读答案,我得出的结论是,对于我的问题,没有理想的解决方案.因此,我决定首先使我的程序具有多线程功能,并在不同的线程中运行多个RNG(以一个random_device编号+一个线程单独增量播种).目前这种接缝是最不可避免的步骤(无论如何都需要多线程).作为进一步的步骤,等待确切的要求,我考虑切换到建议的英特尔RNG或Thrust.这意味着我的RNG实现不应该是复杂的,当前不是.但是现在我喜欢专注于我的模型的物理正确性而不是编程的东西,只要我的程序输出在物理上是正确的. 推力 关于英特尔RNG
这是我目前所做的事情:
class Generator {
public:
Generator();
virtual ~Generator();
double rand01(); //random number [0,1)
int binomial(int n, double p); //binomial distribution with n samples with probability p
private:
std::random_device randev; //seed
/*Engines*/
std::mt19937_64 gen;
//std::mt19937 gen;
//std::default_random_engine gen;
/*Distributions*/
std::uniform_real_distribution<double> uniform01;
std::binomial_distribution<> binomialdist;
};
Generator::Generator() : randev(), gen(randev()), uniform01(0.,1.), binomial(1,1.) {
}
Generator::~Generator() { }
double Generator::rand01() {
//return uniform01(gen);
return generate_canonical<double,numeric_limits<double>::digits>(gen);
} …今天我想:好吧,即使RDRAND对NIST SP 800-90A的实施有很大的怀疑,它仍然是伪随机数发生器(PRNG)的硬件实现,对于非敏感应用来说必须足够好.所以我想在我的游戏而不是Mersenne Twister上使用它.
因此,为了查看使用该指令是否有任何性能提升,我比较了以下两个代码的时间:
// test.cpp
#include <cstdio>
int main()
{
unsigned int rnd = 0;
for(int i = 0; i < 10000000; ++i) {
__builtin_ia32_rdrand32_step(&rnd);
}
printf("%x\n", rnd);
}
和
//test2.cpp
#include <cstdio>
#include <random>
int main()
{
unsigned int rnd = 0;
__builtin_ia32_rdrand32_step(&rnd);
std::mt19937 gen(rnd);
for(int i = 0; i < 10000000; ++i) {
rnd ^= gen();
}
printf("%x\n", rnd);
}
通过运行这两个我得到:
$ time ./test
d230449a
real 0m0.361s
user 0m0.358s
sys 0m0.002s
$ time ./test2
bfc4e472 …我正在研究一种需要尽快生成数百万个数字的算法。实际上我发现我的算法的 rand() 函数占用了 75% 的处理时间。
所以我正在寻找更快的东西。而且我根本不需要大范围。（我只需要 1000 以下的整数）
你知道我可以使用的东西吗？
谢谢 ！
编辑 ：
我使用这个数字来洗牌少于 1000 个实体的组。
我发现了更多关于“快速兰特”的信息。还有 SSE 版本，速度更快，一次生成 4 个数字。
英特尔C++编译器和/或GCC是否支持以下内在函数,例如自2012/2013年以来MSVC的内在函数？
int _rdrand16_step(uint16_t*);
int _rdrand32_step(uint32_t*);
int _rdrand64_step(uint64_t*);
int _rdseed16_step(uint16_t*);
int _rdseed32_step(uint32_t*);
int _rdseed64_step(uint64_t*);
如果支持这些内在函数,那么它们支持哪个版本(请使用编译时常量)？
那么，这个 AVX 的东西 - 它就像每个核心的小型机器？或者它就像整个 CPU 的一个引擎单元？
比如，我可以以某种方式在每个核心上使用它吗？我正在玩它，我觉得我可能会“过度使用”它并造成某种瓶颈。
你能解释一下吗？我都弄错了吗？