为什么新的C++11随机函数库比标准库std::rand()要好?

我看到了一个名为rand() Considered Harmful的演讲,它主张使用随机数生成的引擎分布范式而不是简单的std::rand()加模范式。但是,我想直接看到std :: rand()的失败,所以我做了一个快速的实验:

1.我编写了2个函数getRandNum_Old()和getRandNum_New(),它们分别使用std::rand()和std::mt19937 + std :: uniform_int_distribution生成0到5之间的随机数。

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

令人惊讶的是,两种犯法的差别不大。  我做的另一个观察是新的比旧的方式慢大约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));
}


 
c++
c++11
radom
3s

推荐解答

几乎任何“旧”rand()的实现都使用线性同余发生器(LCG); 虽然它们通常不是最好的发电机,但通常你不会在这样的基本测试中看到它们失败 - 即使是最糟糕的PRNG,平均值和标准偏差通常也是正确的。

坏”的常见缺陷 - 但很常见 - rand()实现是:

  • 低阶位的低随机性;

  • 短期内;

  • 低RAND_MAX;

  • 连续提取之间的一些相关性(通常,LCG产生有限数量的超平面上的数字,尽管这可以以某种方式减轻)。

但是,这些都不是特定于rand()的API。 一个特定的实现可以在xrand / rand后面放置一个xorshift-family生成器,并且在算法上,它可以获得最先进的PRNG而不需要更改接口,因此没有像你所做的那样测试会显示输出中的任何弱点。

正确地指出rand / srand接口受srand采用unsigned int这一事实的限制,因此实现可能放在它们后面的任何生成器本质上都限于UINT_MAX可能的起始种子(以及生成的序列)。 确实如此,尽管可以简单地扩展API以使srand采用无符号长long,或者添加单独的srand(unsigned char *,size_t)重载。

实际上,rand() 的实际问题原则上并没有太多的实现,但是:

  • 向后兼容; 许多当前的实现使用次优的生成器,通常具有错误选择的参数; 一个臭名昭着的例子是Visual C ++,它的RAND_MAX只有32767.然而,这不容易改变,因为它会破坏与过去的兼容性 - 使用srand和固定种子进行可重复模拟的人不会太高兴(事实上) ,IIRC上述实施可以追溯到Microsoft C早期版本 - 甚至是八十年代中期的Lattice C);

  • 简单的界面; rand()为整个程序提供具有全局状态的单个生成器。 虽然这对于许多简单的用例来说非常好(并且实际上非常方便)但它会带来问题:

  • 使用多线程代码:为了解决这个问题,你需要一个全局互斥体 - 这会无缘无故地减慢一切,并且因为调用序列本身变成随机的,或者线程本地状态,所以不会有任何重复性的可能性。 最后一个已经被几个实现采用(特别是Visual C ++);

  • 如果你想要一个“私有”,可重现的序列到你的程序的特定模块中,不会影响全局状态。

最后:

  • 没有指定实际的实现(C标准只提供了一个示例实现),因此任何旨在跨不同编译器生成可重现输出(或期望某种已知质量的PRNG)的程序必须使用自己的生成器;

  • 没有提供任何跨平台的方法来获得合适的种子(时间(NULL)不是,因为它不够精细,而且经常 - 认为没有RTC的嵌入式设备 - 甚至不够随机)。

  nopapp推荐


其它解答 (2)

C++ 11 笔记 (六) : 随机数 - Anti-Magic - 博客园
C++11笔记(六):随机数-Anti-Magic-博客园Anti-Magic首页新随笔联系订阅管理随笔-119文章-0评论-28C++11笔记(六):随机数以前生成一个随机数都是这样:1srand(time(NULL));2rand();在C++11中,标准库中增加了随机数引擎std::default_random_engine这个好东西,然后我们就可以这样:1std::default_random_enginerand_default;2rand_default();另外可以指定随机数种子,有两种方式:std::default_random_enginerand_defaul
  cnblogs.com
C++ 生成随机数 - 漆天初晓 - 博客园
C++生成随机数-漆天初晓-博客园漆天初晓陌上阡头,草长莺飞博客园首页新随笔联系订阅管理随笔-50文章-0评论-0C++生成随机数Rand函数单纯的rand()会返回一个0至RAND_MAX之间的随机数值,而RAND_MAX的值与int位数有关,最小是32767。不过rand()是一次性的,因为系统默认的随机数种子为1,只要随机数种子不变,其生成的随机数序列就不会改变。srand函数srand()可用来设置rand()产生随机数时的随机数种子。通过设置不同的种子,我们可以获取不同的随机数序列。可以利用srand((unsignedint)(time(NULL))的方法,利用系统时
  cnblogs.com