h-index を Ruby で書いてみた
最近 Ruby のプログラムを書いていなかったので、話題のはてブ指数で使われているH指数を求めるメソッドを書いてみた。 H指数は、配列のなかから「N以上の数がN個以上含まれる」場合の最大のNを求めるもの。 例えば、「5,4,3,2,2,1」という配列なら、3以上の数が3個含まれるので、H指数は3になる。
やっていることはそんなに難しくない。
- 配列を大きい順に並び替える
- 先頭からの数と配列の値を比較する
- 両者が一致するならその値を返す
- 配列の値の方が小さければ、先頭からの数 - 1 を返す(この条件を見つけるのにちょっと手間取った)
class Array def hindex index = 0 sort.reverse.each do |item| index += 1 if item == index return index elsif item < index return index - 1 end end index end end
テストケースはこんな感じ。 ちょっと冗長かなぁ。上手にテストを書くって難しい。
require 'test/unit' require 'hindex' class ArrayTest < Test::Unit::TestCase def test_hindex assert_equal(4, [0,10,20,30,40].hindex) assert_equal(4, [10,20,30,40].hindex) assert_equal(3, [20,30,40].hindex) assert_equal(2, [30,40].hindex) assert_equal(1, [40].hindex) assert_equal(3, [1,2,3,4,5].hindex) assert_equal(2, [1,2,3,4].hindex) assert_equal(2, [1,2,3].hindex) assert_equal(1, [1,2].hindex) assert_equal(1, [1].hindex) assert_equal(3, [3,3,3].hindex) assert_equal(2, [3,3].hindex) assert_equal(1, [3].hindex) assert_equal(0, [0,0].hindex) assert_equal(0, [0].hindex) assert_equal(0, [].hindex) end end
他の言語で書いてみても面白いかも。Haskellとかね。
追記
MovableTypeで構築されたブログのh-indexを求める - Open MagicVox.netのソースを読んで、もっとシンプルに書けることに気がつく。 2つの条件で比べる必要は無かったのか…。
class Array def hindex index = 0 sort.reverse.each do |item| index += 1 return index - 1 if item < index end index end end
こっちの方が分かりやすいかな? リンク先のソースはこのアルゴリズムになってた。
class Array def hindex index = 1 sort.reverse.each do |item| break if item < index index += 1 end index - 1 end end
追記 (2)
odz buffer - h-index に Haskell 版のソースが。 「-1」が無くてシンプル!
hindex :: [Int] -> Int hindex lst = length $ takeWhile cond (zip sorted [1..]) where sorted = sortBy (flip compare) lst cond (val, rank) = val >= rank
追記 (3)
h-index を Ruby で書いてみた - にっき (2007-07-20)に Ruby のシンプルなコードが!
class Array def hindex sort.reverse.each_with_index do |item, index| return index if item <= index end.size end end