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

遠藤です。

2010年12月20日1:27 Yoji Ojima <redmine@ruby-lang.org>:
> 私個人としては高速性に興味はなく、最初のサンプルのような処理を標準機能の範囲で簡潔に記述することができさえすれば満足です。

係数レベルの性能には私も大して興味ないんですが、オーダが違うとなると
さすがに気になります。特に、機能的には O(log n) で実現できるのに、
見た目の都合で API を O(n) にしか実装できないよう制約してしまおうと
いう話ですから。記述性の話もよくわかるので、悩ましいところですが。

R や Matlab などがこぞって O(n) の API を採用していることから、重み
付きサンプリングをしたいユースケースでは母集団はそんなに大きくない
ことが多いのでは、という予感がしてきています。
この事が確かめられれば、O(n) でもいいかなと思うんですが……。


> 単純な復元抽出に関しては (1..n).map { ary.sample } で代替できるので不要という意見に同意します。しかし同時に、重み付き抽出に関しては同様にシンプルな代替方法がありませんから、同じ考え方でこちらは必要と言うことも可能かとも思います。

いやいや、簡単に書けないからといって片っ端から機能追加で解決していく
わけには行かないでしょう。
あと、復元抽出なしなら Walker's method の選択肢は消えます。



n 個の母集団から m 個を復元抽出する場合の計算量をまとめておきます。

  1. 元提案の API で、線形探索で実装すると O(n * m)

  2. 元提案の API で、二分探索で実装すると O(n + m log n)

  3. 元提案の API で、Walker's method で実装すると O(m + n)

  4. [ruby-dev:42794] の API で、二分探索で実装すると O(m log n)

m << n の場合は、1 から 3 は O(n) 、4 は O(log n) 。
m >> n の場合は、どれも O(m) 。

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