Почему новая случайная библиотека лучше, чем 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::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));
}

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

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

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

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

Изменить: @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 предоставляет только образец реализации), поэтому любая программа, которая предназначена для создания воспроизводимого вывода (или ожидает ГПСЧ некоторого известного качества) в разных компиляторах, должна запускать собственный генератор;
• не предоставляет какой-либо кроссплатформенный метод для получения приличного начального числа ( time(NULL)нет, поскольку он недостаточно детализирован и часто - подумайте о встроенных устройствах без RTC - даже недостаточно случайный).

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

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

... а также значение по умолчанию random_deviceдля их заполнения.

Теперь, если вы спросите меня, мне бы также понравился простой API, построенный поверх этого, для «простых» случаев «угадать число» (аналогично тому, как Python предоставляет «сложный» API, но также тривиальный random.randint& Co .используя глобальный, предварительно засеянный 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его легче встроить.

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

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

Например, если у нас есть RAND_MAX25, мы rand() % 5получим числа со следующей частотой:

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

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

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

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

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

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

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

Стандартная библиотека C ++ предоставляет три класса механизмов генерации случайных чисел: линейный конгруэнтный (из которых rand() пример которого), запаздывающий по Фибоначчи и крутильный механизм Мерсенна. У каждого класса есть свои компромиссы, и каждый класс в определенном смысле «лучший». Например, LCG имеют очень маленькое состояние и, если выбраны правильные параметры, довольно быстро на современных настольных процессорах. Группы LFG имеют более крупное состояние и используют только операции выборки и сложения из памяти, поэтому работают очень быстро во встроенных системах и микроконтроллерах, в которых отсутствует специализированное математическое оборудование. MTG имеет огромное состояние и работает медленно, но может иметь очень большую неповторяющуюся последовательность с превосходными спектральными характеристиками.

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

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