Lua协程与Python生成器

wiki

Python生成器与Lua协程有何区别？最重要的是，在Lua中，coroutine.yield()是一个普通的函数，可以在coroutine.resume()的动态范围内任何地方调用，但限制是不能通过C回调yield（除非使用MikePall的[Coco]库）。在Python中，yield是语法上的，只能出现在生成器函数的词法体中。

这意味着Python生成器必须编写为生成器，不能轻易地分解成更小的函数；也不能轻易地递归。可以通过一种链式形式实现递归；[Python邮件列表]上的一条消息描述了这种机制

!Python
def inorder(t):
     if t:
         for x in inorder(t.left):
             yield x
         yield t.label
         for x in inorder(t.right):
             yield x

在Lua中，可以将一个更通用的inorder函数编写为高阶函数

function inorder(f, t)
  if t then
    inorder(f, t.left)
    f(t.label)
    return inorder(f, t.right)
  end
end

然后，Lua函数可以在for循环中用作迭代器

for label in coroutine.wrap(inorder), coroutine.yield, t do
  -- something with label
end

或者用作一种foreach函数

inorder(print, t)

为了将递归生成器的比较简化到最小程度，我编写了一对简单的程序，它们生成无限的[尺子函数]。（关于此函数更有趣的页面是Michael Naylor的[Abacaba-Dabacaba]，其中包括音乐探索。）

尺子函数可以非递归地生成，但在本例中，它代表着类似于深度优先搜索的东西，因此我们只关注递归实现。程序生成序列中的前2^k个值，并将它们加起来作为一种有效性测试，因为很容易证明尺子函数前2^k个元素的总和为2^(k+1)-1。Python的内置函数和标准库在这里很方便；在Lua中，我不得不自己实现sum和islice（序列的前k个元素）函数，但幸运的是这并不难。

以下是Lua实现

function ruler(put, k)
  for i = 1, k do
    put(i)
    ruler(put, i-1)
  end
end
 
function eachruler()
  return coroutine.wrap(function()
    return ruler(coroutine.yield, 100)
  end)
end
 
function sumseq(k, f, o, s)
  local sum = 0   
  for v in f, o, s do
    k, sum = k-1, sum + v
    if k <= 0 then break end
  end        
  return sum
end
 
local howmany = tonumber(arg[1]) or 24
local now = os.clock()
local sum = sumseq(2^howmany, eachruler())
local took = os.clock()-now
print(("%2i: %7.3f seconds  %i check %i"):format(howmany, took, sum, 2^(howmany+1)-1))

以及非常相似且略短的Python实现

!Python
from itertools import islice
from sys import argv
from time import clock
 
def ruler(k):
  for i in range(1, k+1):
    yield i
    for x in ruler(i-1): yield x
 
howmany = int(argv[1])
now = clock()
total = sum(islice(ruler(100), 2**howmany))
took = clock()-now
print "%2d: %7.3f seconds %d check %d" % (howmany, took, total, 2**(howmany+1)-1)

递归的略微奇怪的公式是手动将尾调用更改为for循环的结果，因为 Python 不支持尾调用，而原始的尾调用实现让 Python 处于更加不利的境地。

由于两个程序都通过了检查，我将只在此处粘贴比较计时结果（以秒为单位，如上所述）。我不认为这仅仅是“Lua 比 Python 快”的基准测试；我认为这表明协程本质上更快；主要区别在于不必通过一系列 yield 传递值。

 N      Lua   Python
--    -----   ------
12:   0.000    0.008
13:   0.000    0.023 
14:   0.008    0.055 
15:   0.016    0.109 
16:   0.031    0.227 
17:   0.078    0.469 
18:   0.148    0.961 
19:   0.305    1.961 
20:   0.602    4.000 
21:   1.211    8.148 
22:   2.430   17.211 
23:   4.820   40.094 
24:   9.875   94.992