ブログトップ 記事一覧 ログイン 無料ブログ開設

mjh.日記@渋谷 with TH55 RSSフィード

7N1MJH 運用状況 2014/04/05 10:56 現在
QSO回数:62176 (通常QSO:36885(59%), コンテスト:25291(40%))
周波数帯別: 3.5:273(0%) 7:1697(2%) 14:19(0%) 18:37(0%) 21:361(0%) 24:5(0%) 28:847(1%) 50:1448(2%) 144:5011(8%) 430:51374(82%) 1200:1104(1%)
モード別: FM:53551(86%) SSB:8583(13%) AM:10(0%) D-STAR(DV):32(0%)

2010年10月24日

[][]Rubyで上位n件を求める

最近は仕事先以外でコードを書くことが多くなっている。

特にここ1・2ヶ月はパズルとかの問題を解くために実験的に多くの組み合わせの計算をRubyにさせることが多い。このときにしばしば欲しくなるのが「上位n件を求める」機能。配列に設定済みのデータであれば、Array#sortを呼び出した後に配列の先頭を見れば良いのだけど、以下の点が気になる。

  • 上位10件を求めるときに100万件のデータを貯めておいて完全にソートするのはメモリと時間の無駄
  • Arrayで扱わない無限個のデータには対応できない

例えば、一万個の乱数を求めてその値の上位5件を表示させたいのなら、こんな感じで簡単に取り出したい。(以下、コードはすべてRuby 1.9)

topn = TopN.new(5)
1.upto(10000).each do
  topn << Random.rand
end
topn.each_with_index do |data,i|
  puts "Rank#{i+1}:value=#{data}"
end

ついでに、個々のデータに付加情報があるのであれば、データから値を取り出す処理をコンストラクタにブロックとして与えればうまく動くようにしたい。例えば、「値が何回目に出現したか」を扱いたい時はこんな感じで書けたらなぁ...と。

topn = TopN.new(5) { |data| data[:value] }
1.upto(10000).each do |count|
  topn << {value: Random.rand,description: count}
end
topn.each_with_index do |data,i|
  puts "Rank#{i+1}:value=#{data[:value]} count=#{data[:description]}"
end

探してみても相当するライブラリが見つからなかったので、TopNクラスのコードを書いてみた。

(ちゃんと探せば実は有る??)

最初の例を実行すると以下のように出力され、

Rank1:value=0.9999727375403678
Rank2:value=0.9999709710675848
Rank3:value=0.9998929520002925
Rank4:value=0.9998796385129795
Rank5:value=0.9998750822342006

二つ目の例であれば、以下のように出力される。

Rank1:value=0.9999711913114 count=3520
Rank2:value=0.9999658723206534 count=4642
Rank3:value=0.9999289720505727 count=9733
Rank4:value=0.9998648527153264 count=916
Rank5:value=0.9998544367073094 count=3624

数値に限らず、<や>で比較可能なオブジェクトであれば何でも対象に出来る。

以下、コード。

# 上位n件のソートされたデータ
class TopN
  attr_reader :top_data

  def initialize(n,&b)
    @n,@sel_v,@top_data = n,b,[]
  end

  def each
    @top_data.each { |v| yield v }
  end

  def each_with_index
    @top_data.each_with_index { |v,i| yield v,i }
  end

  def <<(target)
    update(target) if (@top_data.size < @n || to_v(@top_data[-1]) < to_v(target))
  end

  protected
  def to_v(v)
    @sel_v ? @sel_v.call(v) : v
  end

  def update(target)
    if @top_data.empty?
      @top_data << target
    else
      dest_data = []
      @top_data.each do |source|
        if target && to_v(target) > to_v(source)
          dest_data << target 
          target = nil
        end
        break if dest_data.size == @n
        dest_data << source
      end
      @top_data = dest_data
    end
  end
end

aa 2012/12/23 17:41 こちらのコードを使用させて頂きました.
はじめに0.5を代入し次に0.4を代入すると0.4を受け付けてくれません.
はじめのn件は無条件で受け取るようにしないとtopNになっていないと思います.

aa 2012/12/23 18:16 上記の問題を改良しました.
@top_data.sizeがn以下の場合には無条件で適する場所に追加するようにしています.

# 上位n件のソートされたデータ
class TopN
attr_reader :top_data

def initialize(n,&b)
@n,@sel_v,@top_data = n,b,[]
end

def each
@top_data.each { |v| yield v }
end

def each_with_index
@top_data.each_with_index { |v,i| yield v,i }
end

def <<(target)
update(target) if (@top_data.size < @n || to_v(@top_data[-1]) < to_v(target))
end

protected
def to_v(v)
@sel_v ? @sel_v.call(v) : v
end

def update(target)
if @top_data.empty?
@top_data << target
else
dest_data = []
if @top_data.size < @n
@top_data.each do |source|
if target && to_v(target) > to_v(source)
dest_data << target
target = nil
end
dest_data << source
end
if target != nil
dest_data << target
end
@top_data = dest_data
else
@top_data.each do |source|
if target && to_v(target) > to_v(source)
dest_data << target
target = nil
end
break if dest_data.size == @n
dest_data << source
end
@top_data = dest_data
end
end
end
end

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/mjh/20101024/1287901875