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

降順と昇順を組み合わせたソート - わさっき，降順と昇順を組み合わせたソート〜データ生成 - わさっき，降順と昇順を組み合わせたソート〜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すればいいのですね．

わさっきhb

大学（教育研究）とか，親馬鹿とか，和歌山とか，とか，とか．

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