CS 知识库

简体中文

English

简体中文

English

主题

原文链接：[C++] 使用＜random＞头文件生成均匀分布、正态分布的数据

对于满足指定分布的自由变量，如果无法通过分布函数公式计算得到其期望和方差，可以考虑使用采样法得到其期望、方差值的近似值。在此过程中需要按照特定的分布函数进行随机采样，并统计采样数据，可以使用蒙特卡洛或者接受拒接方法得到满足特定分布的随机变量。本文简要介绍了如何使用C++random头文件中自带的函数得到满足 均匀分布 和 高斯分布的变量 。

随机数生成的基本步骤 ​

  1. 定义随机数生成器对象gen，random.h头文件中包含几个随机数生成器类，包括mt19937、default_random_engine等等。
    Generators: Objects that generate uniformly distributed numbers.
  2. 定义随机数分布对象dis，randome头文件中包含了均匀分布(uniform_int_distribution,uniform_real_distribution)、正态分布(normal_distribution)等等几种常用分布类。
    Distributions: Objects that transform sequences of numbers generated by a generator into sequences of numbers that follow a specific random variable distribution, such as uniform, Normal or Binomial.
  3. 使用dis(gen)产生一个满足dis分布的随机变量。

random头文件中关于随机数生成器、分布类的详细信息请参考cplusplus官网。

均匀分布代码 ​

uniform_real_distribution:

c
#include <iostream>
#include <random>
#include <time.h>
using namespace std;
int main() {
    mt19937 gen((unsigned int) time(nullptr)); // 定义随机数生成器对象gen，使用time(nullptr)作为随机数生成器的种子
    uniform_real_distribution<double> dis(-1.0, 1.0); // 定义随机数分布器对象dis，为在[-1.0,1.0]区间内的均匀分布
    for (int i = 0; i < 10; i++) {
        cout << dis(gen) << endl;
    }
    return 0;
}

输出结果为：

bash
0.946503
0.823232
0.340609
0.634292
-0.499202
0.350881
0.925468
-0.914869
-0.648034
-0.36995

mt是指maxint（整型int最大值的缩写）19937是指\(2^{19937}-1\)。mt19937是c++11新特性，它是一种随机数算法，用法与rand()函数类似，但是mt19937具有速度快，周期长的特点（所谓周期长应该是指19937所代表的意思吧）

rand()在windows下生成的数据范围为0-32726，此时的mt19937所生成的数据范围大概为(-maxint,+maxint)（maxint整型int最大值的缩写）

uniform_int_distribution:

cpp
// uniform_int_distribution
#include <iostream>
#include <random>

int main()
{
    const int nrolls = 10000; // number of experiments
    const int nstars = 95;    // maximum number of stars to distribute

    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(0,9);

    int p[10]={};

    for (int i=0; i<nrolls; ++i) {
        int number = distribution(generator);
        ++p[number];
    }

    std::cout << "uniform_int_distribution (0,9):" << std::endl;
    for (int i=0; i<10; ++i)
        std::cout << i << ": " << std::string(p[i]*nstars/nrolls,'*') << std::endl;

    return 0;
}

Possible output:

bash
uniform_int_distribution (0,9):
0: *********
1: *********
2: *********
3: *********
4: *********
5: *********
6: *********
7: *********
8: *********
9: *********

高斯分布代码 ​

c
#include <iostream>
#include <random>
#include <time.h>
using namespace std;
int main() {
    mt19937 gen((unsigned int) time(nullptr)); // 定义随机数生成器对象gen，使用time(nullptr)作为随机数生成器的种子
    normal_distribution<double> dis(0.0, 1.0); // 定义随机数分布器对象dis，期望为0.0，标准差为1.0的正态分布
    for (int i = 0; i < 10; i++) {
        cout << dis(gen) << endl;
    }
    return 0;
}

输出结果为：

bash
-0.188695
0.0804475
-0.647262
-0.0837869
0.84727
-0.115599
0.836252
0.821125
-2.17249
2.01725

注意事项 ​

读者可能会遇到下面的代码（比如在C++11带来的随机数生成器中介绍了这种在linux下的随机数生成方式）：

c
int main{
	...
	random_device rd;
  mt19937 gen(rd());
  for (int i = 0; i < 10; i++) {
    cout << gen() << endl;
  }
  ...
	return 0;
}

该代码在Linux下运行正常，但是在windows下每次运行的结果都相同。比如在我的windows电脑上两次运行的结果都是：

bash
2412496532
3119216746
1495923606
3931352601
26313293
2552602825
3745457912
2213446826
4119067789
4188234190

在C++11带来的随机数生成器中讲这是因为在windows下random_device使用的是rand_s，因此本博客中使用time(nullptr)作为种子。

举个🌰子 ​

例题描述 ​

380. Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present.Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present.Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

思路解析 ​

这道题要求实现一个类，满足插入、删除和获取随机元素操作的平均时间复杂度为 \(O(1)\)。

变长数组可以在\(O(1)\)的时间内完成获取随机元素操作，但是由于无法在 \(O(1)\) 的时间内判断元素是否存在，因此不能在 \(O(1)\)的时间内完成插入和删除操作。

哈希表可以在\(O(1)\)的时间内完成插入和删除操作，但是由于无法根据下标定位到特定元素，因此不能在 \(O(1)\) 的时间内完成获取随机元素操作。

为了满足插入、删除和获取随机元素操作的时间复杂度都是 \(O(1)\)，需要将变长数组和哈希表结合，变长数组中存储元素，哈希表中存储每个元素在变长数组中的下标。

插入操作时，首先判断 \(\textit{val}\)是否在哈希表中，如果已经存在则返回 \(\text{false}\)，如果不存在则插入 \(\textit{val}\)，操作如下：

  1. 在变长数组的末尾添加 \(\textit{val}\)；
  2. 在添加 \(\textit{val}\)之前的变长数组长度为 \(\textit{val}\) 所在下标 \(\textit{index}\)，将 \(\textit{val}\) 和下标 \(\textit{index}\) 存入哈希表；
  3. 返回 \(\text{true}\)。

删除操作时，首先判断 \(\textit{val}\) 是否在哈希表中，如果不存在则返回 \(\text{false}\)，如果存在则删除 \(\textit{val}\)，操作如下：

  1. 从哈希表中获得 \(\textit{val}\)的下标 \(\textit{index}\)；
  2. 将变长数组的最后一个元素\(\textit{last}\)移动到下标\(\textit{index}\)处，在哈希表中将\(\textit{last}\)的下标更新为\(\textit{index}\)；
  3. 在变长数组中删除最后一个元素，在哈希表中删除 \(\textit{val}\)；
  4. 返回 \(\text{true}\)。

删除操作的重点在于将变长数组的最后一个元素移动到待删除元素的下标处，然后删除变长数组的最后一个元素。该操作的时间复杂度是 \(O(1)\)，且可以保证在删除操作之后变长数组中的所有元素的下标都连续，方便插入操作和获取随机元素操作。

获取随机元素操作时，由于变长数组中的所有元素的下标都连续，因此随机选取一个下标，返回变长数组中该下标处的元素。

代码 ​

cpp
class RandomizedSet {
vector<int> nums;
unordered_map<int,int> indices;
mt19937 gen;
public:
RandomizedSet() {
    gen = std::move(mt19937((unsigned int) time(nullptr)));
}

bool insert(int val) {
    if(indices.count(val)>0) return false;
    int index = nums.size();
    nums.emplace_back(val);
    indices[val] = index;
    return true;
}

bool remove(int val) {
    if(indices.count(val)==0) return false;
    int index = indices[val];
    int last = nums.back();
    nums[index] = last;
    indices[last] = index;

    nums.pop_back();
    indices.erase(val);
    return true;
}

int getRandom() {
    std::uniform_int_distribution<int> dis(0,nums.size()-1);
    return nums[dis(gen)];
}
};

/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/

注：你也可以使用传统的随机数：

c
 RandomizedSet() {
        srand((unsigned)time(NULL));
 }

 int getRandom() {
        int randomIndex = rand()%nums.size();
        return nums[randomIndex];
}

参考引用 ​

  1. cplusplus官网
  2. C++11带来的随机数生成器
  3. c/c++产生随机数

用心记录，持续成长

Copyright © 2026 hswsp