c++ - 生成一个范围内的随机数，其中的百分比为特定值

Question

我需要创建大型(请参阅下文的详细信息)随机图来比较 Dijkstra、Bellman-Ford 和 Floyd 算法在最短路径图遍历方面的性能。我将邻接存储在一个数组中。到目前为止，我在顶点之间生成了随机权重，并用 0 填充了主对角线。我也有关于主对角线的对称性(我假设图形是无向的但不一定完全连接)。

随机值在 0 - 24 左右的范围内，使用 rand() % 25 生成。问题是我希望图表更稀疏(即边缘更少)。有没有一种方法可以生成一个范围内的随机数，并且生成的数字中大约有 1/3 到 1/2 是特定值？请注意，随机分布对于我正在做的事情并不是很重要...

另一个问题:我应该测试多大的图表才能看到性能差异？ 10个顶点？ 100？ 1000？ 10000000？

Answer 1

C++ 提供了 discrete_distribution 和 uniform_int_distribution 类，它们共同实现了您想要的。示例如下:

#include <random>
#include <iostream>

template<typename rgen>
int custom_random_int(rgen& mt) {
    // Returns 0 at a 1/3 chance, 1 at a 2/3 chance
    std::discrete_distribution<> d({1, 2});
    // Uniform distribution of integers in [0, 24]
    std::uniform_int_distribution<> ud(0, 24);
    if (d(mt) == 0) {
      // Return 0 at 1/3 chance
      return 0;
    } else {
      // Output a random number at 2/3 chance
      return ud(mt);
    }
}

int main() {
    // Fixed seed of 1 for demonstration purposes
    std::seed_seq ss{ 1 };
    std::mt19937 mt(ss);
    for(int i = 0; i < 100; i++) {
           std::cout << custom_random_int(mt) << std::endl;
    }
}