同僚がそのような処理を実装していた。

問題設定はこうだ。リストのなかに複数の要素がふくまれている。それぞれの要素は重みづけされている。重みの大きいものがより高い確率になるように、ランダムに要素をひとつ抽出したい。例えば要素の重みがすべておなじならば、たんなるランダムピックアップになる。

ではどうするか。すべての重みの総和の範囲で乱数を生成する。リストを前かみていき、乱数から要素の重みをひとつづつひいていく。はじめて乱数が 0 以下になったら、そのときの要素をピックアップすれば良い。

たとえば次のリストを考える。要素の数値は重みをあらわす。

[10, 3, 1]

重みの総和の範囲の乱数をだす。今回の場合は 1 - 14 の範囲の乱数がほしい。bash ならばこんなかんじだ。

$ echo $(($RANDOM % 14 + 1))

この結果が 11 だとする。リストを先頭から見ていく。乱数から重みを引く。11 - 1 = 1。まだ正の数なので次へ。1 - 3 = -2。0 以下なのでこの要素をピックアップする。こんかいは 2 番目の要素が選ばれた。

これはつぎのように、要素ごとに重みを考慮した領域をひろげて、

--------------------
|     10     | 3 |1|
--------------------

このなかから等確率でひとつの数値を選び、それが属する要素を抽出する。直感的な理解はこんなかんじだろう。

短くコードがかけてなるほどなとおもった。自分ならどう実装するだろうとかんがえたが、このアルゴリズムにひっぱられたのか、この方法以外が思いつけなかった。あいかわらず発想がとぼしい。