代码生成

wiki

定制排序

很明显，通过为不同的比较函数专门化 shellsort，可以大大提高其速度。然而，没有明显的标准来决定在特定程序中哪些专门化的版本会很有用。我们不必猜测哪些有用，哪些无用，而是可以利用 Lua 内置的（并且快速的）编译器，通过模板即时创建专门化的版本。Shellsort 特别适合这一点，因为比较函数只在一个地方被调用。

我们希望最终得到一个函数，该函数接收一个代表比较的任意 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 sort 模板中。为了使模板能够工作，我们需要重命名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 sorter 后，我们有 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

将代码生成与记忆化结合起来

现在我们可以轻松地生成专门化的 sorter，但仍然有点笨拙。随着应用程序的增长，我们发现我们在不同的模块中反复生成相同的 sorter。此外，为每个排序函数想一个名字，并为每个函数调用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。所以我们有一个代码维护问题。

现在，我们可以在需要时创建 sorter，如下所示：

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

请注意，我已经将对make_sorter的调用替换为对Shellsorter的索引。上面提供的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函数将被调用2N log₂N次，总共针对N个对象；换句话说，它将被调用2 log₂ N次针对每个对象，每次都产生相同的结果。如果我们有，比如说，100,000 个点，那么每个点大约需要调用 34 次distance。上面对记忆化的讨论表明，应该有可能对每个对象只调用一次。

特征不一定是数字；它们只需要比原始值更容易比较即可。例如，根据给定语言的规则对单词进行排序，可以通过将每个单词转换为一个更长的字符串来实现，该字符串可以与简单的字符串比较进行比较。（请参阅 Posix 中的strxfrm()函数。）

按特征函数排序的最简单方法是，首先计算每个元素的特征，构造一个键值对数组 {characteristic, element} 。然后可以使用一个简单的比较函数对该数组进行排序，然后通过仅选择每个对的第二个元素将排序后的数组还原为对象数组。这种方法在 Perl 中是一种常见的习惯用法，在那里它被称为Schwartzian 变换，以著名的 Perl 黑客 Randall Schwartz 的名字命名。[wikipedia]

然而，将 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

此技术适用于原始表中的任何键。更重要的是，因为键被提供给比较函数，我们可以通过在值特征相等时回退到键比较来确保稳定排序；我们只需将排序替换为：

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

但有一个问题：我们实际上希望辅助表是局部变量；特别是，特征表是一个临时值，我们希望它尽快被垃圾回收。但我们所做的代码生成不允许比较函数引用上值。

卫生宏

通常，我们希望将一段代码插入到样板模板中。但是，如果插入的代码有一个自由变量，而该变量恰好在插入点被绑定，这可能导致晦涩的问题。

待续...

另请参阅

• ExPattern - 代码生成示例
• ListComprehensions - 代码生成示例