[ruby-dev:42821] Re: [Ruby 1.9-Feature#4147] Array#sample で重みを指定したい

遠藤です。

2010年12月20日14:06 Yoji Ojima <[e-mail]>:
>>係数レベルの性能には私も大して興味ないんですが、オーダが違うとなると
>>さすがに気になります。特に、機能的には O(log n) で実現できるのに、
>>見た目の都合で API を O(n) にしか実装できないよう制約してしまおうと
>>いう話ですから。記述性の話もよくわかるので、悩ましいところですが。
>
> メソッド自体が高速であっても、そのために累積分布を渡す必要があるというのでは、たとえば要素の重みを一つだけ変えて再抽選というときには Ruby 側で累積分布を再計算しなければならず、逆に遅くなる状況もありえます。

それこそ係数レベルの性能の話ですよね。


> 総合的に見て、ご提案のインタフェースが有利な状況は限られており、汎用性に欠けるのではないかと考えます。

「重みを変えずに繰り返し抽選したい」というユースケースで有利になる
んですが、汎用性に欠けますかね。結構ありそうだと思うんですが。
「頻繁に重みを変えて再抽選したい」というユースケースでも、オーダが
悪くなるわけではないですし。


> 復元抽出に関しては、単体では「本当に必要なの」と言われてしまったものの、重み付き抽出との組み合わせで特定のケースでは高速なアルゴリズムが使用可能であること、R と同様のインタフェースにすることで両方使う人が便利であること等のメリットが整理されれば、まつもとさんの判断も違ってくる可能性があるかと思います。

そうですね。

-- 
Yusuke Endoh <[e-mail]>