图文版 http://goo.gl/7WPkp 若想在不同的资料结构中套用相同的演算法操作资料，往往会使用 iterator pattern。Iterator 的原理很简单：不同的容器都要实作出具有相同介面的 iterator，把巡访资料的过程封装在 iterator 之中，使用者只需要知道如何 使用这个共通的 iterator 介面，就可以操作各式各样结构不同的容器。 传统的 iterator 实作方法，往往是把巡访容器时的状态储存在某个变数当中。 比如说巡访阵列时，会在 iterator 中储存阵列的 index；而在巡访 linked list 时则是储存其中一个 node。在更复杂的场合－－比如说树状结构的 iterator 可能要储存 stack，实作起来就没那麽简单了。然而带有 call stack 的 coroutine 却可以很漂亮地实做出这种复杂结构的 iterator。 简介 Lua Function 及 Closure 由於接下来会大量使用 closure，在这边先为不习惯 functional programming 的读者做简单的介绍。 Lua 中的函式属於 first-class object，它就像数字或字串那样，你可以把函 式存在变数当中、当作参数传进另一个函式、或是当成其它函式的回传值。 local foo = function(n) -- 把函式存在 foo 这个变数中 if n%7 == 0 then -- 检查 n 是不是 7 的倍数 print(n .." is dividable by 7.") end end foo(14) -- 印出 14 is dividable by 7. function check_between(min, max, checker) for i=min, max do -- 把 min 到 max 之间的数 checker(i) -- 都代入 checker 函式检查 end end check_between(10, 100, foo) -- 列出 10 到 100 之间所有 7 的倍数 把函式当作回传值则颇为微妙，因为这个回传的函式可以存取上一层的区域变数， 比如说以下这个例子： function make_counter() local c = 0 return function() c = c + 1 print("c = " .. c) end end local counter = make_counter() counter() -- 印出 c = 1 counter() -- 印出 c = 2 counter() -- 印出 c = 3 若依照一般对 C 语言的认知，区域变数在函式结束後就会消失，因此在回传的 函式中使用它似乎会造成非法记忆体存取。但在 functional programming 之 中，编译器会侦测出这类的外层变数（称之为 upvalue），并且把它绑在回传值 上。因此在呼叫 counter() 时，c 这个变数就彷佛全域变数般会永久存在，但 在 make_counter() 外部却又看不到。 这样的语言特性称之为 closure，而这也是 Lua iterator 的基础。 Lua 中的 Iterator Iterator 需要储存目前巡访容器的状态，比如说阵列的 index。C++ 或 Java 这类语言通常把这些状态包成物件，但 Lua 则是包装在 closure 之中： function array_iterator(array) local i = 0 -- 封装在 iterator 中的 index local n = #array -- 取得阵列长度 return function() i = i + 1 -- 指向下一个元素 if i <= n then -- Lua 阵列是 1 开始的 return array[i] else return nil end end end it = array_iterator({1, 1, 2, 3, 5}) local e = it() while e ~= nil do print(e) e = it() end Lua 中的 iterator 是个包含 upvalue 的 closure，每次呼叫时会回传下一个 元素，直到结束时回传 nil 为止。上述的 while 回圈看起来不是很直观，因此 Lua 提供了以下的 syntactic sugar： for e in array_iterator({1, 1, 2, 3, 5}) do print(e) end Lua 会自动把它转化成 while 回圈的形式。 使用 Coroutine 巡访阵列 在上一篇 coroutine 的简介中有提到，coroutine 可以视为「可中断及继续执行 的函式」，同时又能用 coroutine.yield() 来传递资料。因此我们可以把巡访容 器这件事写成 coroutine，以 yield 来回传容器中的元素，这麽一来就达成了 iterator 的目标：把巡访容器与操作元素的逻辑分离开。 使用 coroutine 改写上述的 array_iterator() 会变成下面这样子： function array_iterator2(array) local function visit() for i=1, #array do coroutine.yield(array[i]) end end local co = coroutine.create(visit) return function() local status, value = coroutine.resume(co) if status then return value else return nil end end end 现在这个 iterator 中只夹带了 co 这个 upvalue。每次在 iterator 前进到下 一个元素时，它只是重覆地呼叫 coroutine.resume() 让 coroutine 往下执行， 并取得其中使用 coroutine.yield 所传回的元素值。 看起来好像比原来的版本更复杂了？我们来试试不同行为的 iterator。 Shuffle Iterator 想像一个特别的 iterator，它同样会巡访整个阵列，但却会先输出奇数索引上的 元素，再输出偶数索引上的元素。 for e in shuffle_iterator({1, 2, 3, 4, 5, 6}) do print(e) -- 输出 1 3 5 2 4 6 end 制作这种 iterator 并不难，只是不太容易让人理解： function shuffle_iterator(array) local i = -1 local n = #array local even_mode = false return function() i = i + 2 if i > n then if even_mode or n < 2 then return nil else i = 2 even_mode = true end end return array[i] end end even_mode 是用来储存这个 iterator 是否走进了偶数索引区的状态。尽管这个 iterator 并不难，但若利用 coroutine 会更加直觉： function shuffle_iterator2(array) local function visit() for i=1,#array,2 do coroutine.yield(array[i]) end for i=2,#array,2 do coroutine.yield(array[i]) end end return coroutine.wrap(visit) end 我使用了 coroutine.wrap()，这个 Lua 内建函式做的事和我们之前做的一样： 把 coroutine 包装在 closure 之中，每次呼叫这个 closure 时，都等於呼叫 coroutine.resume()。 使用 coroutine 的写法，彷佛就只是单纯使用回圈把内容一一印出来，不同的 地方只在於把 print() 改成 coroutine.yield() 而已。这也意味着只要我们写 一份把容器内容印出来的程式码，它就可以马上改写成 iterator。 我们来看看更复杂的容器。 二元树的例子 现在我们的任务是制作二元树的 iterator，以中序的方式巡访。Lua 中的二元树 可以用 table 来表示： local binary_tree = { data = 5, left = { data = 3, left = { data = 1 }, right = { data = 4 } }, right = { data = 9, left = { data = 7, left = { data = 5.5 }, right = { data = 7.4} }, right = { data = 11 } } } 这颗树大概长这个样子： 5 ／ ＼ 3 9 ／| |＼ 1 4 7 11 ／ ＼ 5.5 7.4 制作二元树的 iterator 不算是个简单 (trivial) 的工作，但前面提到：只要 知道怎麽把内容印出来，就可以把这个过程利用 coroutine 转换成 iterator。 所以我们先用看起来最容易的方法，也就是递回，来把二元树印出来： function print_inorder(node) if node.left ~= nil then print_inorder(node.left) -- 巡访左边的 subtree end print(node.data) -- 印出这个 node 的资料 if node.right ~= nil then print_inorder(node.right) -- 巡访右边的 subtree end end 改成 coroutine iterator 就只是把它照抄一遍： function tree_iterator(root) local function visit_inorder(node) if node.left ~= nil then visit_inorder(node.left) end coroutine.yield(node.data) if node.right ~= nil then visit_inorder(node.right) end end return coroutine.wrap( function() visit_inorder(root) end ) end -- 计算元素总和 local sum = 0 for e in tree_iterator(binary_tree) do sum = sum + e end 如果不使用 coroutine，就相当於把递回的演算法改写成非递回的形式，而这样 的改写通常需要 stack 的协助，而导致结果不易理解。以下是改写成 iterator 的版本： function tree_iterator2(root) local node_stack = {} local function push_left_subtree(node) while node ~= nil do table.insert(node_stack, node) node = node.left end end push_left_subtree(root) return function() if #node_stack == 0 then return nil end local node = table.remove(node_stack) push_left_subtree(node.right) return node.data end end * * * * * * 使用 coroutine 实作 iterator 具有程式码简单易懂的特性，然而这也并非没 有缺点。因为 coroutine 内部保留了 call stack，通常它会比原本的 iterator 占用更多记忆体资源。 在下一篇文章，我会以游戏 UI 作为范例，介绍 coroutine 的另一个应用方式。 (不过我累了...明天再贴下一篇 别打我) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 202.39.238.241 ※ 编辑: littleshan 来自: 202.39.238.241 (07/08 17:55)