23
18

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

重みをつけてランダムに何か出したい

Posted at

広告とかガチャとか色々なところで重みをつけてランダムに何か出したいというときがあります。こういうのを『重み付き乱択アルゴリズム』とかって言うらしいです。

こういうときによくやるのは重みの分だけ要素を用意して、配列にいれておき、要素数未満の乱数をインデックスにしてアクセスするみたいなこともよく見ます。しかしこの方法では重みは整数しか指定できません。実数で重みを指定したい場合はどうすればいいのでしょうか。

今回実装としてCPANモジュールのData::WeightedRoundRobinを参考にしました。

lib/Data/WeightedRoundRobin.pm - metacpan.org

参考にした実装では重みの合計が1である必要はありません。しかし結局重みの合計値を計算する必要があるので、合計値が1という前提にして説明します。合計値が1でない場合は重みの合計値倍すれば大丈夫です。実数値の場合、合計値が正確に1になることはほぼない(すべて2進数で表現できて、かつ極端に小さいものがない場合は大丈夫)ですが、特に問題ありません。

今回はしきい値となる値を用意します。しきい値として最初の要素に0、その後の要素のしきい値には今までの要素の重みの和を与えます。

具体的に説明します。重みを0.2,0.3,0.4,0.1とします。その場合しきい値は下のようになります。

重み しきい値
0.2 0
0.3 0.2
0.4 0.5
0.1 0.9

スクリーンショット 2016-01-10 20.39.57.png

[0,1)の間の乱数を出力して、しきい値が大きい順に見ていって、用意した乱数がしきい値以上かどうかを判定します。しきい値以上ならその要素を選択するようにします。Goならrand.Float64()を使うと[0,1)の間の乱数を出力できます。

randomized_test.go
package randomized

import (
    "math/rand"
    "testing"
    "time"
)

type weight struct {
    weight    float64
    threshold float64
    count     int
}

func BenchmarkRandomized(b *testing.B) {
    b.StopTimer()

    lists := []*weight{&weight{weight: 0.2}, &weight{weight: 0.3}, &weight{weight: 0.4}, &weight{weight: 0.1}}

    totalW := 0.0
    for _, v := range lists {
        (*v).threshold = totalW
        totalW += v.weight
    }

    rand.Seed(time.Now().UnixNano())

    b.StartTimer()

    for i := 0; i < b.N; i++ {
        random := rand.Float64()
        for i := len(lists) - 1; i >= 0; i-- {
            if lists[i].threshold <= random {
                lists[i].count++
                break
            }
        }
    }
}

一応最初に説明した重みを整数にして重みの分だけ要素を用意する実装との速度比較をしたかったのでGoで用意してみました。

go test -bench .と実行すると比較することができます。

また要素数が増えたときは2分木探索をした方が速いです。今回参考にしたCPANモジュールのData::WeightedRoundRobinではデフォルトで要素数が10以上なら2分木探索になります。そこでどれくらいのサイズで速度は逆転するのか以前に調べました。

golang - 線形探索ではなく2分木探索した方がいいサイズってどれくらいなのか - Qiita

記事にも書いたように実際には線形探索だと最悪実行時間が長いです。2分木探索がいいのか線形探索がいいのかはアプリケーションの仕様から考えましょう。

23
18
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
23
18

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?