Нужен быстрый генератор случайных чисел для С++

Я пытаюсь сделать некоторую замену opt-3 на моем генераторе TSP для эвклидовых расстояний, и поскольку во многих случаях у меня больше, чем ~ 500 узлов, мне нужно случайным образом выбрать хотя бы один из трех узлов, которые я хочу попробуйте обменять.

Поэтому в основном мне нужна функция случайного числа, которая быстро. (нормальный rand() слишком медленный). Это не должно быть потрясающим, достаточно хорошим.

EDIT: Я забыл упомянуть, я сижу в среде, где я не могу добавить никаких библиотек, кроме стандартной языковой библиотеки (например, STL, iostream и т.д.). Таким образом, нет boost =/

Ответ 1

В другой теме упоминается генератор 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 матриц, оно начинает генерировать слишком мало или слишком много сингулярных матриц (я забываю, что). Было показано, что этот генератор эквивалентен регистру обратной связи с линейным сдвигом. Но если вы не делаете криптографию или серьезную работу монте-карло, этот генератор скалывает.

Ответ 2

Две хорошие альтернативы от сайта intel:

1) fastrand - на 2.01 X быстрее, чем std rand(). Процедура возвращает одно целое число, аналогичное диапазону выходных значений, как C lib.

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

2) версия SSE (см. ссылку ниже) составляет примерно 5,5 X с такой скоростью, как std rand(), однако она генерирует 4 случайных значения за раз, требует обработчика с sse (почти все) и сложнее.

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

Ответ 3

Смотрите эти генераторы от эксперта по генератору случайных чисел Джорджа Марсалья. Они реализованы как макросы C, и они молниеносно, всего несколько операций на число сгенерировано.

Ответ 4

Mersenne Twister имеет несколько быстрых реализаций.

Ответ 5

Начиная с Ivy Bridge архитектура Intel добавила RdRand Инструкция CPU и AMD добавили ее позже в июне 2015 года. Поэтому, если вы нацеливаете процессор, который является достаточно новым и не против использования (встроенной) сборки, самый быстрый способ генерации случайных чисел должен быть в вызове RdRand CPU для получения 16- или 32- или 64-битного случайного числа, как описано здесь. Прокрутите до середины страницы примеры кода. В этой ссылке есть также пример кода для проверки текущего процессора для поддержки команды RdRand и см. Также Википедию для объяснения того, как это сделать с инструкцией CPUID.

Связанный с этим вопрос: Использование аппаратного генератора случайных чисел из песчаного моста? (хотя согласно Википедии инструкция RdRand впервые появилась в Ivy Bridge, но не Sandy Архитектура моста, как говорится в этом вопросе)

Ответ 6

rand() действительно штопает быстро, и я не верю, что вы найдете гораздо быстрее.

Если это на самом деле замедляет вас (что я сомневаюсь), вам нужно изменить архитектуру.

Я рекомендую предварительно заполнять длинный список случайными числами, тогда, когда вам это нужно, просто возьмите его из списка, а не создайте. Возможно, вы сможете повторно заполнить список фоновым потоком.

Ответ 7

Даже в этот пост лет, он появился, когда я искал аналогичный ответ, и ответ, который я использовал, даже не в нем. Поэтому я добавляю тот, который я нашел;

#include <random> msdn entry

Этот подход будет строить автономный генератор случайных чисел, и я обнаружил, что он намного более случайный, чем 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)<<std::endl
//will generate 1000 dice throws
for (int i=0;i<1000;++i)rng_dice(gen);

Ответ 8

Вы можете заранее создать кучу случайных бит и очистить их по 2 за раз (так как вам нужно только случайное число от 1 до 3)?

Ответ 9

Библиотека Boost имеет набор случайных генераторов. Таблицу производительности можно найти здесь.

EDIT: этот ответ был до редактирования исходного вопроса. Но я надеюсь, что это может быть полезно, поэтому я оставляю его здесь.

Ответ 10

Я думаю, что WELL очень хорош, а WELL512a довольно короткий. http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a является сложным в то же время. Однако WELL генерирует число от 0 до 1.