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

むらたです。

yugui さんのおかげでこのスレに気付けました。ありがとうございます。

# Math/Random の話しが長くなったので、引用を前後させます。

On 2010/12/19, at 21:15, Yugui wrote:

> 2010/12/19 Masaya TARUI <[e-mail]>:
>>> じゃあ反対ないので実装はともかく、この仕様は基本入れる方向で考えましょう。反対の人は意思表示お早めに。
>> 仕様が詰められていないと思うので、そういう意味で消極的反対です。
> 
> 同意見です。仕様をもっとよく考えるべきです。
> 
> ニーズについては頷けるので、何らかの形で分布関数を与えることには異論はありません。
> ここで、幾つかの考慮すべきことがあります。
> * 効率的な実装の可能な仕様であるべきです。
> * [ruby-dev:41918] 非復元抽出の要望が入るとすれば、その要望と衝突せず、整合性を持つ仕様である必要があります。

復元抽出が可能なようにする方法として replace キーワードが分かりにくいという
意見が出ていたので、成瀬さんが提案しているように choice メソッドとして
提供する方法が良いのではないかと。


>  * mrknさんの考えるArray#sampleの仕様も聞きたいです

抽出数が小さいならば、後述する確率情報源クラスを用いても、
Ojima さんが欲しがっている Array#sample を用いても、
計算コストはそんなに変わらないでしょう。
ですから、私は導入することに反対ではありません。
その代わりインターフェイスで以下の提案があります。

Ojima さんが欲しがってる「n標本だけの重み付き抽出」を Array#sample で対応するなら、
次のようにすると良いのではないでしょうか。

- Array#sample では重みを配列かハッシュで受け取る。
- Array#sample_by を用意し、後置ブロック経由で重みを与えられるようにする。

後者は、sort_by などとの対応で、Array#sample が後置ブロックを受け付けるより
分かりやすいと思っています。

田中さんが非復元抽出用の効率良いアルゴリズムを探してくれているので、
複数個の抽出を実装して良いと思います。抽出後の重みは 0 とする事が
最も一般的なのではないかと思います。

n がある程度大きい場合は Walker のアルゴリズムを採用したほうが効率が良いはずです。
アルゴリズムを切り替えるための閾値の調査などが必要になるでしょうね。
Walker のアルゴリズムは昔 boost 用に作ったことがあります。
それは CodeRepos の http://bit.ly/eAk1M1 ここに置いてあるのですが、
必要なら私が実装しても構いません。

あとは、例えば
- 重みが事前に規格化されている事を伝える方法
- 重みが累積値になっている事を伝える方法
- 重みがソートされている事を伝える方法
などがあれば、それぞれの場合に適したアルゴリズムを切り替えられるんでしょうけど、
後述するように Array#sample の役割としては荷が重すぎる気がするので、
私はここまで複雑にしなくて良だろうと考えています。



以下 Random について。

> * mrknさんのMath/Random構想を考慮して欲しいです。あちらで提供される分布実装と整合性を持つ仕様であって欲しいです。

私が作っている Math/Random は、
- 一様乱数生成器
- 一様乱数生成器を受け取って乱数を一つ生成する分布関数
の二種類で構成されます。
仕様は基本的に boost の random ライブラリに習っています。

使い方の例:

  gen = Math::Random::SFMT216091.new  # Random.new に相当
  gen.()  # 生成器が直接サポートする型と範囲の乱数を生成
  gen.int(min, max)  # [min, max] の一様分布整数乱数を生成する
  gen.real  # [0, 1) の一様分布乱数を倍精度 (53-bit) で生成

  ndist = Math::Random::NormalDistribution.new(0, 1)  # 標準正規分布
  ndist.(gen)  # 標準正規分布に従う乱数を生成

こういう使い方なので、そのまま組み込み Random クラスの代わりにできるように
今はなってないです。

# ここで動くコードを見せられたらカッコ良かったんですが、残念ながら今はコンパイルできません。
# 以前 TypedData に対応させようとして色々と弄ったあげくに TypedData が使えない事を悟り、
# そのまましばらくのあいだ放置してしまっている状況です。

当然のように Walker のアルゴリズムによる離散分布も実装しているんですが、
これを Array#sample で使うためには Array#sample が「呼び出したら添字を返すモノ」を
乱数生成器の代わりに受け取って使えるようになる必要があります。

以前復元抽出を提案したときは Walker のアルゴリズムを実装して
重み付き抽出の追加機能を提案しようと考えていました。
しかし、今では Array#sample はこれ以上複雑にできないだろうなと考えるに
至っています。入れたとしても復元抽出くらいだろうと :P

上のように考えるに至った理由は次のとおりです。

同一条件での連続した抽出を高速に実現するには、遠藤さんが指摘されているように、
母集団をソートしたり Walker のアルゴリズムのように作業用データを準備したりする
必要があります。準備のための計算コストを考えると、そのような準備済みの状態を
オブジェクトにして取り出して使い回せる仕組みが欲しくなります。
そして、その準備済みの状態は母集団から切り離せないものですから、
結局のところ「抽出器」として母集団となる配列なりハッシュなりを含む
オブジェクトが必要になるということですね。

Array#sample は、そのような準備を隠してしまうメソッドです。
ですから、複数回の呼び出しで複数個の抽出を高速に行なう用途には向いてません。
同様に GNU R の sample 関数も複数回の呼び出しには最適化できてないです。
遠藤さんが [ruby-dev:42817] で言及してる事を Array#sample に求めるのは得策じゃないです。

高速な無作為抽出が必要なら、Array や Hash のメソッドとしてではなく、
確率情報源クラスとして抽出器を実装する必要があります。
だから、「Array#sample は遅いものだ」というお墨付きがあるなら、
最低限だけできるようにして「遅いのが嫌なら自分で実装してね」で良いと思います。

と、ここまで書いていて気付きましたが、[ruby-dev:42829] で言及されている
成瀬さんの sample_each は上で書いた「抽出器」を生成するメソッドになってるんですね。
このアイデアはとても素晴しいと思います。


--
Kenta Murata
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54  98C1 CEFE 8AFB 6081 B062

本を書きました!!
『Ruby 逆引きレシピ』 http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: [e-mail]
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/