blog.jiikko.com

アプリケーションで更新頻度の少ない都道府県テーブルのような情報は、メモリに乗せっぱなしにしている実装が多いと思う。
以下rubyのコード。

def find_prefecture(id)
  prefecture_ids.find { |prefecture_id| prefecture_id == id }
end

あたりまえだけど逐次検索を二分探索に置き換えると計算量が減る。
rubyにはArray#bsearchがあるのですぐ使える。最高。
https://docs.ruby-lang.org/ja/latest/method/Array/i/bsearch.html
http://magazine.rubyist.net/?0041-200Special-note#l15

require 'benchmark'

def prefecture_ids
  (1..47).to_a
end

def sequential_search(id)
  prefecture_ids.find { |prefecture_id| prefecture_id == id }
end

def binary_search(id)
  prefecture_ids.bsearch { |prefecture_id| prefecture_id == id }
end

Benchmark.bm do |bm|
  bm.report 'binary_search'.ljust(15) do
    100.times do
      (1..47).each do |id|
        binary_search(id)
      end
    end
  end

  bm.report 'sequential'.ljust(15) do
    100.times do
      (1..47).each do |id|
        sequential_search(id)
      end
    end
  end
end

#リストから見つかる時
user     system      total        real
binary_search    0.010000   0.000000   0.010000 (  0.013782)
sequential       0.030000   0.000000   0.030000 (  0.030816)

#リストから見つからない時
user     system      total        real
binary_search    0.020000   0.000000   0.020000 (  0.015359)
sequential       0.030000   0.000000   0.030000 (  0.033846)

逐次検索は、先頭から舐めていくので欲しい情報が最後にあったり、リストに存在していないと計算量が最大になる。
二分探索するにはリストがソートされている必要があり、
リストの更新頻度が多いケースだと複雑になってしまう可能性があるので逐次処理のままでもいいと思う。