From: Yusuke ENDOH <mame@...>
Date: 2010-12-20T00:41:22+09:00
Subject: [ruby-dev:42812] Re: [Ruby 1.9-Feature#4147] Array#sample 	で重みを指定したい

遠藤です。

2010年12月19日22:52 Yoji Ojima <redmine@ruby-lang.org>:
>>でも、重みを累積分布として与える例はないですねえ。
>>sample ごときで常に O(n) かかってほしくないと思うのですが。
>
> 復元抽出の高速アルゴリズムである Walker's alias method を使うのに必要な情報は累積分布ではないので、それを引数として与えるというのは、簡便性重視と高速性重視のどちらにも寄らない中途半端な仕様であると考えます。


Walker's alias method を知らなかったので R のソースコード
(http://svn.r-project.org/R/trunk/src/main/random.c) を読んで調べて
みましたが、面白いですね。しかし事前に O(n) のテーブルを作ってしまう
んですね。うーん。

思うに R の sample は、1 個や 2 個ではなくすごく大量のサンプリングを、
一括して行うことが前提となっているような気がします。つまり、

  - 母集団の大きさ << 取り出したい数、である
  - 何度も sample を呼ばず、最初に必要なだけサンプリングする
    - なので O(母集団の大きさ) はかかってもよい

というユースケースを想定している。

Ruby でも同じ使われ方が期待できるんですかねえ。
いよいよ、まずは gem で作って配布して、多くの需要があることがわかった
ら取り込む、という手順を踏むほうがいいような気がしてきました。

-- 
Yusuke Endoh <mame@tsg.ne.jp>