kenju's blog

About Programming and Mathematics

"Weighted Random Sampling (2005; Efraimidis, Spirakis)"

ランダムサンプリングのお話。

課題

配列の中から、ランダムに値を選択したい。 その際、必要に応じて重み付けしたい。

実用例

広告配信サーバーにおいて、ランダムにクリエイティブを選択したいときとか。

解決策の一つ

"Weighted Random Sampling (2005; Efraimidis, Spirakis)"

に乗っている"Algorithm A"のアルゴリズムが参考になる。

Pseudo Code

$$ \text{ For each }v_i \in V, u_i = random(0, 1)\text{ and }k_i = u_i \\ \text{ Select the }m\text{ items with the largest keys }k_i\text{ as a } WRS $$

PoC Implementation

def weighted_random_sampling(array)
  array.max_by { |elem| 
    rand ** (1.0/yield(elem)) 
  }
end

Usage:

data = [10, 20, 30]
p weighted_random_sampling(data) { |val| val * 0.5} #=> randomly print out 10, 20 or 30