首頁猿問加權(quán)隨機數(shù)

加權(quán)隨機數(shù)

C++

開心每一天1111 2019-07-08 17:27:25

加權(quán)隨機數(shù)我在嘗試實現(xiàn)一個加權(quán)隨機數(shù)。我現(xiàn)在只是把頭撞在墻上，弄不明白。在我的項目中，我使用的是Boost的隨機函數(shù)(保持手范圍，主觀的全股權(quán)分析)。那么，假設(shè)我想選擇一個介于1到3之間的隨機數(shù)(所以要么是1，2，要么是3)。Boost的Mersenne旋風(fēng)發(fā)生器工作起來就像一種魅力。但是，我希望對這個選項進(jìn)行加權(quán)，例如：1 (weight: 90) 2 (weight: 56) 3 (weight: 4)Boost有某種功能嗎？

查看完整描述

3 回答

開滿天機

TA貢獻(xiàn)1786條經(jīng)驗獲得超13個贊

有一個簡單的算法可以隨機挑選一個項目，其中項目有單獨的權(quán)重：

1)計算所有權(quán)重之和。

2)選擇一個0或更大且小于權(quán)重之和的隨機數(shù)。

3)一次只檢查一項，從你的隨機數(shù)中減去它們的權(quán)重，直到得到隨機數(shù)小于該項目重量的項目為止

偽代碼說明了這一點：

int sum_of_weight = 0;for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];}int rnd = random(sum_of_weight);for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];}assert(!"should never get here");

這應(yīng)該是直接的，以適應(yīng)您的Boost容器和諸如此類。

如果您的權(quán)重很少更改，但您經(jīng)常隨機選擇一個，并且只要您的容器存儲指向?qū)ο蟮闹羔?，或者超過幾十個項(基本上，您必須了解這是否有幫助或阻礙)，那么就會有一個優(yōu)化：

通過在每個項目中存儲累積權(quán)重和，可以使用二進(jìn)制搜索選擇與拾取重量相對應(yīng)的項目。

如果您不知道列表中的項目數(shù)，那么有一個非常簡潔的算法儲層取樣可以調(diào)整為加權(quán)。

反對回復(fù) 2019-07-08

犯罪嫌疑人X

TA貢獻(xiàn)2080條經(jīng)驗獲得超4個贊

如果你的重量變化比畫的慢，C+11discrete_distribution將是最簡單的：

#include <random>#include <vector>std::vector<double> weights{90,56,4};std::discrete_distribution<int> 
dist(std::begin(weights), std::end(weights));std::mt19937 gen;gen.seed(time(0));
//if you want different results from different runsint N = 100000;std::vector<int> samples(N);for(auto & i: samples)
    i = dist(gen);//do something with your samples...

但是，請注意，c+11discrete_distribution計算初始化時的所有累積和。通常，您需要這樣做，因為它加快了采樣時間的一次O(N)成本。但是，對于快速變化的分布，它將招致沉重的計算(和內(nèi)存)成本。例如，如果權(quán)重表示有多少項，并且每次繪制一個項時，您都會刪除它，您可能需要一個自定義算法。

威爾的回答https://stackoverflow.com/a/1761646/837451避免了這種開銷，但是比C+11更慢，因為它不能使用二進(jìn)制搜索。

要看到它這樣做，您可以看到相關(guān)的行(/usr/include/c++/5/bits/random.tcc在我的Ubuntu 16.04+GCC 5.3安裝上)：

  template<typename _IntType>
    void
    discrete_distribution<_IntType>::param_type::
    _M_initialize()
    {
      if (_M_prob.size() < 2)
        {
          _M_prob.clear();
          return;
        }

      const double __sum = std::accumulate(_M_prob.begin(),
                                           _M_prob.end(), 0.0);
      // Now normalize the probabilites.
      __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
                            __sum);
      // Accumulate partial sums.
      _M_cp.reserve(_M_prob.size());
      std::partial_sum(_M_prob.begin(), _M_prob.end(),
                       std::back_inserter(_M_cp));
      // Make sure the last cumulative probability is one.
      _M_cp[_M_cp.size() - 1] = 1.0;
    }

反對回復(fù) 2019-07-08