随机数据生成与对拍

摘要: 随机数据的生成

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

很多时候我们在写出一个解决问题的算法的程序之后，想要验证其正确性。比较直接的方法是构造随机数据，然后将自己的算法与暴力算法的结果是否一致，如果一致就认为自己的算法是正确的。这种算法的关键点是正确地生成随机数据，有了随机数据之后，对比自己的算法与暴力算法的结果这个过程称为对拍。

本文我们首先介绍一下随机整数、随机实数、随机整数数组、随机区间数组、随机树、随机图等常见数据结构的生成方法，附代码模板，然后介绍对拍的过程和代码模板。

随机数据生成

头文件 cstdlib(stdlib.h) 包含 rand 和 srand 两个函数，以及 RAND_MAX 常量。

RAND_MAX 是一个不小于 32767 的整数常量，其值与操作系统，编译器环境有关。一般在 windows 中为 32767，在类 Unix 系统中为 2147483647。

rand() 返回一个 0 ~ RAND_MAX 之间的随机整数。

srand(seed) 接受一个 unsigned int 类型的参数 seed，以 seed 为随机种子。rand 函数基于线性同余递推式生成随机数。随机种子相当于计算线性同余时的一个初始参数，若不执行 srand(seed)，则种子默认为 1。

当种子确定后，接下来的随机数列就是固定的。因此一般在程序开头，以系统时间作为随机种子。

头文件 ctime(time.h) 中包含 time 函数，调用 time(0) 返回从 1970 年 1 月 1 日 0 时 0 分 0 秒(Unix纪元)到现在的秒数。因此初始化随机种子可以这样写

srand((unsigned)time(0));

下面介绍一些随机数据生成的模板。

生成随机数

随机生成 0 ~ n-1 之间的整数

using ll = long long;

ll random(ll n)
{
    return (ll)rand() * rand() % n;
}

int main()
{
    srand((unsigned)time(0));
    ...
}

随机生成 0 ~ x 之间的实数, 小数点后保留 L 位数字

先生成较大的随机整数，再除以 10 的次幂。

double random(double x, const int L)
{
    // 0.0 ~ x 之间的随机实数
    // 小数点后 L 位数字
    ll tmp = random(x * pow(10, L)); // 较大整数
    return (double)tmp / pow(10, L);
}

随机生成 -n ~ n 之间的整数

先生成 0 ~ 2n 的随机整数，然后再减去 n

ll random_with_nega(ll n)
{
    ll tmp = random(n * 2 + 1); // 0 ~ 2n
    return tmp - n;
}

生成整数数列

随机生成 n <= 1e5 个绝对值在 1e9 之内的整数

int n = random((int)1e5); // 随机长度
int m = 1e9;
vector<int> a(n);
for(int i = 0; i < n; ++i)
    a[i] = random_with_nega(m); // 随机值

生成随机区间列

随机生成 m 个 [0, n - 1] 的子区间。

vector<vector<int>> ranges(m, vector<int>(2, -1));

for(int i = 0; i < m; ++i)
{
    int l = random(n);
    int r = random(n);
    if(l > r)
        swap(l, r);
    ranges[i][0] = l;
    ranges[i][1] = r;
}

生成随机树

随机生成一棵 n 个点(编号 1 ~ n)的树，用 n 个点 n - 1 条边的无向图形式输出，每条边附带一个 [0, 1e9] 的权值。

int n = 1e3;
int m = 1e9;

vector<vector<int>> g(n + 1, vector<int>(2, -1));

for(int i = 2; i <= n; ++i)
{
    // 从 2 ~ n 之间的每个点 i 向 1 ~ i-1 之间的点随机连一条边
    int fa = random(i - 1) + 1;
    int val = random(m + 1);
    g[fa][0] = i;
    g[fa][1] = val;

}

生成随机图

随机生成一个 n 个点(编号 1 ~ n)，m 条边的无向图，图中不存在重边、自环，且必须连通。

保证 5 <= n <= m <= n * (n - 1) / 4 <= 1e6

int m = 1e6 + 5;
pair<int, int> e[m]; // 边表
map<pair<int, int>, bool> h; // 防止重边

// 先生成一棵树，保证连通
for(int i = 1; i < n; ++i)
{
    int fa = random(i) + 1; // 给 i + 1 找一个 [1..i] 中的随机父节点
    e[i] = make_pair(fa, i + 1);
}

// 在生成剩余的 m - n + 1 条边
for(int i = n; i <= m; ++i)
{
    int x, y;
    do{
        x = random(n) + 1;
        y = random(n) + 1;
    }while(x == y || h[make_pair(y, x)]);
    e[i] = make_pair(x, y);
    h[e[i]] = h[make_pair(y, x)] = 1;
}

// 随机打乱，输出
random_shuffle(e + 1, e + m + 1);

---

特殊数据生成

在树、图结构中，有三类特殊数据常用于对程序进行极端状况下的效率测试。

(1) 链型数据

链型的数据会增大递归深度，这是点分治等算法需要特别注意的数据。

(2) 菊花型数据

以 1 号节点为中心，2 ~ N 与 1 连边，最终 1 号节点的度数为 N - 1。缩点等图论算法若处理不当，容易在这类数据上退化。

(3) 蒲公英型数据

链型和菊花型数据的综合，令数的一部分构成链，一部分构成菊花，再把两部分连接。

在以上三种数据的基础上，再添加少量随机边，即可得到一张包含局部特殊结构，又不失一般性和多样性的图。

---

对拍

假设我们已经写好了三个程序。

• 暴力解法 bf.cpp, 输入 data.in，输出 data.out
• 我的解法 sol.cpp, 输入 data.in，输出 data.ans
• 随机数据生成 random.cpp, 输出 data.in

依次编译这三个程序得到三个可执行文件 bf.out, sol.out, random.out。

现在只需要写一个脚本，循环执行以下过程。

./random.out > data.in
./bf.out <data.in >data.ans
./sol.out <data.in >data.out
diff data.out data.ans

下面是 Linux 下 C++ 的对拍程序。cstdlib(stdlib.h) 中有一个函数 system，它接受一个字符串参数，并把该字符串作为系统命令执行。

int main()
{
    for(int T = 1; T <= 1e4; ++T)
    {
        system("./random.out");
        // 当前程序已经运行的 CPU 时间，Unix 下单位是 s
        double st = clock();
        system("./sol.out <data.in >data.out");
        double ed = clock();
        system("./bf.out <data.in >data.ans");
        if(system("diff data.out data.ans"))
        {
            puts("Wrong Answer");
            // 程序立即退出，data.in 是发生错误的数据
            return 0;
        }
        else
            printf("Accept, 测试点 #%d, 用时 %.01fms\n", T, ed - st);
    }
}

---