Lua 協同程序對比 Python 生成器

wiki

Python 生成器與 Lua 協同程序有何不同？最重要的特點是，在 Lua 中，coroutine.yield() 是一個可以在 coroutine.resume() 的動態範圍內的任何位置呼叫的一般函數，但限製條件是您不能透過 C 回呼 (callback) 來 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

然後可以在 for 迴圈中將 Lua 函數用作反覆運算元

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

或作為某種類型的 foreach 函數

inorder(print, t)

為了將遞迴生成器的比較減至最低限度，我撰寫了一對簡單程式來產生無限 [Ruler 函數]。（一個關於此函數更有趣的頁面是 Michael Naylor 的 [Abacaba-Dabacaba]，其中包含一段音樂探討。）

Ruler 函數可以非遞迴地產生，但在這個範例中，它代表類似深度的優先搜尋的東西，所以我們只看遞迴實作。這些程式會產生序列中前 2^k 個值，並將它們加總起來作為一種有效性測試，因為很容易證明 Ruler 函數的前 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