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

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;
    }
}

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

generate random numbers within a range with a percentage of them a specific value

c++

random

algorithm

graph-algorithm