무게를 달고 무작위로 무언가를 내고 싶습니다.

광고나 가챠라든지 여러가지 곳에서 무게를 달고 무작위로 뭔가 내고 싶을 때가 있습니다. 이런 것을 '가중 난택 알고리즘'이라고 말하는 것 같습니다.

이러한 경우에 자주 하는 것은 가중치만큼 요소를 준비해, 배열에 넣어 두고, 요소수 미만의 난수를 인덱스로 해 액세스 하는 것도 자주(잘) 보입니다. 그러나 이 방법에서는 가중치는 정수만 지정할 수 있습니다. 실수로 가중치를 지정하려면 어떻게 해야 합니까?

이번 구현으로서 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




[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분 트리 탐색이 좋은지 선형 탐색이 좋은가는 어플리케이션의 사양으로부터 생각합시다.