루비 가중치 랜덤

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 )

  1. 루비 Enumarable 문서를 참고. ↩︎

Juyeong Lee

Read more posts by this author.