需要一個快速隨機發生器爲C++

我試圖做一些opt-3交換我的TSP發生器的歐幾里德距離，因爲我在很多情況下有超過500個節點，我需要隨機選擇至少1我想嘗試交換的3個節點。需要一個快速隨機發生器爲C++

所以基本上我需要一個隨機數函數快速。（正常的蘭特（）方式太慢）它不一定非常棒，只要夠了。

編輯：我忘了提及，我坐在一個環境中，除了標準語言庫（如STL，iostream等）之外我無法添加任何庫。所以沒有提升=/

2009-10-28 Martin Andersson

聲音像我的問題：http://stackoverflow.com/questions/1046714/what-is-a-good-random-number-generator-for-a-game（我去了一個五行XORshift生成器。） – 2009-10-28 21:37:34

@GManNickG ：rand（）實現是特定於平臺的。如何在不知道使用的具體實現的情況下判斷其速度？ – dragonroot 2012-12-04 19:53:54

@GManNickG：「MT通常比rand（）更快，或接近同樣快，具有更好的屬性......」？你怎麼知道它並沒有首先實現MT？ – dragonroot 2012-12-05 05:23:38

另一個線程提到了Marsaglia的xorshf生成器，但沒有人發佈代碼。

static unsigned long x=123456789, y=362436069, z=521288629; 

unsigned long xorshf96(void) {   //period 2^96-1 
unsigned long t; 
    x ^= x << 16; 
    x ^= x >> 5; 
    x ^= x << 1; 

    t = x; 
    x = y; 
    y = z; 
    z = t^x^y; 

    return z; 
}

我已經在這個地方使用了這個。唯一失敗的地方是當我試圖產生隨機二進制矩陣。過去大約95x95矩陣，它開始產生太少或太多的奇異矩陣（我忘記了它）。已經表明這個發生器相當於一個線性移位反饋寄存器。但除非你正在做密碼學或嚴肅的蒙特卡洛工作，否則這個發生器會發生變化。

來源

2009-10-28 21:58:20 AndyV

數字食譜（我知道，這是有點爭議，因爲他們多年來在這些書中提出了大量廢話）建議不要單獨使用XOR移位，而只能使用組合發生器。 – Joey 2009-11-03 06:42:56

奇異矩陣太奇怪了，因爲奇異矩陣在所有矩陣空間中都是「奇異的」。 – becko 2014-02-27 16:29:03

什麼是64位版本而無需調用此函數兩次？用uint64_t替換並將第一個換位從16更改爲32就足夠了嗎？ – 2015-06-15 15:03:50

你能提前預先生成一堆隨機位，並且一次剝離它們2（因爲你只需要一個介於1和3之間的隨機數）？

來源

2009-10-28 21:38:05 Mikeb

Boost庫有一組隨機生成器。性能圖表可以找到here。

編輯：這個答案在這裏是原始問題的編輯之前。但我希望它仍然有幫助，所以我把它留在這裏。

來源

2009-10-28 21:38:24

更新圖表http://www.boost.org/doc/libs/1_47_0/doc/html/boost_random/reference.html#boost_random.reference.generators – k107 2011-09-19 23:15:31

Mersenne Twister有一些快速的實現。

來源

2009-10-28 21:46:24 lhf

MT19937通常比LCG更快。另外還有面向SIMD的Fast Mersenne Twister：http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html更快。 – Joey 2009-10-30 06:59:47

rand（）真的很麻煩，我不相信你會發現更快。如果它實際上減慢你的速度（我有點懷疑），那麼你需要一個體繫結構的改變。

我建議用隨機數預先填充一個長列表，然後當你需要一個列表時，只需從列表中選取一個，而不是生成一個列表。您可以使用後臺線程重新填充列表。

來源

2009-10-28 21:55:21 abelenky

在現代處理器上，計算新數字比從內存中提取新數字要快。 – 2011-09-16 18:48:54

我試過這個，它是Tegra3上最快的方法，如果你在填充它之後按順序遍歷數組。缺點是數字會在短時間內重複。 – 2013-08-10 15:18:38

相當古老的反應，但@MarkRansom：你確定嗎？使用隨機數的密集列表（可實現緩存和預取改進）應該比任何足夠好的隨機數生成快得多。或者你有代碼顯示嗎？ – Bouncner 2017-06-25 11:46:36

查看these generators來自隨機數生成器專家George Marsaglia。它們被實現爲C宏，並且它們閃電般快速，僅僅產生了每個數字的幾個操作。從英特爾的網站

來源

2009-10-28 21:58:40

兩個很好的選擇：

1）fastrand - 它比STD蘭特快2.01 X（）。該例程返回一個整數，與C lib類似的輸出值範圍。

inline int fastrand() { 
    g_seed = (214013*g_seed+2531011); 
    return (g_seed>>16)&0x7FFF; 
}

2）SSE版本（見下面的鏈接）爲約5.5 X一樣快STD蘭特（），然而它在一個時間，生成4個隨機值，需要與SSE一個processer（幾乎所有這樣做），和比較複雜。

http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/

來源

2010-09-19 21:00:19 Sunsetquest

不錯，使用這個而不是rand（）在Tegra 3上加快了約2.5倍的例程。 – 2013-08-10 14:15:48

這太棒了！我不得不產生幾百萬個隨機數字，這給了一個令人難以置信的加速。 – 2017-01-13 04:12:27

我想好是相當不錯的，而且WELL512a是很短。 http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a當時也很複雜。但是，WELL會生成一個介於0和1之間的數字。

來源

2013-08-26 12:47:35

即使這篇文章已經過去了幾年，它在我尋找類似答案時出現了，我最終使用的答案並不存在。所以我添加了我找到的那個;

這種做法將建立一個自包含隨機生成的，我發現這是一個很多比rand()%x更隨機的;超過幾十萬次迭代。 rand()%永遠不會扔16+頭/尾連續，當它應該每隔65k嘗試。這不僅僅是這樣，而且是在四分之一的時間內完成的。

我這是怎麼實現#include <random>自己：

//create rng_gen, using mt technique, with range 0,1 (coin) and 1,6(dice); 
std::random_device rd; //seed 
std::mt19937 gen(rd()); //seed for rd(merzenne twister) 
std::uniform_int_distribution<> rng_coin(0, 1); //rng1 range 
std::uniform_int_distribution<> rng_dice(1, 6); ///rng2 range 

rng_coin(gen); //will apply rng1 range on (gen) object. Is very fast 
rng_dice(gen); //will apply rng2 range, returns int. 

//will output 1000 cointosses to console 
for (int i=0;i<1000;++i)std::cout<<rng_coin(gen)<<"\n"; 
//will generate 1000 dice throws 
for (int i=0;i<1000;++i)rng_dice(gen);

來源

2016-04-16 13:24:20 Charlie

與Ivy Bridge架構英特爾開始加入RdRand CPU指令和AMD在2015年六月以後增加它因此，如果你的目標的處理器已經夠新和唐不介意使用（內聯）程序集，生成隨機數的最快方法應該是調用RdRand CPU指令以獲得如here所述的16位或32位或64位隨機數。滾動到頁面中間的代碼示例。在那個鏈接上還有一個代碼示例，用於檢查當前CPU是否支持RdRand指令，另請參閱維基百科，瞭解如何使用CPUID指令執行此操作。

相關問題：Making use of sandy bridge's hardware true random number generator?（雖然根據維基百科，RdRand指令最早出現在常春藤橋，但不Sandy Bridge架構作爲問題指出）的基礎上_rdrand64_step()

例C++代碼：

#include <immintrin.h> 

uint64_t randVal; 
if(!_rdrand64_step(&randVal)) { 
    // Report an error here: random number generation has failed! 
} 
// If no error occured, randVal contains a random 64-bit number

來源

2016-07-01 21:43:48

需要一個快速隨機發生器爲C++

回答

相關問題