[#42735] [Ruby 1.9-Feature#4147][Open] Array#sample で重みを指定したい — Yoji Ojima <redmine@...>

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

52 messages 2010/12/10
[#42791] [Ruby 1.9-Feature#4147][Assigned] Array#sample で重みを指定したい — Shyouhei Urabe <redmine@...> 2010/12/18

チケット #4147 が更新されました。 (by Shyouhei Urabe)

[#42800] Re: [Ruby 1.9-Feature#4147][Assigned] Array#sample で重みを指定したい — Masaya TARUI <tarui@...> 2010/12/19

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

[#42763] [Ruby 1.9-Bug#4159][Open] test_block_variables(TestRipper::ParserEvents) が失敗する — Kouhei Yanagita <redmine@...>

Bug #4159: test_block_variables(TestRipper::ParserEvents) が失敗する

8 messages 2010/12/14

[#42894] [Ruby 1.8-Feature#4207][Open] これから「1.8.8」の話をしよう -- 1.8がこの先生きのこるには — Shyouhei Urabe <redmine@...>

Feature #4207: これから「1.8.8」の話をしよう -- 1.8がこの先生きのこるには

24 messages 2010/12/26
[#42935] Re: [Ruby 1.8-Feature#4207][Open] これから「1.8.8」の話をしよう -- 1.8がこの先生きのこるには — Kenta Murata <muraken@...> 2011/01/04

むらたです。

[#42936] Re: [Ruby 1.8-Feature#4207][Open] これから「1.8.8」の話をしよう -- 1.8がこの先生きのこるには — Kenta Murata <muraken@...> 2011/01/05

むらたです。

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

From: Tanaka Akira <akr@...>
Date: 2010-12-21 12:35:13 UTC
List: ruby-dev #42842
2010年12月20日22:56 Tanaka Akira <akr@fsij.org>:

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

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

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

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

なお、ヒープ (データ構造) が必要なようです。
-- 
[田中 哲][たなか あきら][Tanaka Akira]

In This Thread