H-indexを二分探索で求める
ただいまはてブ指数として評判のH指数を求めるプログラムを書く話に便乗してみる。
H指数を求めることは、配列とその添字(1はじまり)を比較して、はじめて要素の値が添字より小さくなるところの境界を求めることに等しい。これは各要素とその添字の大小関係だけで計算でき、前後の要素を参照する必要がない。従って、いちいち端から順に値を比較しなくても、二分探索を用いれば、O(log n)で境界値を求めることができる。
#!/usr/bin/perl use warnings; use strict; use integer; sub h_index(@) { my @sorted = sort {$b<=>$a} @_; my $size = 1+$#sorted; my $head = 0; my $tail = $size-1; # 配列が空の場合は0を返り値とする。 return 0 if $size == 0; # ループに入る前に、配列の先頭と末尾の値を確認しておく。 # これは配列の長さが2以下のとき、特に必要になる措置である。 return 0 if $sorted[$head] == 0; return $size if $sorted[$tail] >= ($size); my $index = $tail/2; # メインループ。$sorted[$index]の値によって区間を狭めていく。 while($tail - $head > 1) { # print " * $head $index $tail\n"; # デバッグ用 # Perlの添字は0始まりなので、$indexに1を加えてから比較する。 if ($sorted[$index] >= ($index+1)) { $head = $index; } else { $tail = $index; } $index = ($head+$tail) / 2; } # ここに到達したとき、$headには「n番目の要素がnとなる最大の添字」が、 # $tailにはその次の添字が入っている。しかし、 # 添字のオリジンの関係によって、$tailの方が求めるべき解となる。 return $tail; } # 以下、テスト 0 == h_index() or die; 0 == h_index(0) or die; 1 == h_index(1) or die; 1 == h_index(2) or die; 1 == h_index(1, 0) or die; 1 == h_index(1, 1) or die; 1 == h_index(2, 1) or die; 2 == h_index(2, 2) or die; 2 == h_index(3, 2) or die; 2 == h_index(3, 2, 1) or die; 2 == h_index(2, 2, 1) or die; 1 == h_index(2, 1, 1) or die; 1 == h_index(2, 1, 0) or die; 1 == h_index(1, 1, 1) or die; 1 == h_index(1, 1, 0) or die; 1 == h_index(1, 0, 0) or die; 3 == h_index(1, 2, 3, 4, 5) or die; 4 == h_index(0, 10, 20, 30, 40) or die; 4 == h_index(1, 2, 4, 8, 16, 32, 64) or die; 4 == h_index(1, 1, 2, 4, 6, 7, 8, 11) or die; 5 == h_index(1, 1, 2, 5, 6, 7, 8, 11) or die; 4 == h_index(1, 1, 2, 2, 4, 6, 7, 8, 11) or die; 5 == h_index(1, 1, 2, 2, 5, 6, 7, 8, 11) or die; print "全テスト成功。おめでとう!\n";
しかし以上のコードの本当に重い部分は、実は探索ではなく、冒頭で一行で済ませている整列の部分である。そこで、クイックソートを必要な部分だけ行いながら、適宜整列済みの要素とその添字を比較してH指数を求めることも考えたが、これはうまく書けなかった。