程式碼產生

wiki

自訂排序

顯然，針對不同的比較函式，可以針對 Shell 排序進行大幅度的加速。不過，並沒有明顯的標準可以判定哪些專屬版本會在特定的程式中發揮功能。我們可以利用 Lua 內建（且快速的）編譯器來根據範本在現場建立專屬版本，而不是去猜測哪些有用哪些沒用。Shell 排序非常適合，因為比較函式只在一個地方被呼叫。

我們想要最後得到一個函式，這個函式可以回傳一個專屬的排序函式，給定一個任意的 Lua 表達式，它代表比較。這個表達式將提供為字串；為了簡化處理，我們將堅持表達式使用變數 a 和 b 來表示被比較物件。例如，假設我們想要排序一個 Person 物件陣列，其中每個物件的樣貌為 {name = "Joe", age = 32, <other fields> } 。範例的呼叫看起來會像這樣

local sort_by_age = make_sorter  [[a.age < b.age]]

-- ... somewhere later on ...

sort_by_age(folks)

make_sorter 只會將它的引數插入到 Shell 排序範本中。為了讓範本運作，我們需要將 shellsort 內部的變數重新命名，這樣一來，被比較的數值最後會被呼叫為 a 和 b，以符合比較函式中的名稱。

我們的第一次嘗試看起來像這樣（感謝 DavidManura，他寫了下面的第二版本）

   function make_sorter(compare)
     local src = [[
       local incs = { 1391376,
                      463792, 198768, 86961, 33936,
                      13776, 4592, 1968, 861, 336, 
                      112, 48, 21, 7, 3, 1 }
 
       -- The value of the compiled chunk needs to be the sort function itself
       return function(t, n)
         for _, h in ipairs(incs) do
           for i = h + 1, n do
             local a = t[i]
             for j = i - h, 1, -h do
               local b = t[j]
               if not (]] .. compare .. [[) then break end
               t[i] = b; i = j
             end
             t[i] = a
           end 
         end
         return t
       end
     ]]
     return assert(loadstring(src, "Shellsort "..compare))()
   end

在產生程式碼之間共用共通資料

這運作得很好，但有一個小問題。在我們定義了 35 個不同的 Shell 排序器後，我們有 35 個 incs 陣列複本霸佔了儲存空間。（我們也有 35 個客製化排序函式，但它們實際佔用的空間較少。）我們想做的是對每個專屬的排序函式使用相同的 incs 陣列。

透過 Lua 5.1.1，我們可以將引數傳遞到新編譯的區段中，在這些區段中，這些引數可用作 ... 的值。因此，我們不會只呼叫區段取得排序函式，並在每個區段中編譯新的 incs 陣列，而是直接將主 incs 表格傳遞進去作為引數

   local incs = { 1391376,
                  463792, 198768, 86961, 33936,
                  13776, 4592, 1968, 861, 336, 
                  112, 48, 21, 7, 3, 1 }
   function make_sorter(compare)
 
     -- The first line captures the argument to the chunk
     local src = [[
       local incs = ...
       return function(t, n)
         for _, h in ipairs(incs) do
           for i = h + 1, n do
             local a = t[i]
             for j = i - h, 1, -h do
               local b = t[j]
               if not (]] .. compare .. [[) then break end
               t[i] = b; i = j
             end
             t[i] = a
           end 
         end
         return t
       end
     ]]
     -- We have to call the compiled chunk with incs:
     return assert(loadstring(src, "Shellsort "..compare))(incs)
   end

結合程式碼產生和備忘

現在，我們可以輕鬆產生專屬的排序器，但它仍然有點麻煩。隨著應用程式成長，我們會發現，我們在不同的模組中重複產生相同的排序器。此外，思考每一個排序函式的名稱，並針對每個排序函式呼叫 make_sorter，會有點惱人。如果我們可以將比較直接放在實際呼叫中，會更好。換句話說，我們最後得到了一個像這樣的東西

local sort_by_age = make_sorter [[a.age < b.age]]
local sort_by_name = make_sorter [[a.name < b.name]]
-- This is inefficient, but simple. See below for an improvement.
local sort_by_number_of_children = make_sorter [[#(a.children or {}) < #(b.children or {})]]

-- ... much later ...

function show_offspring(grandmom)
  -- Arrange the families so the smallest ones come first
  sort_by_number_of_children(grandmom.children)
  -- In each family, sort the grandkids, if any, by age 
  for _, child in pairs(grandmom.children) do
     if child.children then sort_by_age(child.children) end
  end
end

但是現在我們才發現，我們其實希望以最大的家族排在第一優先順序來對家族進行排序，而且我們根本不使用 sort_by_name。因此我們有程式維護問題。

現在，我們可以在需要時建立分類器，如下述方式

function show_offspring(grandmom)
  -- Arrange the families so the largest ones come first
  make_sorter[[#(a.children or {}) > #(b.children or {})]](grandmom.children)
  -- In each family, sort the grandkids, if any, by age 
  for _, child in pairs(grandmom.children) do
     if child.children then make_sorter[[a.age < b.age]](child.children) end
  end
end

似乎好一點，雖然有很多標點符號。但是，這表示我們會呼叫 make_sorter 很多次，即使 Lua 編譯器特別快，這仍然是過量工作。

幸運的是，使用 Lua 我們能享有並吃掉我們的蛋糕。我們可以建立一個由比較字串編製索引的排序函數表格，然後讓 Lua 在需要時建立函數，一種虛擬表格。此技術稱為記憶化，表示記憶體：可能會再次使用的複雜運算結果會根據函數實際的引數記住。（有時也會稱作快取，但這個字在許多情況下都會用到。）

我們可以在 make_sorter 的定義中寫入快取，但記憶化是相當常見的 LuaDesignPatterns，所以我們最好使用一個通用解決方案，特別是因為它非常簡單

-- Make this part of your standard Lua library. You'll find yourself using it a lot

-- Given a function, return a memoization table for that function
function memoize(func)
  return setmetatable({}, {
    __index = function(self, k) local v = func(k); self[k] = v; return v end,
    __call = function(self, k) return self[k] end
  })
end

現在，我們可以使用單一行程式碼將 make_sorter 變成一個記憶化表格

Shellsorter = memoize(make_sorter)

而且我們可以安全編寫 show_offspring，確信它最多會在應用程式的生命週期中編譯兩次

function show_offspring(grandmom)
  -- Arrange the families so the largest ones come first
  Shellsorter[ "#(a.children or {}) > #(b.children or {})" ](grandmom.children)
  -- In each family, sort the grandkids, if any, by age 
  for _, child in pairs(grandmom.children) do
     if child.children then Shellsorter[ "a.age < b.age" ](child.children) end
  end
end

請注意，我用 Shellsorter 上的一個索引取代對 make_sorter 的呼叫。上面提供的 memoize 實作讓這件事變得不必要；我可以像使用函數一樣使用 Shellsorter。這種方法有時會對你有用，進一步說明這個技術的細節於 FuncTables。不過，在此例中，它似乎沒有增加任何清晰度，反而只會建立不必要的函數呼叫。

插曲：Schwartzian 轉換

在排序中使用的比較，通常（但並不總是）可以表示為 f(a) < f(b) 的形式，其中 f 是一個函數。f(a) 的值通常稱為特徵。

例如，我們可能需要根據它們與某個參考點的距離，對三維空間中的點陣列進行排序。它的天真版本會是

function distance(x, y) return ((x[1]-y[1])^2 + (x[2]-y[2])^2 + (x[3]-y[3])^2)^0.5 end
Shellsorter[" distance(a, ref) < distance(b, ref) "](array)

稍加思考應該能想到建議移除平方根運算會比較好，因為它對最終結果沒有影響。即使如此，運算還是有點耗時。粗略來說，大多數排序演算法都會執行大約 N log₂N 的比較，來對一個含有 N 個物件的陣列進行排序，表示上面的 distance 會在 N 個物件上被呼叫 2N log₂N 次；換句話說，它會在每個物件上被呼叫 2 log₂ N 次，每次產生相同結果。如果我們有，舉例來說，100,000 個點，表示每個點大約會呼叫 distance 34 次。上面有關記憶化的討論建議，在每個物件上只需要呼叫它一次。

特性值不一定要是數字；它們只需要比原始值更容易做比較即可。例如，依據語言規則對字進行排序，可透過將每個字轉換為較長字串來執行，此字串可以透過簡單字串比較進行比較。（請參閱 Posix 中的 strxfrm() 函數。）

依據特性函數進行排序最簡單的方法，是先計算各元素的特性，建立成對陣列 {特性值, 元素} 。接著可以用更簡單的比較函數對此陣列執行排序，然後僅選取每對陣列的第二個元素即可將已排序好的陣列轉回物件陣列。此方法是 Perl 的常用慣用語，稱為Schwartzian 轉換，其名稱來自著名的 Perl 駭客 Randall Schwartz。 [維基百科]

但直接將 Perl 慣用語翻譯成 Lua 卻非常沒有效率，這是因為成對陣列會使用極大的空間。不過，有一個類似的解決方案，可以用來優雅地解決排序非陣列表格的相關問題。

一般來說，Lua 表格是將鍵對應到值的映射集合

T = {k₁→v₁, k₂→v₂, … kn→vn}

為了提供此表格的有序檢視，我們可以建立一個鍵陣列

K = {1→k₁,2→k₂, … n→kn;}.

接著我們可以逐一檢閱鍵陣列，並使用如下的迭代器在原始表格中查詢鍵值對

function pairs_in_order(T, K)
  local i = 0
  return function iter()
    i = i + 1
    local k = K[i]
    if k then return k, T[k] end
  end
end

為了對此表格進行排序，我們可以建立一個第三個表格，即為將鍵對應到特性值的特性表格

C = {k₁→f(k₁, v₁), k₂→f(k₂, v₂), … kn→f(kn, vn)}

請注意，我們已將特性函數同時指派給鍵和值，因為這兩個值有可能會參與排序順序。接著我們會對鍵陣列進行排序，並在特性表格中逐一查詢每個鍵

-- K = keytable(T)
K = {}; for k in pairs(T) do K[#K+1] = k end
-- C = map(f, T)
C = {}; for k, v in pairs(T) do C[k] = f(k, v) end
-- Sort
Shellsorter["C[a] < C[b]"](K)
-- Get rid of C (see below)
C = nil
-- Iterate the sorted key, value pairs
for k, v in pairs_in_order(T, K) do
  print(k, v)
end

這種技術無論原始表格中的鍵為何，都適用。因為鍵會指派給比較函數，因此，如果值的特性相等，我們可以退回鍵的比較結果以確保穩定的排序；我們僅需要使用以下指令替換 sort

Shellsorter["C[a] < C[b] or C[a] == C[b] and a < b"](K)

但這裡有一個問題：我們真的希望這些輔助表格能是區域變數；尤其是特性表格，它是暫時性的值，且我們希望它在盡可能短的時間內被垃圾回收。但我們所編寫的程式碼產生機制不允許比較函數參照上層變數。

衛生巨集

通常，我們想要將一段程式碼插入到樣板中。然而，倘若所插入的程式碼在插入點具有已被繫結的自由變數，就可能會造成難以偵測的問題。

待續...

另請參閱

• ExPattern - 程式碼產生範例
• ListComprehensions - 程式碼產生範例