Feature #4147: Array#sample で重みを指定したい

• Status: Feedback
• Assignee: -
• Target version: -

[oj (Yoji Ojima)]

=begin
Array#sample にブロックを渡したとき、ブロックの戻り値を要素の重みとして使用するのはいかがでしょうか。

下記のサンプルで、"大吉" が "凶" の 1000 倍の確率で選択されるようにしたいです。

omikuji_box = [
{:name => "大吉", :weight => 1000},
{:name => "中吉", :weight => 100},
{:name => "小吉", :weight => 10},
{:name => "凶", :weight => 1}
]
omikuji = omikuji_box.sample {|v| v[:weight] }
puts omikuji[:name]
=end

[shyouhei (Shyouhei Urabe)]

• Status changed from Open to Feedback

=begin
実装のたたき台があるとなおよいかとおもいます。
まずRubyで同等の処理をするコードを書いてみるというのはどうでしょう。
妥当であれば、取り込まれたり、あるいは高速化のためにCで書きなおされたりするかもしれません。
=end

[sorah (Sorah Fukumori)]

Rubyで実装してみました。あまりコストとか速度は気にしていないので速度は気にせず。

class Array
  def sample(n=1)
    if block_given?
      self.size.times.map do |i|
        Array.new(yield(self[i]), self[i])
      end.flatten.sample(n)
    else
      n == 1 ? self[rand(self.size)] : Array.new(n){ self[rand(self.size)] }
    end
  end
end

# -- テスト

def a
  [1,2,3].sample { |v| v*100 }
end

def b
  [1,2,3].sample { |v| v*100 }
end
ary = 100.times.map{a}
bry = 100.times.map{b}

result_a = {}

ary.each do |i|
  result_a[i] ||= 0
  result_a[i] += 1
end

result_b = {}

bry.each do |i|
  result_b[i] ||= 0
  result_b[i] += 1
end

# aは i*10の重みあり。 bは重みなし。 {i => 出現回数}

p result_a #=> {2=>31, 3=>56, 1=>13}
p result_b #=> {2=>37, 3=>45, 1=>18}

# -- sora_h

[sorah (Sorah Fukumori)]

ミスがあったので訂正。

# -- テスト

def a
  [1,2,3].sample { |v| v*100 }
end

def b
  [1,2,3].sample { |v| v }
end
ary = 100.times.map{a}
bry = 100.times.map{b}

result_a = {}

ary.each do |i|
  result_a[i] ||= 0
  result_a[i] += 1
end

result_b = {}

bry.each do |i|
  result_b[i] ||= 0
  result_b[i] += 1
end

# aは i*10の重みあり。 bは重みなし。 {i => 出現回数}

p result_a #=> {3=>56, 1=>13, 2=>31}
p result_b #=> {2=>34, 3=>46, 1=>20}

# -- sora_h

[oj (Yoji Ojima)]

メソッドの引数を考慮しない簡易的なコードでよろしければ。

class Array
  alias :org_sample :sample

  def sample
    if block_given?
      prob_map = collect {|v| yield(v) }
      rn = rand * prob_map.inject(0) {|r, v| r += v }
      prob_map.each_with_index do |v, i|
        rn -= v
        return self[i] if rn < 0
      end
    else
      org_sample
    end
  end
end

[oj (Yoji Ojima)]

=begin
すみません、入れ違いでした。
=end

[oj (Yoji Ojima)]

=begin
一週間経って特に反対意見はないようですが、実際にパッチを書いたら取り込んでいただけるものなのでしょうか。積極的な賛成がなければダメでしょうか。
=end

[shyouhei (Shyouhei Urabe)]

• Status changed from Feedback to Assigned
• Assignee set to shyouhei (Shyouhei Urabe)

=begin
じゃあ反対ないので実装はともかく、この仕様は基本入れる方向で考えましょう。反対の人は意思表示お早めに。

実装はCで書かれたものがあると取り込まれるまでは早くなる可能性が高いと思います。なければ俺が書くまでお待ちください。
=end

[hasari (Hiro Asari)]

=begin
あさりです。

失礼ですが、これ、標準に入れるほどの需要があるんでしょうか。

積極的に反対という訳ではないですが、「あると便利」くらいだったらgemとかの方が無難だと思います。
=end

[oj (Yoji Ojima)]

=begin
「均一確率での標本抽出は標準で必要だが、その重み指定は不要」とする合理的な理由があるかというのがポイントではないかと考えます。

需要という意味ではさほど違いがあるようには思えませんが、どんなものでしょうか。
=end

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月18日16:20 Yoji Ojima [e-mail]:

一週間経って特に反対意見はないようですが、実際にパッチを書いたら取り込んでいただけるものなのでしょうか。積極的な賛成がなければダメでしょうか。

機能自体には反対ではないものの、API がよくないと思います。
これだと毎回 each することになりますよね。

あまりいい対案がないので黙っていたのですが、どうしてもやるとしたら、

omikuji_box = %w(大吉 中吉 小吉 凶)
omikuji_weight = [1000, 1100, 1110, 1111]

omikuji = omikuji_box.sample(weight: omikuji_weight)

がましかなあと思います。
これなら、重み分布を使い回せますし、最後の値を見れば each しなくても
合計値がとれますし、要素数が多くても二分探索が使えます。

見た目がいまいちなのと、配列の長さが異なる場合や重み分布がソートされて
いない場合などのコーナーケースが気にはなります。
ただ、この機能の用途を考えると、モンテカルロシミュレーションがすごく
出てきそうなので、非効率的にしか実装できない API は避けるべきだと
思います。

--
Yusuke Endoh [e-mail]

=end

[hasari (Hiro Asari)]

=begin
On Dec 18, 2010, at 9:15 PM, Yoji Ojima wrote:

需要という意味ではさほど違いがあるようには思えませんが、どんなものでしょうか。

需要だけが標準に入れるかどうかの物差しである、という意味に取られたのでしたら
私の言葉足らずでした。すみません。

「既に在るものを外す」には「今無いものを入れる」よりも多くの労力が必要だと思うので、
今から入れるものには慎重になるべき、という意味でした。ご理解下さい。

1.9でMath.gammaとMath.lgammaが入って、それをJRubyで実装する際に
ちょっと苦労したのでその時のことが思い出されたのでした。
=end

[hasari (Hiro Asari)]

=begin
ちょっと諄いようですが、私は「積極的に反対」というわけではありません。
=end

[oj (Yoji Ojima)]

=begin

これだと毎回 each することになりますよね。

もちろんそうですが、これはゲームでの利用を意図したもので、毎回と言うほど何度も繰り返し呼び出すことは想定していません。

モンテカルロシミュレーション等、速度が重要な場合は Ruby 自体が選択されないのではないかと思います。
=end

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月19日12:41 Yoji Ojima [e-mail]:

これだと毎回 each することになりますよね。

もちろんそうですが、これはゲームでの利用を意図したもので、毎回と言うほど何度も繰り返し呼び出すことは想定していません。

モンテカルロシミュレーション等、速度が重要な場合は Ruby 自体が選択されないのではないかと思います。

個人的には、そういう場合でも、プロトタイプとしてまずは Ruby で書いて
みますね。それで速度が問題になれば、ある程度最適化を試みて、それでも
ダメなら移植などを考えます。

モンテカルロ法が想定用途でないとすれば、Asari さんの仰るように「需要
がそんなにあるのか？」という点が疑問ですね。
個人的な経験上、等確率のサンプリングはシミュレーション以外の用途でも
数多くやったことがありますが、重み付きのサンプリングがモンテカルロ法
のような用途以外で必要になったケースはほとんど思い出せません。

ちなみに、new feature の採択に必要なのは、積極的な賛成ではなく、matz
の承認です。
多くの人が賛成しても matz がダメと言えば入りません。
多くの人が反対しても matz がいいと言えば入ります。
「多くの人が賛成・反対している」という事実は matz の判断に影響を与え
ると思いますが、それ以上のものではありません。

--
Yusuke Endoh [e-mail]

=end

[mame (Yusuke Endoh)]

=begin
2010年12月19日13:33 Yusuke ENDOH [e-mail]:

ちなみに、new feature の採択に必要なのは、積極的な賛成ではなく、matz
の承認です。
多くの人が賛成しても matz がダメと言えば入りません。

言い直し。

多くの人が賛成しても、matz が「よし」と言わない限り入りません。

卜部さんの [ruby-dev:42791] が、一読すると採択自体はほぼ決定みたいに
読めますが、「パッチがあれば matz の承認が降りやすくなる」という意味
(のはず) です。

--
Yusuke Endoh [e-mail]

=end

[tarui (Masaya Tarui)]

=begin

じゃあ反対ないので実装はともかく、この仕様は基本入れる方向で考えましょう。反対の人は意思表示お早めに。
仕様が詰められていないと思うので、そういう意味で消極的反対です。

複数個取り出すときは重みはどうなるんでしょうか？

現在のsampleの仕様は非復元抽出なので一度取り出されたitemはもう取り出されないのですが、
重みを与える場合の仕様が不明確だと思います。

復元抽出を入れたいという要望は
[ruby-dev:41918] [Feature #3647] Array#sample(n, replace=false)
でされていますが、
matzからは『「本当に必要なの」ってところがですかね。』と言われているので、
誰かが必要性をアピールしないと、入らないと思います。

#3647が入らなかったとして、仕様を考えると大体3通りがあると思います。
1)重みを与えた時は復元抽出にする。
2)取り出されたアイテムの重みを-1する。 (-1以外もあるかもしれませんが)
3)重みと複数個抽出両方与えられたらエラーにする。

と挙げてみたもののどれも今一な仕様に思えます。
もっとよい仕様ないですかね。

後、個人的な感想では重みをブロックで決めるのがスッキリしません。

樽家昌也(Masaya TARUI)
No Tool,No Life.

=end

[shyouhei (Shyouhei Urabe)]

=begin
(2010/12/19 14:02), Yusuke ENDOH wrote:

卜部さんの [ruby-dev:42791] が、一読すると採択自体はほぼ決定みたいに
読めますが、「パッチがあれば matz の承認が降りやすくなる」という意味
(のはず) です。

いや、あの状況ではtrunkに突っ込む気まんまんでしたけどね。なんせ拒否する理由が
なかったし。

まあ反対意見が出てきたことですし、今の時点ではみなさんが合意するかまつもとさん
が入れると言い出さない限りは、私からはアクションは取りません。

=end

[oj (Yoji Ojima)]

=begin

#3647が入らなかったとして、仕様を考えると大体3通りがあると思います。
1)重みを与えた時は復元抽出にする。
2)取り出されたアイテムの重みを-1する。 (-1以外もあるかもしれませんが)
3)重みと複数個抽出両方与えられたらエラーにする。

4. 取り出されたアイテムの重みを 0 にする。

が、もっとも整合性のある仕様ではないでしょうか。
=end

[oj (Yoji Ojima)]

=begin

後、個人的な感想では重みをブロックで決めるのがスッキリしません。

R では重みの配列を引数として渡すようになっているようです。
http://stat.ethz.ch/R-manual/R-devel/library/base/html/sample.html

ブロックが嫌か、または少しでも高速にしたいと考えるなら R と同じ方法でも良いですが、私はブロックを使う方が Ruby らしいし、「引数の意味が何だか忘れる」心配もなくて良いと思います。
=end

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月19日14:06 Masaya TARUI [e-mail]:

#3647が入らなかったとして、仕様を考えると大体3通りがあると思います。
1)重みを与えた時は復元抽出にする。
2)取り出されたアイテムの重みを-1する。 (-1以外もあるかもしれませんが)
3)重みと複数個抽出両方与えられたらエラーにする。

と挙げてみたもののどれも今一な仕様に思えます。

4. 取り出されたアイテムの重みを 0 にする (もう取り出さない)

も考えられます。

いくつか関連調査してみました。

○ R
http://stat.ethz.ch/R-manual/R-devel/library/base/html/sample.html

sample(母集団, 取り出す個数, replace かどうか = false, 重み = nil)

非復元抽出で重みが指定された場合は、取り出されたアイテムの重み
は無視して残りの重みだけで次を取り出す (つまり 4 に相当) 。

○ Matlab
http://www.mathworks.com/help/toolbox/stats/randsample.html

randsample(母集団, 取り出す個数, replace かどうか = false, 重み = nil)

非復元抽出で重みが指定された場合はサポートされていない (つまり
3 に相当) 。

○ Mathematica
http://reference.wolfram.com/mathematica/ref/RandomSample.html
http://reference.wolfram.com/mathematica/ref/RandomChoice.html

RandomSample[母集団, 取り出す個数]
RandomSample[重み->母集団, 取り出す個数]
RandomChoice[母集団, 取り出す個数]
RandomChoice[重み->母集団, 取り出す個数]

非復元抽出が RandomSample 、復元抽出が RandomChoice 。
-> の文法の意味は知りません。

非復元抽出で重みが指定された場合の意味は説明されていないけれど、
サンプルを見る感じでは 4 っぽい。

ちょっと面白いのは、個数の引数を省略した場合、RandomSample は
母集団のサイズを指定されたものとみなし (つまり Ruby の shuffle
相当) 、RandomChoice は 1 を指定されたものとみなす (Ruby の
sample 相当) そうです。Ruby ではわかりにくいとされそうですが。

○ Python
http://docs.python.org/library/random.html

choice(母集団) # 1 つ取り出す
shuffle(母集団)
sample(母集団, 取り出す個数)

復元抽出も重み指定もなさそう。(?)

どれもマニュアルを読んでるだけなので、正確さは期待しないでくだ
さい。

でも、重みを累積分布として与える例はないですねえ。
sample ごときで常に O(n) かかってほしくないと思うのですが。
あと、浮動小数で重みを与えたとき、下手に sum を自前で計算すると
誤差が蓄積しそうなのもちょっとだけ気になってます。

--
Yusuke Endoh [e-mail]

=end

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月19日14:33 Urabe Shyouhei [e-mail]:

(2010/12/19 14:02), Yusuke ENDOH wrote:

卜部さんの [ruby-dev:42791] が、一読すると採択自体はほぼ決定みたいに
読めますが、「パッチがあれば matz の承認が降りやすくなる」という意味
(のはず) です。

いや、あの状況ではtrunkに突っ込む気まんまんでしたけどね。なんせ拒否する理由が
なかったし。

まあ反対意見が出てきたことですし、今の時点ではみなさんが合意するかまつもとさん
が入れると言い出さない限りは、私からはアクションは取りません。

たとえみなさんが合意しても、matz が承認を示さない限り new feature は
入れてはいけないものだと思っていました。

反対意見がなくても matz が見解を出さないために保留になっている new
feature は結構あるはず。その状況が良くないという意見はよくわかります
が、別途議論すべきだと思います (そしてこれも matz が意見を出してくれ
なくてまとまらないのだろう) 。

--
Yusuke Endoh [e-mail]

=end

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月19日15:20 Yoji Ojima [e-mail]:

後、個人的な感想では重みをブロックで決めるのがスッキリしません。

R では重みの配列を引数として渡すようになっているようです。
http://stat.ethz.ch/R-manual/R-devel/library/base/html/sample.html

ブロックが嫌か、または少しでも高速にしたいと考えるなら R と同じ方法でも良いですが、私はブロックを使う方が Ruby らしいし、「引数の意味が何だか忘れる」心配もなくて良いと思います。

「Ruby らしさ」は十人十色なので否定はしませんが、私にはむしろ
何個取り出すべきかあらかじめ決まってないときに、「ブロックが
真を返すまで抽出し続ける」という意味に感じられます。
take_while みたいに。

「引数の意味を忘れる」については、最近はこの手のオプショナルな
引数をキーワード引数とするようになっているので、問題ないと思い
ます。

--
Yusuke Endoh [e-mail]

=end

[yugui (Yuki Sonoda)]

=begin
Yuguiです。

2010/12/19 Masaya TARUI [e-mail]:

じゃあ反対ないので実装はともかく、この仕様は基本入れる方向で考えましょう。反対の人は意思表示お早めに。
仕様が詰められていないと思うので、そういう意味で消極的反対です。

同意見です。仕様をもっとよく考えるべきです。

ニーズについては頷けるので、何らかの形で分布関数を与えることには異論はありません。
ここで、幾つかの考慮すべきことがあります。

• 効率的な実装の可能な仕様であるべきです。
• [ruby-dev:41918] 非復元抽出の要望が入るとすれば、その要望と衝突せず、整合性を持つ仕様である必要があります。
• mrknさんのMath/Random構想を考慮して欲しいです。あちらで提供される分布実装と整合性を持つ仕様であって欲しいです。
  • mrknさんの考えるArray#sampleの仕様も聞きたいです

--
Yuki Sonoda (Yugui)
[e-mail]
http://yugui.jp

=end

[oj (Yoji Ojima)]

=begin

でも、重みを累積分布として与える例はないですねえ。
sample ごときで常に O(n) かかってほしくないと思うのですが。

復元抽出の高速アルゴリズムである Walker's alias method を使うのに必要な情報は累積分布ではないので、それを引数として与えるというのは、簡便性重視と高速性重視のどちらにも寄らない中途半端な仕様であると考えます。
=end

[matz (Yukihiro Matsumoto)]

=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:42806] Re: [Ruby 1.9-Feature#4147] Array#sample で重みを指定したい"
on Sun, 19 Dec 2010 20:17:57 +0900, Yusuke ENDOH [e-mail] writes:

|たとえみなさんが合意しても、matz が承認を示さない限り new feature は
|入れてはいけないものだと思っていました。

そうしていただけると助かります。私の反応が悪い時はつついてく
ださい。今回のような私は使わない機能については判断が難しいの
で、素人でもなにが求められていて、今回の変更によってどのよう
に嬉しいのかをまとめてくださらないと判断できないと思います。

|反対意見がなくても matz が見解を出さないために保留になっている new
|feature は結構あるはず。その状況が良くないという意見はよくわかります
|が、別途議論すべきだと思います (そしてこれも matz が意見を出してくれ
|なくてまとまらないのだろう) 。

いやあ(苦笑

=end

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月19日22:52 Yoji Ojima [e-mail]:

でも、重みを累積分布として与える例はないですねえ。
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 [e-mail]

=end

[oj (Yoji Ojima)]

=begin

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

私個人としては高速性に興味はなく、最初のサンプルのような処理を標準機能の範囲で簡潔に記述することができさえすれば満足です。

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

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月20日1:27 Yoji Ojima [e-mail]:

私個人としては高速性に興味はなく、最初のサンプルのような処理を標準機能の範囲で簡潔に記述することができさえすれば満足です。

係数レベルの性能には私も大して興味ないんですが、オーダが違うとなると
さすがに気になります。特に、機能的には 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 [e-mail]

=end

[oj (Yoji Ojima)]

=begin

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

メソッド自体が高速であっても、そのために累積分布を渡す必要があるというのでは、たとえば要素の重みを一つだけ変えて再抽選というときには Ruby 側で累積分布を再計算しなければならず、逆に遅くなる状況もありえます。総合的に見て、ご提案のインタフェースが有利な状況は限られており、汎用性に欠けるのではないかと考えます。

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

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

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月20日14:06 Yoji Ojima [e-mail]:

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

メソッド自体が高速であっても、そのために累積分布を渡す必要があるというのでは、たとえば要素の重みを一つだけ変えて再抽選というときには Ruby 側で累積分布を再計算しなければならず、逆に遅くなる状況もありえます。

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

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

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

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

そうですね。

--
Yusuke Endoh [e-mail]

=end

[oj (Yoji Ojima)]

=begin

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

ほとんどの場合は一回の呼び出しで大量の抽出を行うことで代替可能ではないでしょうか。

繰り返しになりますが、二分探索は最適なアルゴリズムではない（簡便性を犠牲にする割に半端にしか速くならない）というのも重要な点で、高速な細切れ抽出を本当に求めるのであれば、以下のサイトのコードのように専用のクラスを用意するのが適切だと思います。
http://code.activestate.com/recipes/576564-walkers-alias-method-for-random-objects-with-diffe/
しかしながら、これは組み込みライブラリでサポートすべき範疇ではないでしょう。
=end

[akr (Akira Tanaka)]

=begin
2010年12月19日21:15 Yugui [e-mail]:

• 効率的な実装の可能な仕様であるべきです。

もしこの話が復元抽出 (同じものが何回でも現れても良い）の話なら、
それを効率的に実装する乱数は、どんな分布にせよ、

x = f(rand(n))

として、f, n を適当に選ぶことで表現できるので、

f, n = Random.分布変換関数生成_分布の種類(パラメータ)

とかが効率的なんじゃないかと思っています。
(call が抜けてますが気にしないように)

f, n = Random.分布変換関数生成_離散分布(beg..end) {|v| 頻度 }
f, n = Random.分布変換関数生成_累積離散分布(beg..end) {|v| 累積頻度 }
...

とか、分布の指定のしかたがいろいろ欲しければ、そのぶんだけ
メソッドを作ればいいでしょう。

まぁ、f, n というのはあまりに生々しすぎるとは思いますが、原理としては。

しかし、問題は、Array#sample は非復元抽出だと言うことです。

• [ruby-dev:41918] 非復元抽出の要望が入るとすれば、その要望と衝突せず、整合性を持つ仕様である必要があります。

ここの記述は間違っていると思います。
Array#sample は非復元抽出 (同じものはたかだか一回しか現れない) です。
[ruby-dev:41918] は復元抽出の要望です。
[ruby-dev:41919] には日本語でそう書いてありますね。

(まぁ、私にとっても、復元抽出・非復元抽出は親しみのある名前ではありません)

なので、被復元抽出を効率的に実装する方法について検討が必要ですが、
それはちょっと自明ではありません。

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

Random に話を広げると、連続分布の話が出てきますね。
Array#sample だけなら、離散分布だけでいいんですが。

連続分布では個々の要素に対する頻度をすべて調べるのは無謀だし、
あと、復元抽出と非復元抽出の違いに意味はないと思うので、
話はさらに変わってくるでしょう。

[田中 哲][たなか あきら][Tanaka Akira]

=end

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月20日22:33 Yoji Ojima [e-mail]:

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

ほとんどの場合は一回の呼び出しで大量の抽出を行うことで代替可能ではないでしょうか。

最初に大量抽出でプールしておいて、ちょっとずつ消費し、無くなったら
また大量抽出してプールする、というデバッグが面倒なコードをユーザに
書かせることになるのはよくないと思います。

繰り返しになりますが、二分探索は最適なアルゴリズムではない（簡便性を犠牲にする割に半端にしか速くならない）というのも重要な点で、高速な細切れ抽出を本当に求めるのであれば、以下のサイトのコードのように専用のクラスを用意するのが適切だと思います。
http://code.activestate.com/recipes/576564-walkers-alias-method-for-random-objects-with-diffe/
しかしながら、これは組み込みライブラリでサポートすべき範疇ではないでしょう。

確かに組み込みにするには大掛かりすぎると思います。
しかしある程度ちゃんと対応しようとしたら大掛かりな API が必要である
以上、組み込みにするのが不適切なのではないかという気もします。

重み付き sample を本気で使おうとして困った人が「O(n) かかって遅いん
だけどなんでこんな API にしたの」と言ってきたときに、「重み付き
sample はおみくじ専用なので本気で使わないでください」とかアホなこと
言いたくないですし、本気で使うときは自力で書き直すのが定番になるのも
嬉しくないです。

ところで以前 naruse さんが (IRC で) 言ってたアイデアなのですが、
Enumerator で返すという API が考えられます。つまり、

e = %(大吉 中吉 小吉 凶).sample_each
e.each {|x| p x } #=> 凶 中吉 大吉 小吉

e = %(大吉 中吉 小吉 凶).sample_each(unique: false, weight: [1000, 100, 10, 1])
e.each {|x| p x } #=> 大吉 大吉 中吉 大吉 ...

これが実は相性いいかもしれない？

--
Yusuke Endoh [e-mail]

=end

[oj (Yoji Ojima)]

=begin

ところで以前 naruse さんが (IRC で) 言ってたアイデアなのですが、
Enumerator で返すという API が考えられます。つまり、

e = %(大吉 中吉 小吉 凶).sample_each
e.each {|x| p x } #=> 凶 中吉 大吉 小吉

e = %(大吉 中吉 小吉 凶).sample_each(unique: false, weight: [1000, 100, 10, 1])
e.each {|x| p x } #=> 大吉 大吉 中吉 大吉 ...

これなら悪くないと思います。
ただ sample_each.each となると少し変なので、名前は要検討かと。
=end

[naruse (Yui NARUSE)]

=begin
今の論点は以下の三つだと思います。

• 復元抽出の指定
• 重みの指定 (引数/block)
• 効率 (ユースケースはなにか、何に対して最適化するか)

== 復元抽出の指定

まず、今回のおみくじは復元抽出なので、復元抽出の指定を追加する必要があります。
optional hashで指定という論もありますが、わたしは Array#choice という名の復元抽出
メソッド追加を推します。

Array#choice は 1.8.7 に存在し、その後削除されましたが、この時のは無引数だったため、
互換性上の問題は発生しません。
sample/choice の名付けは Mathematica に沿っています。(see also [ruby-dev:42805])

== 重みの指定

重みをどこから与えるかですが、そもそも元のデータはどこにあるのかという観点があります。
一つはレシーバである ary の要素が何らかの形で持っている場合、
もう一つはそれとは別に ary なり hash なりで存在する場合があるでしょう。
両者を考えると、block でやるというのはそれなりに理由があるように感じます。

== 効率

呼び出し回数が多い場合について考えると、要素数・抽出数が少ない場合はどうでもよいとしましょう。
一方で要素数・抽出数が多い場合は、そもそもなんども呼び出して初期化するという設計がおかしいわけで、
そのために初期化をシンプルにするよりは、初期化済みの状態を enumerator (というか generator というか)
で保持して、そこから取ってくるようにしたほうがいいんじゃないですかね。
もっとも、これは現時点では必ずしも入れる必要はない気もします。

これなら悪くないと思います。
ただ sample_each.each となると少し変なので、名前は要検討かと。

その場合は sample_each {|x| .. } とするだろうので、変にはなりませんね。

--
NARUSE, Yui
[e-mail]

=end

[oj (Yoji Ojima)]

=begin

まず、今回のおみくじは復元抽出なので、復元抽出の指定を追加する必要があります。
optional hashで指定という論もありますが、わたしは Array#choice という名の復元抽出
メソッド追加を推します。

賛成です。1.8.7 であったものが急に使えなくなる問題も自然と解消されますし。

これなら悪くないと思います。
ただ sample_each.each となると少し変なので、名前は要検討かと。

その場合は sample_each {|x| .. } とするだろうので、変にはなりませんね。

そうでしたか、失礼。
これを採用する可能性を考えると、重みをブロックで指定する方式は整合性がなくなる可能性が高いでしょうか。
=end

[akr (Akira Tanaka)]

=begin
2010年12月20日22:56 Tanaka Akira [e-mail]:

なので、被復元抽出を効率的に実装する方法について検討が必要ですが、
それはちょっと自明ではありません。

Pavlos S. Efraimidis, Paul G. Spirakis
Weighted random sampling with a reservoir
Information Processing Letters
Volume 97, Issue 5 (16 March 2006)

というアルゴリズムがあるようですね。

検索するとそれっぽいのが見つかって読めますが、
重みの情報は、存在する各要素から重みを求める関数の形で
与えればいいようです。

なお、ヒープ (データ構造) が必要なようです。

[田中 哲][たなか あきら][Tanaka Akira]

=end

[akr (Akira Tanaka)]

=begin
2010年12月21日21:35 Tanaka Akira [e-mail]:

Pavlos S. Efraimidis, Paul G. Spirakis
Weighted random sampling with a reservoir
Information Processing Letters
Volume 97, Issue 5 (16 March 2006)

というアルゴリズムがあるようですね。

検索するとそれっぽいのが見つかって読めますが、
重みの情報は、存在する各要素から重みを求める関数の形で
与えればいいようです。

なお、ヒープ (データ構造) が必要なようです。

論文の最初のほうだけ読んでやってみるとこうですかねぇ。

正規分布っぽいものを与えて、それっぽい形になっています。

% ./ruby -I /home/akr/ruby/depq/lib -rdepq -e '
module Enumerable
def sample2(n)
Depq.nlargest(n, self) {|e| rand ** (1.0/(yield(e))) }
end
end

enum = (-20..20).to_a10000
a = enum.sample2(20000) {|e| Math.exp(-(e/5.0)**2) }
h = a.categorize(:op=>:+) {|e| [e,1] }
-10.upto(10) {|x| puts "" * (h[x]/30.0).to_i }
'
*

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

注: 要 depq, categorize

[田中 哲][たなか あきら][Tanaka Akira]

=end

[akr (Akira Tanaka)]

=begin
2010年12月21日15:20 NARUSE, Yui [e-mail]:

== 復元抽出の指定

まず、今回のおみくじは復元抽出なので、復元抽出の指定を追加する必要があります。

いまさらこのスレッドの最初の方を読み直したんですが、
どっちかっていうと、 一回の呼び出しで複数取り出すことはあまり考えていなかった
のではないか、という印象を受けます。

[ruby-dev:42735] のサンプルでは引数がないですし、
[ruby-dev:42741] の実装でも引数を考慮しない簡易的なもの、と書かれています。
[ruby-dev:42797] でもそういう感じですよね。

そして、ひとつだけ取り出すなら、復元抽出でも非復元抽出でもかわりないので、
どちらでも気にしないんじゃないかと思っています。

[田中 哲][たなか あきら][Tanaka Akira]

=end

[naruse (Yui NARUSE)]

=begin
2010年12月21日17:59 Yoji Ojima [e-mail]:

これなら悪くないと思います。
ただ sample_each.each となると少し変なので、名前は要検討かと。

その場合は sample_each {|x| .. } とするだろうので、変にはなりませんね。

そうでしたか、失礼。
これを採用する可能性を考えると、重みをブロックで指定する方式は整合性がなくなる可能性が高いでしょうか。

あ、確かにこれだと重みが指定できませんね。
うーん・・・。

--
NARUSE, Yui
[e-mail]

=end

[naruse (Yui NARUSE)]

=begin
2010年12月22日13:08 Tanaka Akira [e-mail]:

2010年12月21日15:20 NARUSE, Yui [e-mail]:

== 復元抽出の指定

まず、今回のおみくじは復元抽出なので、復元抽出の指定を追加する必要があります。

いまさらこのスレッドの最初の方を読み直したんですが、
どっちかっていうと、 一回の呼び出しで複数取り出すことはあまり考えていなかった
のではないか、という印象を受けます。

[ruby-dev:42735] のサンプルでは引数がないですし、
[ruby-dev:42741] の実装でも引数を考慮しない簡易的なもの、と書かれています。
[ruby-dev:42797] でもそういう感じですよね。

そして、ひとつだけ取り出すなら、復元抽出でも非復元抽出でもかわりないので、
どちらでも気にしないんじゃないかと思っています。

IRCにおけるちょっとした議論の結果、主たる想定ユースケースはRPGゲームだろうということになりました。
つまり、

• フィールドやダンジョン移動時にモンスターとエンカウントするかどうか
• エンカウントする場合、戦闘するモンスター群の種別の決定
• バトル時のヒットクリティカル・ミスの判定
• 攻撃ダメージ・回復量の決定
• 戦闘後に取得するアイテムの決定
  などであろうと。

この場合確かにakrさんのご指摘通りな可能性が高いように思います。

--
NARUSE, Yui
[e-mail]

=end

[oj (Yoji Ojima)]

=begin

そして、ひとつだけ取り出すなら、復元抽出でも非復元抽出でもかわりないので、
どちらでも気にしないんじゃないかと思っています。

おっしゃる通り、個人的には全く気にしません。
気にする人たちのことを考えて仕様を検討してほしいとは思っています。
=end

[mrkn (Kenta Murata)]

=begin
むらたです。

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/

=end

[mame (Yusuke Endoh)]

=begin
遠藤です。

2010年12月23日14:00 Kenta Murata [e-mail]:

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

この名前については ruby-core で議論すべきだと思います。
個人的には sample/choice の命名はわかるわけがないと思うのですが、
いい対案もないので、matz と英語圏ユーザがそれでいいというなら反対
しないです (replace はわからないどころか誤解させる語感があるので
かなり反対ですが) 。

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

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

IRC では、sample(weight: proc { ... }) としたらどうかな、という
案が挙がっていました。

個人的には、ブロックが重みを表すのにはどうも違和感があります。
sort_by との類似という話もわかるっちゃわかるのですが。
また、sample_each と相性が悪いって問題もあります。

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

おお。
ところで、mrkn さんは何のためにこれを作ったのかが興味あります。
この提案はユースケースが明確でなく、その辺の議論がどうも机上の域を
こえてない感じですので、参考になるのではないかと。

同一条件での連続した抽出を高速に実現するには、遠藤さんが指摘されているように、
母集団をソートしたり Walker のアルゴリズムのように作業用データを準備したりする
必要があります。準備のための計算コストを考えると、そのような準備済みの状態を
オブジェクトにして取り出して使い回せる仕組みが欲しくなります。
snip
だから、「Array#sample は遅いものだ」というお墨付きがあるなら、
最低限だけできるようにして「遅いのが嫌なら自分で実装してね」で良いと思います。

そんなもの組み込みにする必要があるんでしょうか。gem ではダメなんで
しょうか。というのが私の意見だったんですが、

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

ということです。両方あれば問題ないと思います。

--
Yusuke Endoh [e-mail]

=end

[mame (Yusuke Endoh)]

=begin
遠藤です。

議論が大分入り組んで来たので、一旦現在の API とその実装の案を
まとめてみました。sample_each は each_sample に改名してます。

Array#sample([size, [opt]])

• API

  • size が省略されたら 1 つサンプリングして返す
  • size が与えられたら size 分だけ非復元抽出して配列で返す
  • opt の意味:
    weight: proc or array
    random: Random instance

• 実装

  • weight が省略されたら現在の実装と同じ
  • weight が与えられたら akr さんの方法 [ruby-dev:42844]

Array#choice([size, [opt]])

• API

  • size が省略されたら 1 つサンプリングして返す
  • size が与えられたら size 分だけ復元抽出して配列で返す
  • opt は Array#sample と同じ

• 実装

  • 乱数選択を size 回繰り返すだけ (weight が与えられたら考慮する)
  • Walker's alias method は使わない (size が小さい時は不利になる
    し、size が大きい場合だけ使うのも乱数の再現性が壊れるからダメ)

Array#each_sample([opt])

• API

  • サンプリングして yield を繰り返す (全部サンプリングしたら終了)
  • ブロックを省略したら Enumerator を返す
  • opt は Array#sample と同じ

• 実装

  • weight が省略されたら現在の実装と似た感じ
  • weight が与えられたら akr さんの方法 (ちょっと非効率になる？)

Array#each_choice([opt])

• API

  • サンプリングして yield を無限に繰り返す
  • ブロックを省略したら Enumerator を返す
  • opt は Array#sample と同じ

• 実装

  • weight が省略されたら乱数選択を無限に繰り返す
  • weight が与えられたら Walker's alias method を無限に繰り返す

それぞれの例

• %(大吉 中吉 小吉 凶).sample #=> 等確率にどれか

• %(大吉 中吉 小吉 凶).sample(4) #=> shuffle と同じ

• %(大吉 中吉 小吉 凶).sample(weight: [1000, 100, 10, 1])
  #=> 重み付きでどれか (大吉が出やすい)

• %(大吉 中吉 小吉 凶).sample(4, weight: [1000, 100, 10, 1])
  #=> 重み付きでどれか、の配列 (["大吉", "中吉", "小吉", "凶"] が最も出やすい)

• %(大吉 中吉 小吉 凶).sample(4, weight: proc {|x| ... } )
  #=> 重み付きでどれか、の配列 (重みは proc が返した値)

• %(大吉 中吉 小吉 凶).choice #=> 等確率にどれか

• %(大吉 中吉 小吉 凶).choice(4) #=> choice を 4 回繰り返すのに相当

• %(大吉 中吉 小吉 凶).choice(weight: [1000, 100, 10, 1])
  #=> 重み付きでどれか (大吉が出やすい)

• %(大吉 中吉 小吉 凶).choice(4, weight: [1000, 100, 10, 1])
  #=> 重み付きでどれか、の配列 (["大吉", "大吉", "大吉", "大吉"] が最も出やすい)

• %(大吉 中吉 小吉 凶).each_sample.first #=> sample と同じ

• %(大吉 中吉 小吉 凶).each_sample.to_a #=> shuffle と同じ

• %(大吉 中吉 小吉 凶).each_sample(weight: [1000, 100, 10, 1]).take(4)
  #=> 重み付きでどれか、の配列 (["大吉", "中吉", "小吉", "凶"] が最も出やすい)

• %(大吉 中吉 小吉 凶).each_choice.first #=> choice と同じ

• %(大吉 中吉 小吉 凶).each_choice.to_a #=> choice(4) と同じ

• %(大吉 中吉 小吉 凶).each_choice(weight: [1000, 100, 10, 1]).take(4)
  #=> 重み付きでどれか、の配列 (["大吉", "大吉", "大吉", "大吉"] が最も出やすい)

--
Yusuke Endoh [e-mail]

=end

[akr (Akira Tanaka)]

=begin
2010年12月22日18:01 Yoji Ojima [e-mail]:

おっしゃる通り、個人的には全く気にしません。
気にする人たちのことを考えて仕様を検討してほしいとは思っています。

いろんなひとの思惑が重なって大きな話になっていますが、
小さい変化で済むといいですね。

将来のためには大きな話を検討したほうがいいですけど、
実際の進め方としては (可能なら) うまく分割して漸進的に
作るのがいいと思うので。

[田中 哲][たなか あきら][Tanaka Akira]

=end

[mrkn (Kenta Murata)]

=begin
むらたです。

On 2010/12/23, at 14:56, Yusuke ENDOH wrote:

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

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

IRC では、sample(weight: proc { ... }) としたらどうかな、という
案が挙がっていました。

私も同様のインターフェイスを考えていました。
weight は proc だけじゃなくて配列とハッシュも受け付けられれば良いと思います。

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

おお。
ところで、mrkn さんは何のためにこれを作ったのかが興味あります。
この提案はユースケースが明確でなく、その辺の議論がどうも机上の域を
こえてない感じですので、参考になるのではないかと。

discrete_distribution.hpp は、それと同じディレクトリにある zipf_distribution.hpp のために
作りました。zipf_distribution.hpp は Zipf-Mandelbrot 分布の実装です。

私が Zipf-Mandelbrot 分布を作った理由は、離散ベキ分布に従う乱数を生成する必要があったからです。
学生の頃、複雑ネットワークの研究をしていて、観測データの検証用に使ったり、
頂点の次数 (接続する辺の本数) がベキ分布に従うようなネットワーク構造を作るときに使いました。

--
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/

=end

[oj (Yoji Ojima)]

=begin

議論が大分入り組んで来たので、一旦現在の API とその実装の案を
まとめてみました。sample_each は each_sample に改名してます。

これは、とりあえず意見は出尽くした感じですよね。
私としては遠藤さんがまとめられた案で問題ないと思いますが、まつもとさんのご意見はいかがでしょう？
命名についてはまだ議論の余地がありますが、ruby-core に投げるべきでしょうか。
=end

[matz (Yukihiro Matsumoto)]

=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:42968] [Ruby 1.9-Feature#4147] Array#sample で重みを指定したい"
on Thu, 6 Jan 2011 22:30:42 +0900, Yoji Ojima [e-mail] writes:

|>議論が大分入り組んで来たので、一旦現在の API とその実装の案を
|>まとめてみました。sample_each は each_sample に改名してます。
|
|これは、とりあえず意見は出尽くした感じですよね。
|私としては遠藤さんがまとめられた案で問題ないと思いますが、まつもとさんのご意見はいかがでしょう？
|命名についてはまだ議論の余地がありますが、ruby-core に投げるべきでしょうか。

機能的な必要性/十分性については私には判断がつきませんが、私
には問題なさそうに見えます。ただし、each_sample, each_choice
という名前に若干の違和感がありますので、ruby-coreの人たちの
意見も聞きたいところです。

=end

[oj (Yoji Ojima)]

=begin

機能的な必要性/十分性については私には判断がつきませんが、私
には問題なさそうに見えます。ただし、each_sample, each_choice
という名前に若干の違和感がありますので、ruby-coreの人たちの
意見も聞きたいところです。

遅くなりましたが、簡単にまとめると、

• choice というネーミングは単一選択のニュアンスがあるので望ましくない
• 復元抽出をオプション repeat: true で指定するなら反対意見なし
• #each_sample を #samples にするという提案あり

というところでしょうか。どうされますか？
=end

[matz (Yukihiro Matsumoto)]

=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:43148] [Ruby 1.9-Feature#4147] Array#sample で重みを指定したい"
on Sun, 30 Jan 2011 19:14:20 +0900, Yoji Ojima [e-mail] writes:

|遅くなりましたが、簡単にまとめると、
|
|- choice というネーミングは単一選択のニュアンスがあるので望ましくない
|- 復元抽出をオプション repeat: true で指定するなら反対意見なし
|- #each_sample を #samples にするという提案あり
|
|というところでしょうか。どうされますか？

ありがとうございます。最初の2点については私も妥当だと思いま
す。もう取り込んでもいいんじゃないでしょうか。

samplesについては、うーん、Enumeratorを返す場合には
each_sampleよりもわかりやすいと思いますが、まだちょっと違和
感が。慣れるかもしれませんが。

=end

[shyouhei (Shyouhei Urabe)]

ちょっと、この件が自分にアサインされていてかつ最後がまつもとさんの「取り込んでもいい」で終わってるのを発見したのですが、これってえんどうさんが実装持ってたりします? なければ今から自分が書こうと思いますが。

[naruse (Yui NARUSE)]

• Target version set to 2.0.0

そろそろ言っちゃっても大丈夫だと思うんですが、これの主たるユースケースってRPGツクールですよね。
http://tkool.jp/
http://d.hatena.ne.jp/ktakaki/20111201/p1

という話を出しつつ、ping

[shyouhei (Shyouhei Urabe)]

まだなんも手をつけてません。卜部にアサインされているのが適切ではないという気もします。
そのうちなんとかしようとは思っていますが、お急ぎでしたらまきとっていただいたほうがよいです。

[akr (Akira Tanaka)]

開発ミーティングで話したところ、何を実装すればいいのか仕様がいまひとつはっきりしていないのが
問題で進まないということに一致を見ました。

とりあえず、私は、repeat: オプションとブロックによる重みを実装するのがいいのではないか、と思います。

ここでブロックは与えられた値に対する重みを返すものとします。（累積確率ではありません）

（累積確率よりも単なる重みの方が単純でわかりやすそうというのが、
単にブロックを与えたときに重みと解釈する理由です。
もし累積確率が必要なら、将来的になにかオプション引数で指定するというのはありえます。）

[yhara (Yutaka HARA)]

• Target version changed from 2.0.0 to 2.6

[gogotanaka (Kazuki Tanaka)]

こんにちは.

大変昔の話を掘り返すようで恐縮ですが、こちらてパッチを書いたら取り込まれる可能性てございますか？
（もちろんそのパッチ如何によるんでしょうが）

まずはパッチ書いてからにしろという話なら申し訳ございません、

２年前という事で、他の文脈がある事やどなたかが着手されている事を危惧致しました.

[naruse (Yui NARUSE)]

• Assignee deleted (shyouhei (Shyouhei Urabe))

gogo tanaka wrote:

こんにちは.

大変昔の話を掘り返すようで恐縮ですが、こちらてパッチを書いたら取り込まれる可能性てございますか？
（もちろんそのパッチ如何によるんでしょうが）

まずはパッチ書いてからにしろという話なら申し訳ございません、

この件については、結局どのような仕様を入れるのかというのがポイントな気がしますが、
パッチがあった方が話が早い可能性もあるかな、といったところでしょうか。

２年前という事で、他の文脈がある事やどなたかが着手されている事を危惧致しました.

わたしの知る限りでは進捗ないと思います。
うらべさん、あるいは他のどなたか何かありますか？

[shyouhei (Shyouhei Urabe)]

Yui NARUSE wrote:

わたしの知る限りでは進捗ないと思います。
うらべさん、あるいは他のどなたか何かありますか？

進捗ダメです。

このスレッドのコメント#1でも書きましたが実装があると話が大幅に進むことが多いので実装は大歓迎です。この議論は途中で話が大きくなったり小さくしようとしたりしてだいぶ混乱してしまったので、見通しをよくする意味でもコードがあったほうが助かります。

[hsbt (Hiroshi SHIBATA)]

• Status changed from Assigned to Feedback