Ruby Weighted Random
랜덤
배열을 무작위로 섞는 방법은 루비 기본 API에서 제공한다
[a, b, c].shuffle # => [c, a, b]
[a, b, c].sample # => b
shuffle을 통해 섞거나, sample을 통해 추출 할 수 있다.
가중치 랜덤
이때 각 값의 가중치(weight)를 다르게 적용하려면?
쓸만한 gem이 없어서 만들어 보았다.[1] (github.com/juyeong/wrandom)
ex) a.weight => 1, b.weight => 99
[a, b].wsample { |item| item.weight } #=> b
[a, b].wshuffle { |item| item.weight } #=> [b, a]
99%의 확률로 99가 추출된다.
Algorithm
Weighted random sampling with a reservoir 논문에 나오는 알고리즘
Input : A population V of n weighted items
Output : A WRS of size m
1: For each v₁ ∈ V , u₁ = random(0, 1) and k₁ = u₁ ** (1/w₁)
2: Select the m items with the largest keys k as a WRS
rand ** ( 1.0 / weight )