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