From: Tanaka Akira <akr@...>
Date: 2010-12-22T00:32:34+09:00
Subject: [ruby-dev:42844] Re: [Ruby 1.9-Feature#4147][Assigned] Array#sample 	で重みを指定したい

2010年12月21日21:35 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)
>
> というアルゴリズムがあるようですね。
>
> 検索するとそれっぽいのが見つかって読めますが、
> 重みの情報は、存在する各要素から重みを求める関数の形で
> 与えればいいようです。
>
> なお、ヒープ (データ構造) が必要なようです。

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

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

% ./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_a*10000
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]