読者です 読者をやめる 読者になる 読者になる

コモディティ化するエンジニア

組み込み系のSI屋から、Railsを扱うWeb系のベンチャーに転職した筆者が、日々ミジンコなりに情報を綴るブログ。

Rubyの Set / Array それぞれの検索速度を比較してみた

Ruby

RubyではArrayよりSetの方が高速に検索(include?)できるとのことですが、実際どのぐらいの差があるか調べてみました。

実行環境

以下の通りです。

$ ruby -v          
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-darwin15]

計測に使うコード

require './process_measure.rb'
require 'set'

array = Array.new
set = Set.new
10001.times { |i| array.push("#{i}") }
10001.times { |i| set.add("#{i}") }

6.times do |i|
  str = "#{i * 2000}"
  puts "-------------------- #{str} --------------------"
  measure_do { array.include?(str) }
  measure_do { set.include?(str) }
end

process_measure.rbについては、以下の記事をご参照ください。

muramurasan.hatenablog.jp

計測結果

$ ruby set_array.rb
-------------------- 0 --------------------
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000007)
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000005)
-------------------- 2000 --------------------
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000071)
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000004)
-------------------- 4000 --------------------
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000115)
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000004)
-------------------- 6000 --------------------
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000170)
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000004)
-------------------- 8000 --------------------
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000395)
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000008)
-------------------- 10000 --------------------
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000576)
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000008)

考察

Setの方が明らかに高速ですね。 Arrayは先頭から順番に検索するんでしょうか? 検索対象が後ろになればなるほど遅くなる傾向にあります。

Arrayは便利なメソッドがたくさんありますが、追加/削除/検索しかせず、値が重複しないならばSetを使う方が良いですね。