概要

重み付き乱択アルゴリズムは結果に偏りのある抽選で

ソシャゲのガチャのようにレアリティによって出現確率を変えたい
リクエストを重み付けして分散したり、A/Bテストで99:1のように振り分けたい

といった用途で使えます。

今回はその説明と実装方法の紹介を行います。

環境

Go 1.19.1
Python 3.9.11

Weighted Random Selection

重み付き乱択のイメージとしては以下のようにいくつかの重みがある中で、0〜重みの合計値の範囲でランダム値を生成してどの重みにヒットしたかを返します。

図ではランダム値34が出たため、item Cが結果として返ります。

探索アルゴリズム

またランダム値とこの重みの探索についてもいくつかのアルゴリズムがあります。

こちら↓のサイトでそれぞれデモができます。

A Faster Weighted Random Choice – Naming Things

liner scan

forループで先頭から走査する方法です。

binary search

二部探索で走査する方法です。

パフォーマンス

アルゴリズムによってパフォーマンスが大きく変わるので、重みの数が10を超える場合はHopscotchやBinary searchで実装する必要があります。

ref: https://blog.bruce-hill.com/a-faster-weighted-random-choice

実装

Pythonの場合

numpyを使えばすぐに実現できます。
ただし重みの合計を1にする処理をしておく必要があります。

import numpy as np

np.random.choice(5, 10, p=[0.1, 0, 0.3, 0.6, 0])

ref: numpy.random.choice — NumPy v1.23 Manual

5つの要素[0, 1, 2, 3, 4]に対し、重みを[0.1, 0, 0.3, 0.6, 0]と付けています。

実行結果

第２引数に試行回数になるので今回だと10回となります。

>>> np.random.choice(5, 10, p=[0.1, 0, 0.3, 0.6, 0])
array([3, 2, 2, 3, 3, 0, 2, 3, 3, 2])

期待通りほぼ3と2になりました。

Goの場合

liner scanで実装すると以下のようになります。

var weights = []int{
    10, // item A
    20, // item B
    30, // item C
    40, // item D
}

func main() {
    bs := NewBoundaries(weights)
    result := make([]int, len(weights))

    n := 10000
    for i := 0; i < n; i++ {
        v := rand.Intn(bs.last())
        boundaryIndex := bs.search(v)
        result[boundaryIndex]++
    }
    for _, v := range result {
        pcnt := float64(v) / float64(n) * 100
        fmt.Printf("%.3f\n", pcnt)
    }
}

ref: https://go.dev/play/p/EdjXiAHi9_S

ポイントは以下です。

重み(weight)から境界値(boundary)を設定する
rand.Intn(max)で[0, max)（0以上、maxより小さい）な値を生成
値が境界値のどこに属するかを線形探索チェック

Boundaries周りの実装は以下の感じです。

type Boundaries []int

func NewBoundaries(w []int) Boundaries {
    sort.Ints(w)

    b := make([]int, 0, len(w)+1)
    for i, v := range w {
        if i == 0 {
            b = append(b, v)
            continue
        }
        next := b[i-1] + v
        b = append(b, next)
    }
    return b
}

// search returns boundary index which given value belongs.
func (bs Boundaries) search(val int) int {
    for i, b := range bs {
        if val < b {
            return i
        }
    }
    return 0
}

// last returns boundaries last value.
func (bs Boundaries) last() int {
    return bs[len(bs)-1]
}

結果

重みと同じくらいの確率になりました。

その他

外部ライブラリ

ざっと調べた感じ以下のライブラリがstarが多かったです。

github.com

まとめ

重み付き乱択の説明と、GoやPythonでの実装について説明しました。

ライブラリを使う際は探索アルゴリズムによってパフォーマンスが大きく異なる点に注意して選定すると良いです。

Carpe Diem

備忘録

重み付き乱択を行う

概要

環境