使用uniform_int_distribution与模运算相比有哪些优势？

Question

根据以下结果，使用 % 操作生成两个数字之间的均匀随机整数比使用 std::uniform_int_distribution 快近3倍：是否有充分的理由使用 std::uniform_int_distribution？

代码：

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
#include <random>

#include <cstdio>
#include <cstdlib>

using namespace std;

#define N 100000000

int main()
{

clock_t tic,toc;

for(int trials=0; trials<3; trials++)
{
    cout<<"trial: "<<trials<<endl;

    // uniform_int_distribution
    {
        int res = 0;
        mt19937 gen(1);
        uniform_int_distribution<int> dist(0,999);

        tic = clock();
        for(int i=0; i<N; i++)
        {
            int r = dist(gen);
            res += r;
            res %= 1000;
        }
        toc = clock();
        cout << "uniform_int_distribution: "<<(float)(toc-tic)/CLOCKS_PER_SEC << endl;
        cout<<res<<" "<<endl;

    }

    // simple modulus operation
    {
        int res = 0;
        mt19937 gen(1);

        tic = clock();
        for(int i=0; i<N; i++)
        {
            int r = gen()%1000;
            res += r;
            res %= 1000;
        }
        toc = clock();
        cout << "simple modulus operation: "<<(float)(toc-tic)/CLOCKS_PER_SEC << endl;
        cout<<res<<" "<<endl;

    }

    cout<<endl;
}

}

输出：

trial: 0
uniform_int_distribution: 2.90289
538 
simple modulus operation: 1.0232
575 

trial: 1
uniform_int_distribution: 2.86416
538 
simple modulus operation: 1.01866
575 

trial: 2
uniform_int_distribution: 2.94309
538 
simple modulus operation: 1.01809
575 

- vervenumen

---

std::uniform_int_distribution 能够在任意整数区间内生成等概率分布，而 % 不能。 - Lingxi

如果不需要写正确的代码，那么编写快速代码非常容易。 - T.C.

https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful - T.C.

附注：我建议你尝试删除 res %= 1000; 这行代码。我可以想象几种它会破坏你的测试的方式。 - user1084944

也许是因为它很“统一”吧？ - CodesInChaos

Answer 1

使用模除 (%) 将 e.g. rand() 的值域映射到另一个区间时，你会获得统计偏差。

例如，假设 rand() 均匀地映射 (没有偏差) 到 [0, 32767]，并且你想要将其映射到[0,4]，则进行 rand() % 5。那么平均产生的值为0、1和2会有6554次在32768次中出现，但是值3和4只有6553次 (所以3 * 6554 + 2 * 6553 = 32768)。

偏差很小 (0.01%)，但根据你的应用程序可能会导致灾难性后果。请观看 Stephan T. Lavavej 的演讲 "rand() considered harmful" 了解更多细节。

- TemplateRex

---

公平地说，一个推论是，如果模数是2的常数幂，则％ rsp.＆可能比uniform_int_distribution快得多，并且在通常的实现中不会引入偏差。 - Arne Vogel

@ArneVogel 是的，但只有当RAND_MAX也是2的幂时才成立。这个值取决于具体实现。保证这个值至少为32767。对于可移植的代码和通用接口，只需使用uniform_int_distribution即可。 - TemplateRex

@ArneVogel 那看起来像是一个QOI问题，不是吗？但是，如果你有一个具有X位熵的随机数，它的宽度为Y位，熵均匀分布，如果你提取较低的Z位，则最终会得到X * Z/Y位的熵。如果你将所有Y位混合到你的结果中（一个简单的移位异或系统），你的输出仍然可以具有高达X位的熵（假设X <= Z）。 - Yakk - Adam Nevraumont

@Yakk 如果你的随机数生成器以100%的随机性返回M个数字中的一个，并且你需要其中的N个数字，那么除非M可被N整除，否则任何接受M个原始数字并将其映射到N个数字之一的操作都会存在偏差。你需要计算出M'，它是N的倍数，将这些M'个数字中的任何一个映射到N个数字之一，如果选择了另一个数字，则拒绝它并选择另一个数字（或使用更复杂的方法）。 - gnasher729

如果在晴朗无云的中午走出户外，天空是蓝色的。天空不可能是淡粉色带绿条纹。(简而言之，你在说什么？你的句法看起来像是在回应我的评论，但你最多只是谈论我所谈论的话题的相关性，并且以一种似乎在反驳我的方式进行？我正在讨论ArneVogel暗示的想法，即如果源随机数据范围和模数都是2的幂，则百分号可能是一个好主意。这就是“@arnevogel”的意思。请看Arne的评论。) - Yakk - Adam Nevraumont