Route 477

■ [ruby] Ruby 2.0のbsearchについて調べてみた

メモ

• Array#bsearchとRange#bsearchがある
• 条件にあう要素を二分探索で探し出す (Arrayの場合は、事前にソートしておかなくてはならない)
• 条件にあう要素がなかった場合はnilが返る

例

$ cat junk.rb
ary = 10000.times.map{ rand }.sort
p ary.bsearch{|x| x > 0.5}
$ ruby junk.rb
0.5002038714292806

配列の中から、0.5を超える最初の数を探す。二分探索なので速い。配列の中身はソートされていなければならないのに注意。

Range#bsearchの方も同様に使える (検索対象がrng.to_aになったような感じ)。

$ cat junk.rb rng = (1..10000)
p rng.bsearch{|x| x > 5000}
$ ruby junk.rb
5001

応用例

これを利用して、git-bisectみたいのも作れるんじゃないかな。

bsearchを使うと「条件を満たす最初の要素」が取れるので、Range#bsearchを以下のように使うと、 「テストがNGになった最初のコミットID」を(git bisectのように)探しだすことができる。 Ruby 2.0が二分探索のアルゴリズムをうまく担当してくれるので、プログラマは判定条件だけ実装すれば良いので楽ちん。

commit_ids = %w(74fa16 e2be41 84f638 55130b 5a7a42 82ca3f)
puts "Bisecting #{commit_ids}"

rng = (0...commit_ids.length)
guilty = rng.bsearch{|i|
  commit_id = commit_ids[i]
  puts "Try #{commit_id}"
  print "Is it ok? [y/n]"
  $stdin.gets.chomp != "y"
}

puts "#{commit_ids[guilty]} is the bad commit."

ここでひとつ注意点を。Range#bsearchではなく、commit_ids.bsearchを使えばいいんじゃないの？と思うかもしれないが、 Array#bsearchはソートされていないといけないという条件があるので、インデックスの方をbsearchしないといけないのです。

find-anyモード

Array/Rangeのbsearchにはもう一つ、「find-any mode」というモードがあります。 ここまで見てきたものは「find-minimum mode」という、条件にあう最初のものを探し出すモードでした。 一方find-anyモードは、「一定範囲の要素をどれでもいいから一つ見つけたい」という場合に役立つモードです。 と書いておきつつ、それが具体的にどういう時なのかいい例を思いつかないのですが…。rdocにも、通常の用途では find-any modeの方を使うことになるだろうと書いてあります。

さっきのcommit_idsの例だと、「2012年10月15日のコミットが存在するか否か」を二分探索で検査したいようなケースで役に立つかな？