c++去重函數，C++ 偏微分數值計算庫_ESYSim仿真器介紹之一 C++庫介紹

本文檔介紹在ESYSim仿真器中使用到的C++標準庫或第三方庫。

偽隨機數產生器

偽隨機數產生器是仿真器中非常常用的組件，比如片上網絡中的負載產生器、片上網絡中的隨機仲裁器等。評價偽隨機數的指標通常是重復周期，重復周期越長越好。同時，偽隨機數的概率分布也很重要的。對于仿真器來說，偽隨機數產生器需要在兩個方面優化：

• 在完整仿真過程中，偽隨機數序列都不發生重復。
• 當偽隨機數足夠多之后，偽隨機數的概率分布趨近于期望的概率分布。
• 偽隨機數的序列是確定的，即給定相同的種子，偽隨機數序列可以復現。

c++去重函數，C語言的stdlib.h 中提供了rand函數用來產生[0, RAND_MAX)范圍內的整形偽隨機數。這是C語言ANSI標準中提供了唯一偽隨機數產生函數。

為了彌補C/C++語言在偽隨機數方面的缺陷，Boost庫提供了比較豐富的偽隨機數生成函數庫boost/random。在C++11標準中，這個庫從Boost庫引入STL庫中，頭文件為#include <random>。

與C語言不同，C++11的隨機數生成器包含隨機數產生器和隨機數分布兩個部分。根據隨機數的生成方法，隨機數產生器包括利用硬件隨機數產生器構建的隨機數設備random_device，利用算法生成偽隨機數的生成器（線性同余、梅森糾纏以及借位減法），以及通過調整偽隨機數序列的偽隨機數生成器（消除塊和洗牌排序）。每一種生成器都可以通過設置種子來復現偽隨機序列。

• 線性同余引擎（LCG）linear_congruential_engine。預設產生器minstd_rand0和 minstd_rand。
• 梅森糾纏引擎（Mersenne Twister）mersenne_twister_engine。預設產生器 mt19937和 mt19937_64。
• 借位減法引擎（Subtract with carray） subtract_with_carry_engine。預設產生器ranlux24_base和 ranlux48_base。
• 消除塊引擎（Discard）discard_block_engine 。預測產生器ranlux24和ranlux48。
• 洗牌排序引擎（Shuffle）shuffle_order_engine。 預測產生器knuth_b。

C++11提供的隨機數分布包括均勻分布、伯努利分布（二項分布）、泊松分布、正態（高斯）分布以及采樣分布。如果需要使用隨機數分布，首先利用隨機數產生器得到一個均勻分布的隨機數；然后再通過隨機數分布映射到需要的概率分布。

• 均勻分布：uniform_int_distribution（整數均勻分布）和 uniform_real_distribution（浮點均勻分布）。
• 伯努利分布：bernoulli_distribution、binomial_distribution、negative_binomial_distribution、geometric_distribution 。
• 泊松分布：poisson_distribution、exponential_distribution、 gamma_distribution、 weibull_distribution、 extreme_value_distribution。
• 正態分布：normal_distribution 、lognormal_distribution 、chi_squared_distribution、cauchy_distribution、fisher_f_distribution、student_t_distribution。
• 采樣分布：discrete_distribution、piecewise_constant_distribution、 piecewise_linear_distribution。

ESYSim中的randgen模塊

目前推薦的c++標準 虛構造函數、ESYSim中的randgen模塊用來為仿真過程產生隨機數。這個模塊的C++源文件和SWIG文件在路徑srcs/rangen中；python封裝和測試文件在路徑python/randgen。

使用randgen模塊，需要創建EsyRandGen對象。創建EsyRandGen對象需要制定隨機數的種子和隨機數的生成算法。

EsyRandGen(long a = 1, RandGenAlg alg = C11_DEFAULT);

隨機數的生成算法用枚舉變量RandGenAlg表示。EsyRandGen選擇對應的C++11隨機數生成器產生隨機數。 RandGenAlg定義如下。

    enum RandGenAlg{C11_DEVICE = 1,C11_MINSTD_RAND0 = 2,C11_MINSTD_RAND = 3,C11_MT19937 = 4,C11_MT19937_64 = 5,C11_RANLUX24_BASE = 6,C11_RANLUX48_BASE = 7,C11_RANLUX24 = 8,C11_RANLUX48 = 9,C11_KNUTH_B = 10};

如果創建EsyRandGen對象時提供的alg不屬于上面的枚舉類型，則EsyRandGen采用C語言標準定義的rand函數產生隨機數。

EsyRandGen對象提供兩類分布：均勻分布和高斯（正態）分布。由于C++是強類型語言，EsyRandGen提供了不同的函數用來產生不同數據范圍的隨機數。

• 生成均勻分布的函數如下：

double flatDouble(double low, double high);
long flatLong(long low, long high);
unsigned long flatUnsignedLong(unsigned long low, unsigned long high);
unsigned long long flatUnsignedLongLong(unsigned long long low, unsigned long long high);

每一個函數產生在[low, high)之間的一個隨機數。

• 生成高斯分布的函數如下：

double gaussDouble(double mean, double variance);
long gaussLong(long mean, double variance);
unsigned long gaussUnsignedLong(unsigned long mean, double variance);
unsigned long long gaussUnsignedLongLong(unsigned long long mean, double variance);

函數產生的高斯分布滿足均值為mean而且方差為variance。

randgen模塊的測試

randgen模塊的測試程序在路徑python/randgen/test.py。 由于使用的是C和C++11官方提供的隨機數生成器，所以我們默認了偽隨機序列的重復性能夠滿足要求，不進行測試。我們著重測試的是生成的隨機序列的概率分布。測試程序采用最為基本的均勻分布的概率分布作為測試項目。

測試程序會測試由不同隨機數生成算法得到的均勻分布的方差和執行速度。測試程序使用flatUnsignedLong產生規定范圍內的整形隨機數。統計產生的隨機數，可以得到每一個數值出現的頻次，對頻次求方差作為均勻分布的方差。

均勻分布的范圍由min_range和max_range確定；每一種隨機數產生算法需要對seed_count種隨機數種子進程測試；每一個隨機數產生算法和隨機數種子的測試需要產生number個隨機數。

根據網絡負載產生的場景，我們假設：均勻分布的范圍是[0, 99)；總共測試50個隨機數種子；并且每組測試的隨機數為100000個隨機數。經過多次測試，C語言標準函數rand以及Minstd_rand0、Ministd_rand、Mt19937和Mt19937_64四種算法的方差接近，一般都是小于0.001。具體數值隨隨機數種子波動。另外5種方法的方差較大，一般都大于0.001。

執行時間上，C語言標準函數rand的執行時間最小；Minstd_rand0、Ministd_rand、Mt19937和Mt19937_64四種算法的執行時間大于rand。另外5種方法的執行時間較大。

此外，我們發現不同算法的最大偏差（某個數值出現的頻次相對于理想均勻分布的頻次的偏差）相對穩定（大于10%），并且無法下降。用于片上網絡仿真器，這是一個較大的缺陷。如果用這樣的隨機數產生通信負載，某個目標地址可能比其他地址少10%的通信流量；或者多10%的通信流程。本人才疏學淺，暫時沒有找到能夠獲得最大偏差更小的隨機數算法。