Rubyで二分探索する

配列に含まれる要素を検索する際に、対象の配列がソート済みの場合は二分探索（バイナリサーチ）を用いると高速に検索できます。

Rubyには配列の二分探索を行うメソッドとしてArray#bsearch、Array#bsearch_indexが用意されているので、わざわざ自前で二分探索を実装する必要がありません。

今回はこの二分探索の使い方とベンチマーク比較を紹介します。

Array#bsearchの使い方

はじめにArray#bsearchについてです。
このメソッドはブロックの評価結果で条件を満たす値を二分探索で検索しその値を返します。

以下はソートされた配列から4より大きい数字を取得する例です。

ary = [1, 3, 5, 7, 11]
puts ary.bsearch{|a| a > 4}
# 5が出力される

Array#bsearch_indexの使い方

次はArray#bsearch_indexについてです。
このメソッドはブロックの評価結果で条件を満たす値を二分探索で検索しその位置を返します。

以下はソートされた配列から4より大きい数字の位置を取得する例です。先頭の位置が0番目なので5の位置は2となります。

ary = [1, 3, 5, 7, 11]
puts ary.bsearch_index{|a| a > 4}
# 2が出力される

二分探索以外との方法との性能比較

前提となる環境

ruby 3.2.0 (2022-12-25 revision a528908271) [arm64-darwin22]

Array#include?と比較

まずはじめに配列に要素が存在するかを判定するArray#include?と比較してみます。

配列の要素数が100,1000,10000,100000の場合でそれぞれ1万回処理したときのベンチマークを取ります。

require 'benchmark'

n = 10000
data_size = [100, 1000, 10000, 100000]

Benchmark.bm do |x|
  data_size.each do |d|
    ary = (0..d-1).to_a

    puts "要素数:#{d}"
    x.report 'Array#include?' do
      n.times do
        target = rand(d)
        ary.include?(target)
      end
    end

    x.report 'Array#bsearch' do
      n.times do
        target = rand(d)
        ary.bsearch{|a| a == target}
      end
    end
  end
end

結果は以下の通りです。

       user     system      total        real
要素数:100
Array#include?  0.002923   0.000002   0.002925 (  0.002923)
Array#bsearch  0.002766   0.000000   0.002766 (  0.002766)
要素数:1000
Array#include?  0.018837   0.000003   0.018840 (  0.018840)
Array#bsearch  0.003403   0.000001   0.003404 (  0.003402)
要素数:10000
Array#include?  0.173394   0.000026   0.173420 (  0.173415)
Array#bsearch  0.004416   0.000001   0.004417 (  0.004416)
要素数:100000
Array#include?  1.720558   0.000408   1.720966 (  1.720927)
Array#bsearch  0.005206   0.000008   0.005214 (  0.005231)

いずれの結果もArray#bsearchの方が速くなりました。
Array#include?の計算量がO(n)に対してArray#bsearchの計算量はO(log n)なので、要素数が増えるにつれて差が大きく開いていくことがわかります。

その他様々なメソッドと比較

次は似たようなメソッドのArray#find、Array#bsearch_index、Set#include?、Set#findとも比較してみました。

require 'benchmark'

n = 10000
data_size = [100, 1000, 10000, 100000]

Benchmark.bm do |x|
  data_size.each do |d|
    ary = (0..d-1).to_a
    s = Set.new(ary)

    puts "要素数:#{d}"
    x.report 'Array#include?' do
      n.times do
        target = rand(d)
        ary.include?(target)
      end
    end

    x.report 'Array#find' do
      n.times do
        target = rand(d)
        ary.find{|a| a == target}
      end
    end

    x.report 'Array#bsearch' do
      n.times do
        target = rand(d)
        ary.bsearch{|a| a == target}
      end
    end

    x.report 'Array#bsearch_index' do
      n.times do
        target = rand(d)
        ary.bsearch_index{|a| a == target}
      end
    end

    x.report 'Set#include?' do
      n.times do
        target = rand(d)
        s.include?(target)
      end
    end

    x.report 'Set#find' do
      n.times do
        target = rand(d)
        s.find{|b| b == target}
      end
    end
  end
end

実行した結果は以下の通りです。

       user     system      total        real
要素数:100
Array#include?  0.002954   0.000000   0.002954 (  0.002950)
Array#find  0.019293   0.000123   0.019416 (  0.019418)
Array#bsearch  0.002672   0.000013   0.002685 (  0.002685)
Array#bsearch_index  0.002650   0.000044   0.002694 (  0.002697)
Set#include?  0.001320   0.000005   0.001325 (  0.001324)
Set#find  0.020483   0.000095   0.020578 (  0.020579)
要素数:1000
Array#include?  0.018342   0.000066   0.018408 (  0.018406)
Array#find  0.158500   0.000600   0.159100 (  0.159104)
Array#bsearch  0.003366   0.000004   0.003370 (  0.003373)
Array#bsearch_index  0.003339   0.000000   0.003339 (  0.003340)
Set#include?  0.001353   0.000000   0.001353 (  0.001353)
Set#find  0.172065   0.001208   0.173273 (  0.173275)
要素数:10000
Array#include?  0.170974   0.000680   0.171654 (  0.171660)
Array#find  1.535577   0.009384   1.544961 (  1.544990)
Array#bsearch  0.004513   0.000054   0.004567 (  0.004642)
Array#bsearch_index  0.004381   0.000000   0.004381 (  0.004384)
Set#include?  0.001445   0.000009   0.001454 (  0.001453)
Set#find  1.683042   0.008779   1.691821 (  1.691840)
要素数:100000
Array#include?  1.714387   0.007768   1.722155 (  1.722186)
Array#find 15.526816   0.069367  15.596183 ( 15.596378)
Array#bsearch  0.005219   0.000037   0.005256 (  0.005366)
Array#bsearch_index  0.005073   0.000009   0.005082 (  0.005084)
Set#include?  0.002169   0.000001   0.002170 (  0.002171)
Set#find 16.573293   0.083549  16.656842 ( 16.656929)

Array#bsearchとArray#bsearch_indexに速度の違いはほとんどないことがわかります。
ArrayもSetも要素を値指定で検索する際はfindではなくinclude?を使う方が速くなりました。また、Array#findとSet#findでは若干Array#findの方が早いようです。

そして結局は集合を扱うSetを使ったSet#include?が二分探索と比較しても一番高速でした。

まとめ

ソートされた配列を検索する際はArray#bsearchやArray#bsearch_indexで二分探索を行うと速く検索できることがわかりました。また、要素数が増えるにつれて二分探索と線形探索との性能差は大きくなるので、大量データを検索する時は非常に二分探索が効果的です。

ただし、すでに存在する配列に対して一度ソートを行ってから二分探索を行ってしまうとソート処理の分かえって速度が遅くなってしまうことがあるので注意が必要です。あくまで事前にソートされているデータで利用しましょう。

その他にも集合Setを使用することで要素の存在チェックを高速に行うことができます。
こちらもすでに配列で保持しているデータをSetに変換するとその分のコストが掛かり逆に遅くなってしまうので注意が必要です。