Array : sort 的陷阱與 sort vs sort_by


#1

大概就是工作需求,需要做有趣的 sort … 以下 demo

起手式陷阱 error …

[[1,nil] , [2,true] , [3,false]].sort
#=> [[1, nil], [2, true], [3, false]]

[[1,nil] , [1,true] , [2,false]].sort
# ArgumentError: comparison of Array with Array failed

[[1,nil] , [1,true] , [2,false]].sort{|i,j|i[0]<=>j[0]}
#=> [[1,nil], [1,true], [2,false]]

[[1,nil] , [1,true] , [2,false]].sort_by{|i|i[0]}
#=> [[1,nil], [1,true], [2,false]]

所以如果為 Array 且希望由第一個欄位做 sort 則希望強制指定,否則會遞迴由第二欄位做比較,其實真正實作如下

  0 <=> 0    #=>   0 # =
  9 <=> 3    #=>   1 # >
  2 <=> 7    #=>  -1 # <
nil <=> true #=> nil #無法比較,所以 sort 出 exception ...

繼續如同這篇所測 …

require 'benchmark'

puts "Running Ruby #{RUBY_VERSION}"

ary = []
1000.times {
  ary << {:bar => rand(1000)}
}

n = 500

puts "n=#{n}"
Benchmark.bm(20) do |x|
  x.report("sort")               { n.times { ary.dup.sort{ |a,b| b[:bar] <=> a[:bar] } } }
  x.report("sort reverse")       { n.times { ary.dup.sort{ |a,b| a[:bar] <=> b[:bar] }.reverse } }
  x.report("sort_by -a[:bar]")   { n.times { ary.dup.sort_by{ |a| -a[:bar] } } }
  x.report("sort_by a[:bar]*-1") { n.times { ary.dup.sort_by{ |a| a[:bar]*-1 } } }
  x.report("sort_by.reverse")    { n.times { ary.dup.sort_by{ |a| a[:bar] }.reverse } }
  x.report("sort_by.reverse!")   { n.times { ary.dup.sort_by{ |a| a[:bar] }.reverse! } }
end

# >> Running Ruby 2.1.1
# >> n=500
# >>                            user     system      total        real
# >> sort                   0.670000   0.000000   0.670000 (  0.667754)
# >> sort reverse           0.650000   0.000000   0.650000 (  0.655582)
# >> sort_by -a[:bar]       0.260000   0.010000   0.270000 (  0.255919)
# >> sort_by a[:bar]*-1     0.250000   0.000000   0.250000 (  0.258924)
# >> sort_by.reverse        0.250000   0.000000   0.250000 (  0.245179)
# >> sort_by.reverse!       0.240000   0.000000   0.240000 (  0.242340)

其實你會感覺一定要用 sort_by 啊,因為比較快 … 但其實你改成類似 5.times & n = 500000 整個結果就會反轉,細節不詳述(大概就是一個抓出來比,一個還要塞回去後直接比的差別),所以應該依照資料量來做選擇才是(自己測過的東西才是真的|||)

hmm… 雖然我還是愛用 sort 就是 … 因為資料通常沒很大且反著寫就是 reverse 了,而其實底層實作應該都是 linked list,所以 reverse 只需要改 header 即可,不需要真正的位移資料,而也可能是 circular linked list ,因為負值的 index 後會很好追,不過這話題請見資料結構,以上


#2

RubyDoc 上面就有提到[^1],當前實做的 sort_by 會建立一個陣列,裡面為原值與映射值的內容,所以 sort_by 在被排序的元素量較少的時候,會導致他比 sort 慢很多。

The current implementation of sort_by generates an array of tuples containing the original collection element and the mapped value. This makes sort_by fairly expensive when the keysets are simple.

但是在排序時建立映射值成本很高的時候就可以大幅的加速,例如以下範例:

files = Dir["*"]
sorted = files.sort { |a, b| File.new(a).mtime <=> File.new(b).mtime }
sorted   #=> ["mon", "tues", "wed", "thurs"]

上述使用 sort 方法來取得每個檔名對應的檔案修改時間時,每次比較時都會建立一次 File 物件(還有 Time 物件)。為了避免上述情況,我們可以在排序時建立一個 cache,大致上可以寫成如下形式:

sorted = Dir["*"].collect { |f|
   [File.new(f).mtime, f]
}.sort.collect { |f| f[1] }
sorted   #=> ["mon", "tues", "wed", "thurs"]

這剛好就是 sort_by 內部實做的邏輯,換成 sort_by 只要寫成:

sorted = Dir["*"].sort_by { |f| File.new(f).mtime }
sorted   #=> ["mon", "tues", "wed", "thurs"]

所以 sort_by 在被排序項目在 (1) 需要映射比對值的時候;(2) 求映射值的過程成本較高的時候,會比 sort 來划算。

[^1]: ref: https://ruby-doc.org/core-2.5.0/Enumerable.html#method-i-sort_by