Дешевая и веселая замена rand () - PullRequest
Новая
       1

Дешевая и веселая замена rand ()

9 голосов
/ 16 июня 2010

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

Ответы [ 7 ]

7 голосов
/ 16 июня 2010

Существует несколько распространенных алгоритмов, которые работают быстрее, чем LCG (что весьма вероятно, что использует rand()).Вы можете попробовать генератор Marsaglia Xorshift , который работает довольно быстро (в зависимости от аппаратного обеспечения).Генератор WELL512a также довольно быстрый (больше, чем MT19937 или MT19937-64).

4 голосов
/ 16 июня 2010
2 голосов
/ 16 июня 2010

Вот один из тех, что я написал для Java на основе алгоритма XORShift от Marsaglia, который вы, вероятно, можете адаптировать. Прекрасно работает для моих целей (разработка игр, симуляция). 

/**
 * State for random number generation
 */
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);

/**
 * Gets a long random value
 * @return Random long value based on static state
 */
public static final long nextLong() {
    long a=state;
    state = xorShift64(a);
    return a;
}

/**
 * XORShift algorithm - credit to George Marsaglia!
 * @param a Initial state
 * @return new state
 */
public static final long xorShift64(long a) {
    a ^= (a << 21);
    a ^= (a >>> 35);
    a ^= (a << 4);
    return a;
}
2 голосов
/ 16 июня 2010

Вы можете использовать некоторые предварительно рассчитанные значения для случайных чисел и сохранять их в некоторых массивах. Алгоритмы RNG - задача не из легких. Если вам нужно небольшое количество случайных чисел, то, на мой взгляд, это решение.

Обычно в играх существует много предварительных вычислений (значения sin / cos и другие вещи, которые очень часто используются в видеоигре, и они будут потреблять много циклов ЦП, если не будут предварительно рассчитаны).

Вы также можете посмотреть на HW RNG , но я считаю, что об этом не может быть и речи.

1 голос
/ 16 июня 2010

Поскольку вы мало говорили о своей реализации, если она многопоточная, с использованием функции, использующей глобальное состояние, почти всегда плохая идея. Многие реализации тогда просто используют мьютексы для защиты одновременного доступа. Длинные времена, которые вы наблюдаете, будут просто временем ожидания, а не вычислением самой функции rand. POSIX имеет семейство функций rand48, которые также имеют реентерабельные версии, которые должны работать лучше при одновременном доступе, см. http://opengroup.org/onlinepubs/007908799/xsh/drand48.html

0 голосов
/ 16 июня 2010

Говорят, что Mersenne Twister быстрее, чем многие реализации RAND, но YMMV в зависимости от деталей реализации и аппаратного обеспечения.

0 голосов
/ 16 июня 2010

Это может быть не очень хороший ответ, и на самом деле это скорее вопрос.

В зависимости от платформы и частоты в зависимости от значения, не будут ли наименее значимые числа возвращаемой функции в микросекундах приближаться к чему-то «случайному»?

...