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