Ruby 之“Schwartzian 變換”

Ruby 的 Array#sort 和 Array#sort_by 在實現上有微妙差異。Array#sort 通過在每次迭代過程中直接比較元素来進行排序，而 Array#sort_by 在排序之餘還進行了一種優化，試圖減少計算元素“键”時帶來的開銷。

這裡所謂的“键”是用來衡量两个元素孰大孰小的一個標準，在元素是標量類型（即並非兩個或兩個以上域的複合結構）的情況下，鍵通常就是元素本身的值的大小；在元素是兩個或兩個以上域的複合結構時，鍵則通常是其域值的一個組合。比如，字符串可以看作是擁有 n 個字符域的複合結構，而在進行字符串排序時常用到的字典順序，就可以看作是所有字符域組合之下得出的鍵。

鍵的計算有時是昂貴的，而特定的排序算法在迭代過程中往往都需要多次獲取同一個元素的鍵，這就使得冗餘的鍵計算給整個排序帶來了不可磨滅的開銷。Array#sort_by 採用的優化技巧，實際上就是緩存優化（Memoization）的一個特例。所有元素的鍵都事先被 Array#sort_by 計算好，並和元素本身關聯在一起，儲存到另一個表中。之後對該表中計算好的鍵進行排序就同時排列了與之關聯的元素本身。最後，拋棄表中的鍵而返回所有元素本身，排序就完成了。這個優化在 Perl 編程中被反復地運用，最終成為了一個廣為人知的編程手法——“Schwartzian 變換”。在 Lisp 編程中，同樣的手法被稱為“decorate-sort-undecorate”。

Ruby 可以如下般實現 Schwartzian 變換：

class Array
  def my_sort
    map { |e| [ e, e.key ] }.sort { |a, b| a[1] <=> b[1] }.map { |e| e[0] }
  end
end

這和 Perl 的參考實現如出一轍（感謝 Ruby 的發散性！）——

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
               @unsorted;

可以簡單地來測試一下實際執行時的效率差別。首先給 Fixnum 打一個猴子補丁：

class Fixnum
  def key
    sleep 0.1
    self
  end
end

如此就可以在排列 Fixnum 時通過 Fixnum#key 這個“昂貴”的函數來獲取鍵。睡眠線程的語句只是為了偽造函數的開銷。

require 'benchmark'
include Benchmark

array = [3, 1, 2, 4]

bm(10) do |b|
  b.report('sort')    { array.sort { |a, b| a.key <=> b.key } }
  b.report('my_sort') { array.my_sort                         }
  b.report('sort_by') { array.sort_by { |e| e.key }           }
end

筆者本機輸出：

                user     system      total        real
sort        0.000000   0.000000   0.000000 (  1.000057)
my_sort     0.000000   0.000000   0.000000 (  0.400023)
sort_by     0.000000   0.000000   0.000000 (  0.400023)

可見 Array#sort 相比於 Array#sort_by 和 Array#my_sort 慢了許多。由於鍵計算函數的開銷是通過睡眠線程偽造的，所以雖然掛鐘時間不是零，但用戶時間加系統時間卻是零。

當然，Schwarzian 變換只是針對昂貴鍵計算排序的一種手法。很多時候我們都僅僅是在排列簡單的鍵，比如 Fixnum （或其它整型數據類型）本身，那附帶了 Schwarzian 變換的 Array#sort_by 由於多做了緩存鍵的工作，效率上自然就不如 Array#sort 了。