代码生成

wiki

自定义排序

很明显，通过针对不同的比较函数专门化，可以显著提高希尔排序的速度。但是，没有明显的标准来决定哪些专门化的版本在特定程序中会很有用。与其试图猜测哪些有用，哪些无用，我们可以利用 Lua 的内置（且快速）编译器来创建专门化的版本，使用模板。希尔排序特别适合这种情况，因为比较函数只在一个地方调用。

我们希望最终得到一个函数，该函数返回一个专门的排序函数，该函数接受一个表示比较的任意 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只是将它的参数插入到希尔排序模板中。为了使模板工作，我们需要重命名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 个不同的希尔排序器之后，我们得到了 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的定义中，但记忆化是一种非常常见的Lua设计模式，所以我们不妨使用一个通用的解决方案，尤其是因为它非常简单

-- 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 命名。 [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 - 代码生成示例