Cần một máy phát ngẫu nhiên nhanh cho C++

Question

Tôi đang cố gắng thực hiện một số thay đổi opt-3 trên máy phát TSP của mình cho khoảng cách euclidian, và vì tôi trong nhiều trường hợp có hơn ~ 500 nút, tôi cần chọn ngẫu nhiên ít nhất 1 của 3 nút mà tôi muốn thử trao đổi.

Vì vậy, về cơ bản tôi cần một hàm số ngẫu nhiên là nhanh. (rand bình thường() là cách quá chậm) Nó không phải là tuyệt vời, chỉ tốt đủ.

EDIT: Tôi quên đề cập đến, tôi đang ngồi ở môi trường nơi tôi không thể thêm bất kỳ thư viện nào ngoại trừ Thư viện ngôn ngữ chuẩn (chẳng hạn như STL, iostream v.v.). Vì vậy, không tăng =/

Answer 1

Chủ đề khác đề cập đến trình tạo xorshf của Marsaglia, nhưng không ai đăng mã.

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

Tôi đã sử dụng mã này ở mọi nơi. Nơi duy nhất nó thất bại là khi tôi đang cố tạo ra các ma trận nhị phân ngẫu nhiên. Quá khứ về ma trận 95x95, nó bắt đầu tạo ra quá ít hoặc quá nhiều ma trận số ít (tôi quên cái nào). Nó được chỉ ra rằng máy phát điện này tương đương với thanh ghi phản hồi thay đổi tuyến tính. Nhưng trừ khi bạn đang làm mật mã hoặc làm việc nghiêm túc monte carlo, đá máy phát điện này.

Answer 2

bạn có thể tạo trước một loạt các bit ngẫu nhiên trước thời gian và bóc chúng ra 2 tại một thời điểm (vì bạn chỉ cần một số ngẫu nhiên từ 1 đến 3)?

Answer 3

Thư viện tăng cường có một bộ máy phát ngẫu nhiên. Biểu đồ hiệu suất có thể được tìm thấy here.

EDIT: Câu trả lời này đã có ở đây trước khi chỉnh sửa câu hỏi gốc. Nhưng tôi hy vọng nó có thể vẫn hữu ích, vì vậy tôi để nó ở đây.

Answer 4

Mersenne Twister có một số triển khai nhanh.

Answer 5

rand() thực sự rất nhanh, và tôi không tin bạn sẽ tìm thấy nhanh hơn nhiều.

Nếu thực tế là làm chậm bạn xuống (điều mà tôi nghi ngờ), thì bạn cần thay đổi kiến ​​trúc.

Tôi khuyên bạn nên điền trước một danh sách dài với số ngẫu nhiên, sau đó khi bạn cần, chỉ cần lấy một từ danh sách, thay vì tạo một. Bạn có thể điền lại danh sách bằng chuỗi nền.

Answer 6

Xem these generators từ chuyên gia tạo số ngẫu nhiên George Marsaglia. Chúng được triển khai dưới dạng macro C và chúng nhanh như chớp, chỉ một vài thao tác trên mỗi số được tạo.

Answer 7

Hai lựa chọn thay thế tốt từ trang web của intel của:

1) fastrand - đó là 2,01 X nhanh hơn so với rand std(). Thường trình trả về một số nguyên, phạm vi giá trị đầu ra tương tự như C lib.

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

2) một phiên bản SSE (xem link bên dưới) là khoảng 5,5 X nhanh như std rand() tuy nhiên nó tạo ra 4 giá trị ngẫu nhiên tại một thời điểm, đòi hỏi một processer với SSE (hầu hết làm), và phức tạp hơn.

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

Answer 8

tôi nghĩ cũng là khá tốt, và WELL512a là khá ngắn. http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a cũng rất phức tạp. Tuy nhiên, WELL tạo một số từ 0 đến 1.

Answer 9

Thậm chí tho bài đăng này là năm cũ, nó xuất hiện khi tôi đang tìm kiếm một câu trả lời tương tự và câu trả lời tôi đã sử dụng, thậm chí không có trong đó. Vì vậy, tôi đang thêm cái tôi tìm thấy;

#include <random> msdn entry

Cách tiếp cận này sẽ xây dựng một khép kín phát ngẫu nhiên, và tôi thấy nó được rất nhiều ngẫu nhiên hơn rand()%x; hơn vài trăm nghìn lần lặp lại. rand()% sẽ không bao giờ ném 16+ đầu/đuôi trong một hàng, khi cần 65 nghìn lần thử khác. Điều này không chỉ làm điều đó, nhưng nó thực hiện nó trong một phần tư thời gian.

Đây là cách tôi thực hiện #include <random> bản thân mình:

//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); 

Answer 10

Bắt đầu với Ivy Bridge kiến ​​trúc Intel thêm RdRand hướng dẫn CPU và bộ xử lý AMD thêm nó sau này trong tháng Sáu năm 2015. Vì vậy, nếu bạn đang nhắm mục tiêu một bộ xử lý đó là mới đủ và don Không sử dụng lắp ráp nội tuyến (inline), cách nhanh nhất để tạo ra các số ngẫu nhiên nên gọi số RdRand Lệnh CPU để nhận số ngẫu nhiên 16 hoặc 32 hoặc 64 bit như được mô tả here. Cuộn đến gần giữa trang để xem các ví dụ về mã. Tại liên kết đó cũng có một ví dụ mã để kiểm tra CPU hiện tại để hỗ trợ hướng dẫn RdRand, và xem thêm Wikipedia cho một lời giải thích về cách thực hiện điều này với lệnh CPUID.

câu hỏi liên quan: Making use of sandy bridge's hardware true random number generator? (mặc dù theo Wikipedia, RdRand hướng dẫn đầu tiên xuất hiện trong Ivy Bridge, nhưng không Sandy Bridge kiến ​​trúc như câu hỏi đó nói)

Ví dụ C++ dựa trên _rdrand64_step():

#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