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 了。

正则表达式字面值的对象构建

之前曾谈到了字符串扣留的概念，那么对于 Ruby 的正则表达式 Regexp 类型来说，是否也有类似的常量池机制呢？

（注：以下输出的具体数字随环境而变，重要的是其前后的相等性）

我们可以做一个简单的测试：

2.times { p "foo".object_id }
2.times { p :foo.object_id }
2.times { p /foo/.object_id }

输出：

5712492
5712432
146408
146408
5713608
5713608

根据输出结果，我们似乎可以得出结论， Regexp 类型也有类似字符串扣留的机制。然而细心的人会进一步测试这段代码：

2.times { p Regexp.new(/foo/).object_id }

输出了两个不同的数字。这和之前的测试难道不是矛盾的吗？当然不是，这实际上和 Ruby 的语法分析器有关。

Ruby 支持正则表达式字面值（/…/）。对于官方的 Ruby 实现来说，其语法分析器会在接受一个正则表达式的单词（token）时生成该正则表达式对象。也就是说，字面值形式的正则表达式是在语法分析时生成的，也可以宏观地看作是在编译时生成的。因此，在运行时，虽然会多次调用 /foo/.object_id，但由于语法分析器只看到了一个正则表达式字面值，其接收者永远都是一个对象。

证明：

ObjectSpace.each_object(Regexp) { |r| p r }
/foo/

第一行是打印出当前的 Ruby 实例中所有 Regexp 对象，而这时解释器还没执行到第二行的字面值。实际的输出中，也确实包含 /foo/ 这个对象。

如果语法分析器看到两个正则表达式字面值，自然也就会生成两个 Regexp 对象了：

p /foo/.object_id, /foo/.object_id

输出：

5713896
5713812

字符串扣留

先从一个 Ruby 实例看起：

p "hello".object_id, "hello".object_id

object_id 可以获取一个对象的唯一标识，而这行代码打印出了不同的 ID，说明两次引用的字符串字面值生成了两个不同的字符串对象，但它们的内容是一致的。这在面向对象语言中是一个普遍的现象，在某些场合下可能会引起以下问题：

1. 当频繁使用 Ruby 的字面值指定某个字符串时，每次通过 Ruby 的字面值指定的字符串都会生成一个新的对象，长此以往就会产生大量的内容相同的字符串对象。这种空间的浪费意味着不必要的数据占用了更多的 Cache 和内存，减少了其它资源利用 Cache 的机会，也同时增加了内存分配和回收的复杂度；
2. 我们经常需要比较字符串是否相等（如散列表的键值比较），而无论是什么语言，底层的实现方法也无非是调用 memcmp、strcmp 之类的函数来比较内存，理论上这个过程需要 O(n) 的时间（n = 字符串长度），而如果这样的比较需要频繁进行，那代价也是不容忽视的。

当今不少高级语言中，都内置一种被称为“扣留”（Intern）的机制，它解决了这一难题。它的思想是：使用一个全局的字符串常量池来管理字符串，每次准备分配新的字符串对象之前，程序都会先检查内容相同的字符串对象是否已经被“扣留”在了常量池中，若是，则不分配新的对象，直接引用常量池中的对象；若不是则分配新的对象，并“扣留”在常量池中。这当然增加了字符串对象构造时的时间，但却解决了上述两种情况下的空间（没有产生字符串的克隆）和时间（逐字节比较字符串变为了指针相等的判断）效率问题。

这个机制最早由 Lisp 用来管理符号，后来也被 Python（intern(string)）、Java（String#intern）、.NET（String.intern） 等语言、平台继承，用来实现字符串的扣留。Ruby 通过符号表实现了符号对象的扣留机制，但内置的字符串对象并没有扣留。Ruby 的 String#intern 方法看似扣留，实则是把一个已有的字符串对象转换为符号对象。使用这个方法并不会节省内存，只能起到简化字符串比较的时间复杂度的作用。所以，在 Ruby 中，操作常量的字符串并处于上述两种情况时应该尽量使用符号而不是字符串。Ruby 1.9 的新 Hash 字面值支持一种更简洁的符号键语法糖，其设计目的就是为了推荐用户使用符号而不是字符串。