Почему новая случайная библиотека лучше, чем std :: rand()?

Итак, я увидел доклад под названием rand() "Вредный", и он рекомендовал использовать парадигму распределения движков для генерации случайных чисел в простой парадигме std::rand() плюс модуль.

Однако я хотел воочию увидеть недостатки std::rand() поэтому я провел быстрый эксперимент:

  1. По сути, я написал 2 функции getRandNum_Old() и getRandNum_New() которые генерировали случайное число от 0 до 5 включительно, используя std::rand() и std::mt19937 + std::uniform_int_distribution соответственно.
  2. Затем я сгенерировал 960 000 (делится на 6) случайных чисел, используя "старый" способ, и записал частоты чисел 0-5. Затем я рассчитал стандартное отклонение этих частот. То, что я ищу, - это как можно более низкое стандартное отклонение, поскольку именно это и произошло бы, если бы распределение было действительно равномерным.
  3. Я провел эту симуляцию 1000 раз и записал стандартное отклонение для каждой симуляции. Я также записал время, которое потребовалось в миллисекундах.
  4. После этого я снова сделал то же самое, но на этот раз генерировал случайные числа "новым" способом.
  5. Наконец, я вычислил среднее и стандартное отклонение списка стандартных отклонений как для старого, так и для нового способа, а также среднее и стандартное отклонение для списка времен, взятых как для старого, так и для нового способа.

Вот результаты:

[OLD WAY]
Spread
       mean:  346.554406
    std dev:  110.318361
Time Taken (ms)
       mean:  6.662910
    std dev:  0.366301

[NEW WAY]
Spread
       mean:  350.346792
    std dev:  110.449190
Time Taken (ms)
       mean:  28.053907
    std dev:  0.654964

Удивительно, но совокупный разброс валков был одинаковым для обоих методов. std::mt19937 есть std::mt19937 + std::uniform_int_distribution не был "более равномерным", чем простой std::rand() + %. Другое наблюдение, которое я сделал, было то, что новый был примерно в 4 раза медленнее, чем старый. В целом, казалось, что я платил огромные затраты на скорость, почти не повышая качество.

Мой эксперимент ошибочен? Или std::rand() действительно не так уж и плохо, а может, даже лучше?

Для справки вот код, который я использовал полностью:

#include <cstdio>
#include <random>
#include <algorithm>
#include <chrono>

int getRandNum_Old() {
    static bool init = false;
    if (!init) {
        std::srand(time(nullptr)); // Seed std::rand
        init = true;
    }

    return std::rand() % 6;
}

int getRandNum_New() {
    static bool init = false;
    static std::random_device rd;
    static std::mt19937 eng;
    static std::uniform_int_distribution<int> dist(0,5);
    if (!init) {
        eng.seed(rd()); // Seed random engine
        init = true;
    }

    return dist(eng);
}

template <typename T>
double mean(T* data, int n) {
    double m = 0;
    std::for_each(data, data+n, [&](T x){ m += x; });
    m /= n;
    return m;
}

template <typename T>
double stdDev(T* data, int n) {
    double m = mean(data, n);
    double sd = 0.0;
    std::for_each(data, data+n, [&](T x){ sd += ((x-m) * (x-m)); });
    sd /= n;
    sd = sqrt(sd);
    return sd;
}

int main() {
    const int N = 960000; // Number of trials
    const int M = 1000;   // Number of simulations
    const int D = 6;      // Num sides on die

    /* Do the things the "old" way (blech) */

    int freqList_Old[D];
    double stdDevList_Old[M];
    double timeTakenList_Old[M];

    for (int j = 0; j < M; j++) {
        auto start = std::chrono::high_resolution_clock::now();
        std::fill_n(freqList_Old, D, 0);
        for (int i = 0; i < N; i++) {
            int roll = getRandNum_Old();
            freqList_Old[roll] += 1;
        }
        stdDevList_Old[j] = stdDev(freqList_Old, D);
        auto end = std::chrono::high_resolution_clock::now();
        auto dur = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
        double timeTaken = dur.count() / 1000.0;
        timeTakenList_Old[j] = timeTaken;
    }

    /* Do the things the cool new way! */

    int freqList_New[D];
    double stdDevList_New[M];
    double timeTakenList_New[M];

    for (int j = 0; j < M; j++) {
        auto start = std::chrono::high_resolution_clock::now();
        std::fill_n(freqList_New, D, 0);
        for (int i = 0; i < N; i++) {
            int roll = getRandNum_New();
            freqList_New[roll] += 1;
        }
        stdDevList_New[j] = stdDev(freqList_New, D);
        auto end = std::chrono::high_resolution_clock::now();
        auto dur = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
        double timeTaken = dur.count() / 1000.0;
        timeTakenList_New[j] = timeTaken;
    }

    /* Display Results */

    printf("[OLD WAY]\n");
    printf("Spread\n");
    printf("       mean:  %.6f\n", mean(stdDevList_Old, M));
    printf("    std dev:  %.6f\n", stdDev(stdDevList_Old, M));
    printf("Time Taken (ms)\n");
    printf("       mean:  %.6f\n", mean(timeTakenList_Old, M));
    printf("    std dev:  %.6f\n", stdDev(timeTakenList_Old, M));
    printf("\n");
    printf("[NEW WAY]\n");
    printf("Spread\n");
    printf("       mean:  %.6f\n", mean(stdDevList_New, M));
    printf("    std dev:  %.6f\n", stdDev(stdDevList_New, M));
    printf("Time Taken (ms)\n");
    printf("       mean:  %.6f\n", mean(timeTakenList_New, M));
    printf("    std dev:  %.6f\n", stdDev(timeTakenList_New, M));
}

Ответы

Ответ 1

Практически любая реализация "старого" rand() использует LCG; в то время как они, как правило, не самые лучшие генераторы, обычно вы не увидите, как они провалится в таком базовом тесте - среднее значение и стандартное отклонение, как правило, корректируются даже худшими PRNG.

Типичные ошибки "плохих" - но достаточно распространенных - реализаций rand():

  • низкая случайность младших битов;
  • короткий период;
  • низкий RAND_MAX;
  • некоторая корреляция между последовательными экстракциями (в общем, LCG производят числа, которые находятся на ограниченном числе гиперплоскостей, хотя это может быть как-то смягчено).

Тем не менее, ни один из них не является специфичным для API rand(). Конкретная реализация может поместить генератор семейства xorshift за srand/rand и, если говорить алгоритмически, получить современный PRNG без изменений интерфейса, поэтому ни один тест, подобный тому, который вы делали, не показал бы слабости в выходных данных.

Изменить: @R. правильно отмечает, что интерфейс rand/srand ограничен тем фактом, что srand принимает unsigned int, поэтому любой генератор, который может быть реализован реализацией, ограничен UINT_MAX возможными начальными начальными семенами (и, следовательно, сгенерированными последовательностями). Это действительно так, хотя API можно тривиально расширить, чтобы srand занимал unsigned long long или добавляла отдельную перегрузку srand(unsigned char *, size_t).

В самом деле, реальная проблема с rand() - это не столько реализация в принципе, сколько:

  • обратная совместимость; во многих современных реализациях используются субоптимальные генераторы, обычно с плохо выбранными параметрами; известный пример - Visual C++, который имеет RAND_MAX всего 32767. Однако это нельзя изменить легко, так как это нарушило бы совместимость с прошлым - люди, использующие srand с фиксированным начальным числом для воспроизводимых симуляций, не были бы рады (действительно, вышеупомянутая реализация IIRC восходит к ранним версиям Microsoft C - или даже к Lattice C - с середины восьмидесятых годов);

  • упрощенный интерфейс; rand() предоставляет один генератор с глобальным состоянием для всей программы. Хотя это прекрасно (и на самом деле очень удобно) для многих простых вариантов использования, оно создает проблемы:

    • с многопоточным кодом: для его исправления вам нужен либо глобальный мьютекс - который бы все замедлял без причины и убивал любые шансы на повторяемость, так как последовательность вызовов сама становится случайной - либо локальное состояние потока; последний был принят несколькими реализациями (особенно Visual C++);
    • если вам нужна "частная" воспроизводимая последовательность в конкретный модуль вашей программы, которая не влияет на глобальное состояние.

И наконец, rand положение вещей:

  • не указывает фактическую реализацию (стандарт C предоставляет только пример реализации), поэтому любая программа, которая предназначена для получения воспроизводимого результата (или ожидает PRNG некоторого известного качества) для разных компиляторов, должна запустить свой собственный генератор;
  • не предоставляет какого-либо кроссплатформенного метода для получения достойного начального числа (time(NULL) - нет, поскольку оно недостаточно детализировано, и часто - думаю, встраиваемые устройства без RTC - даже не достаточно случайные).

Отсюда новый заголовок <random>, который пытается исправить этот беспорядок, предоставляя следующие алгоритмы:

  • полностью указан (так что вы можете иметь кросс-компилятор воспроизводимых выходных данных и гарантированные характеристики - скажем, диапазон генератора);
  • как правило, самого современного качества (с момента создания библиотеки; см. ниже);
  • инкапсулированы в классы (поэтому вам не нужно навязывать глобальное состояние, что позволяет избежать проблем с многопоточностью и нелокальностью);

... и по умолчанию random_device для их random_device.

Теперь, если вы спросите меня, мне бы также понравился простой API, построенный поверх этого, для "простых" случаев "угадать число" (аналогично тому, как Python предоставляет "сложный" API, но также и тривиальный random.randint & Co. использует глобальный, предварительно random.randint PRNG для нас несложных людей, которые хотели бы не утонуть в случайных устройствах/движках/адаптерах/что угодно каждый раз, когда мы хотим извлечь число для карт бинго), но это правда, что Вы можете легко построить его самостоятельно на основе текущих возможностей (в то время как создание "полного" API поверх упрощенного было бы невозможным).

Наконец, вернемся к вашему сравнению производительности: как указали другие, вы сравниваете быструю LCG с более медленным (но обычно считающимся лучшим качеством) Mersenne Twister; если вы согласны с качеством LCG, вы можете использовать std::minstd_rand вместо std::mt19937.

Действительно, после настройки вашей функции использовать std::minstd_rand и избежать бесполезных статических переменных для инициализации

int getRandNum_New() {
    static std::minstd_rand eng{std::random_device{}()};
    static std::uniform_int_distribution<int> dist{0, 5};
    return dist(eng);
}

Я получаю 9 мс (старый) против 21 мс (новый); наконец, если я избавлюсь от dist (который по сравнению с классическим оператором по модулю обрабатывает перекос распределения для выходного диапазона, не кратного входному диапазону) и вернусь к тому, что вы делаете в getRandNum_Old()

int getRandNum_New() {
    static std::minstd_rand eng{std::random_device{}()};
    return eng() % 6;
}

Я уменьшил его до 6 мс (то есть на 30% быстрее), вероятно потому, что в отличие от вызова rand(), std::minstd_rand проще std::minstd_rand.

Между прочим, я провел тот же тест, используя свернутый вручную (но в значительной степени соответствующий стандартному интерфейсу библиотеки) XorShift64*, и он в 2,3 раза быстрее, чем rand() (3,68 мс против 8,61 мс); учитывая, что, в отличие от Mersenne Twister и различных предоставляемых LCG, он проходит текущие тесты на случайность с летающими цветами и невероятно быстро, это заставляет задуматься, почему он еще не включен в стандартную библиотеку.

Ответ 2

Если вы повторите свой эксперимент с диапазоном больше 5, вы, вероятно, увидите другие результаты. Когда ваш диапазон значительно меньше, чем RAND_MAX для большинства приложений RAND_MAX нет.

Например, если у нас RAND_MAX 25, тогда rand() % 5 выдаст числа со следующими частотами:

0: 6
1: 5
2: 5
3: 5
4: 5

Поскольку RAND_MAX гарантированно будет больше 32767, а разница в частотах между наименее вероятным и наиболее вероятным составляет всего 1, для небольших чисел распределение будет почти случайным для большинства случаев использования.

Ответ 3

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

Предсказуемость: последовательность 012345012345012345012345... обеспечит равномерное распределение каждого числа в вашей выборке, но, очевидно, не случайна. Для последовательности, которая должна быть случайной, значение n + 1 не может быть легко предсказано значением n (или даже значениями n, n-1, n-2, n-3 и т.д.). Очевидно, повторяющаяся последовательность из тех же цифр вырожденный случай, но последовательность, сгенерированная любым линейным конгруэнтным генератором, может быть подвергнута анализу; если вы используете стандартные стандартные настройки LCG из общей библиотеки по умолчанию, злоумышленник может "нарушить последовательность" без особых усилий. В прошлом несколько он-лайн казино (и некоторые обычные) пострадали от потерь на машинах, использующих плохие генераторы случайных чисел. Даже люди, которые должны знать лучше, были схвачены; Было показано, что чипы TPM от нескольких производителей легче разбить, чем длина битов ключей, которые можно было бы предсказать из-за неправильного выбора с параметрами генерации ключей.

Распределение: как упоминалось в видео, взятие по модулю 100 (или любого значения, не делимого равномерно на длину последовательности) гарантирует, что некоторые результаты станут, по крайней мере, немного более вероятными, чем другие результаты. Во вселенной 32767 возможных начальных значений по модулю 100 числа от 0 до 66 будут появляться на 328/327 (0,3%) чаще, чем значения от 67 до 99; фактор, который может дать злоумышленнику преимущество.

Ответ 4

Правильный ответ: это зависит от того, что вы подразумеваете под "лучше".

"Новые" <random> движки были введены в C++ более 13 лет назад, поэтому они не совсем новые. Библиотека C rand() была введена несколько десятилетий назад и в то время была очень полезна для множества вещей.

Стандартная библиотека C++ предоставляет три класса механизмов генерации случайных чисел: линейное конгруэнтное (примером которого является rand()), Lagged Fibonacci и Mersenne Twister. Есть компромиссы каждого класса, и каждый класс "лучший" в определенных отношениях. Например, LCG имеют очень маленькое состояние и, если правильные параметры выбраны, довольно быстро на современных процессорах для настольных ПК. LFG имеют большее состояние и используют только выборки памяти и операции сложения, поэтому они очень быстры на встроенных системах и микроконтроллерах, в которых отсутствует специализированное математическое оборудование. MTG имеет огромное состояние и является медленным, но может иметь очень большую неповторяющуюся последовательность с превосходными спектральными характеристиками.

Если ни один из поставляемых генераторов не подходит для вашего конкретного использования, стандартная библиотека C++ также предоставляет интерфейс для аппаратного генератора или вашего собственного пользовательского движка. Ни один из генераторов не предназначен для использования в автономном режиме: они предназначены для использования через объект распределения, который обеспечивает случайную последовательность с определенной функцией распределения вероятностей.

Другое преимущество <random> перед rand() состоит в том, что rand() использует глобальное состояние, не является реентерабельным или поточно-ориентированным и допускает один экземпляр на процесс. Если вам нужен детальный контроль или предсказуемость (т.е. Возможность воспроизвести ошибку с учетом начального состояния RNG), тогда rand() бесполезен. Генераторы <random> создаются локально и имеют сериализуемое (и восстанавливаемое) состояние.