わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

降順と昇順を組み合わせたソート〜時間を計る

降順と昇順を組み合わせたソート - わさっき降順と昇順を組み合わせたソート〜データ生成 - わさっき降順と昇順を組み合わせたソート〜4つのソート方法 - わさっきの続きです.
ソートに要する時間を計測するようにしました.

#!/usr/bin/env ruby

# ddsort.rb

require 'date'
require 'digest/md5'

def generate(seed = 20080722,
             date_from = Date.new(2008, 4, 1),
             date_to = Date.new(2009, 3, 31))
  srand(seed) if seed
  array = []

  date_from.upto(date_to) do |date|
    num_max = rand(10)
    1.upto(num_max) do |num|
      array.insert(rand(array.size + 1), "#{date.strftime('%Y%m%d')}-#{num}")
    end
  end

  array
end

def sort1(array)
  array.sort {|a, b|
    a1 = a[0, 8]
    a2 = a[9, 1]
    b1 = b[0, 8]
    b2 = b[9, 1]
    if a1 != b1
      b1 <=> a1
    else
      a2 <=> b2
    end
  }
end

def sort2(array)
  inv = Hash[%w(0 1 2 3 4 5 6 7 8 9).zip(%w(9 8 7 6 5 4 3 2 1 0))]
  array.sort_by {|a| a.sub(/([0-9])$/) {inv[$1]}}.reverse
end

def sort3(array)
  array.sort_by {|a| a.to_i * 10 - a[-1, 1].to_i}.reverse
end

def sort4(array)
  array.sort_by {|a| ((99999999 - a.to_i) * 10) + a[-1, 1].to_i}
end

def sort5(array)
  array.sort_by {|a| (a.to_i << 4) - a[-1, 1].to_i}.reverse
end

def sort6(array)
  array.sort_by {|a| ((99999999 - a.to_i) << 4) + a[-1, 1].to_i}
end

def time
  t1 = Time.now
  result = yield
  t2 = Time.now
  [t2 - t1, result]
end

def time_sort1(array); time {sort1(array)}; end
def time_sort2(array); time {sort2(array)}; end
def time_sort3(array); time {sort3(array)}; end
def time_sort4(array); time {sort4(array)}; end
def time_sort5(array); time {sort5(array)}; end
def time_sort6(array); time {sort6(array)}; end

dates_random = generate(20080722, Date.new(2000, 1, 1), Date.new(2009, 12, 31))
trial = 5

if false
  require 'pp'
  dates_sorted = sort4(dates_random)
  pp dates_sorted
  exit
end

1.upto(6) do |i|
  tsum = 0
  method_sort = "sort#{i}"
  puts "#{method_sort}:"
  trial.times do |j|
    t, dates_sorted = send("time_#{method_sort}", dates_random)
    puts "  trial #{j + 1}: #{t} sec, digest=#{Digest::MD5.hexdigest(dates_sorted.inspect)}"
    tsum += t
  end
  puts "  average: #{tsum / trial} sec"
end

メソッドのうち,generateとsort1〜sort4は,すでに書いたものです.sort5とsort6は,「掛け算10倍」よりも,「シフト演算で16倍」のほうが演算速度が速いのではと思って定義した関数です.
timeが時間を計測するメソッドで,「t, a = time {処理}」と書けば,aに処理の結果が,tに処理に要した時間が格納されます.時間はTime.nowの差を取りましたので,サーバに負担がかかっているときなんかは,それに依存して時間がかかることになります.正味の処理時間を得るなら,Process.timesだろうなあと思いながら,コードを作ってみたのですが,Time.nowよりも時間が多めになり,回数ごとのばらつきは両者でほぼ差がありませんでした.
time_sort1〜time_sort6は,timeとsort_1〜sort6を組み合わせただけのメソッドですが,これらは,組み込み関数sendの第1引数として,ループによって呼び出す関数を変えるようにしています.
時間測定用の日付は,2000年の元日から,2009年の大みそかまでに広げています.
ソート結果は膨大になるので出力しません.確認するには,「if false」を「if true」にします.「sort4」を変更する必要もあるかもしれません.このあたりは,整理をしないことにしました.
とはいえ,ソート結果を出さないとなると,あるメソッドだけ不要な処理を入れていたりショートカットをしていたりで,結果が異なっていることがあるとまあ不安ですので,MD5によるメッセージダイジェストを出力することにしました.もちろんその計算や出力は,時間測定の対象外です.
さて,手元で実行した結果は次の通り.

$ uname -a
CYGWIN_NT-6.0 duo 1.5.25(0.156/4/2) 2008-03-11 10:31 i686 Cygwin
$ ruby -v
ruby 1.8.7 (2008-06-09 patchlevel 5000) [i386-cygwin]
$ ruby ddsort.rb
sort1:
  trial 1: 1.095 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 2: 1.126 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 3: 1.108 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 4: 1.113 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 5: 1.106 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  average: 1.1096 sec
sort2:
  trial 1: 0.156 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 2: 0.155 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 3: 0.157 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 4: 0.157 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 5: 0.179 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  average: 0.1608 sec
sort3:
  trial 1: 0.081 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 2: 0.075 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 3: 0.077 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 4: 0.079 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 5: 0.059 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  average: 0.0742 sec
sort4:
  trial 1: 0.059 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 2: 0.08 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 3: 0.076 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 4: 0.075 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 5: 0.079 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  average: 0.0738 sec
sort5:
  trial 1: 0.077 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 2: 0.075 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 3: 0.059 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 4: 0.061 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 5: 0.08 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  average: 0.0704 sec
sort6:
  trial 1: 0.115 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 2: 0.101 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 3: 0.1 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 4: 0.12 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  trial 5: 0.104 sec, digest=d9ab60c5d0d3fbc8d1c270686fd07234
  average: 0.108 sec

結果を見ると,sortを使うsort1が最も悪く,sort_byを使う中では,文字列処理でキーを生成するsort2が悪く,sort6がその次で,sort3〜sort5は大差なしと分かります.
しかしreverseを使わないsort4とsort6を比べて,これだけの差が出るのはおかしいです.
これはもしかして,sort6の場合,キーがBignumになるからかなと考えて,irbで確認してみました.

$ irb
irb(main):001:0> 20080728.class
=> Fixnum
irb(main):002:0> ((99999999 - 20080728) * 10 + 9).class
=> Fixnum
irb(main):003:0> (((99999999 - 20080728) << 4) + 9).class
=> Bignum
irb(main):004:0> (99999999 - 20080728) * 10 + 9       
=> 799192719
irb(main):005:0> ((99999999 - 20080728) << 4) + 9       
=> 1278708345
irb(main):006:0> ((99999999 - 20080728) * 13 + 9).class
=> Fixnum
irb(main):007:0> ((99999999 - 20080728) * 14 + 9).class
=> Bignum

もとのddsort.rbで,sort4の中の「* 10」のところを「* 13」にしても時間はほぼ同じで,「* 14」にすると,sort6と同じに上がりました.
まとめ:

  • sortよりもsort_byのほうが高速.
  • sort_byでキーを作るとき,文字列処理して作るよりも整数値にするほうが高速.
  • sort_byでキーを作るとき,BignumよりもFixnumのほうが高速.

まとめを書きながら思ったのですが,上のコードでは,sort_byでキーを作るときに時間がかかるのか,それともsort_byで作ったキーを比較するのに時間がかかるのかが,見極められていません.やろうと思えば,mapでキーを作って,そのあとsortすればいいのですね.