时间戳

首页 > 解决方案 > 生成范围内的随机数，其中百分比为特定值

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

问题描述

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

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

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

标签： c++algorithmrandomgraph-algorithm

解决方案

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

推荐阅读