generic for

最后更新于:2022-04-01 20:44:13

下面写一下怎么给generic***for ***写迭代器。 ## 1. 迭代器和闭包 在Lua中,迭代器用function表示,每次调用该function,都会返回集合中的next元素。 每个迭代器都要在连续的调用之间保存一些state,这样才能知道进行到哪一步,下一步该从哪开始处理。在Lua中,闭包可以处理这个问题。闭包结构包含两个function:一个是闭包本身,另一个是factory,用来创建闭包。下面是个简单的示例: ~~~ function values(t) local i = 0 return function () i = i + 1; return t[i] end end ~~~ 在上面的例子中,values是factory。每次调用factory,都会创建一个新的闭包(迭代器本身)。该闭包在变量t和i中保存state。每次调用这个迭代器,都会从t中返回next元素的值。返回最后一个元素后,它会返回nil,标志着迭代器结束。 可以将上面的迭代器用在***while ***中,但是用generic***for ***更简单: ~~~ t = {10, 20, 30} function value(t) local i = 0 return function () i = i + 1; return t[i] end end iter = value(t) while true do local element = iter() if element == nil then break end print(element) end t = {1, 2, 3} for element in value(t) do print(element) end ~~~ 执行结果如下: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-09-06_57ce5eefa9aeb.PNG) generic***for ***为迭代器循环过程在内部保存state,不需要iter变量;每次迭代都调用该迭代器,并在迭代器返回nil时停止循环。 下面是一个复杂点的例子,从当前输入的文件中遍历所有的word。遍历过程中保存两个值:当前行(变量line),当前位置(pos),***string.find ***函数从当前行中搜索一个word,用'%w+'匹配,在匹配到word后,将当前位置pos置于该word之后的第一个字符处,并返回该word。否则,迭代器读入一个新行再重复上面的过程。如果没有更多的行,返回nil,标志迭代结束。 ~~~ function allwords () local line = io.read() local pos = 1 print("allwords begin") return function () while line do local s, e = string.find(line, "%w+", pos) if s then pos = e + 1 print("return the word") return string.sub(line, s, e) else print("read next line") line = io.read() pos = 1 end end print("return nil, iter end") return nil end end for word in allwords() do print(word) end ~~~ 执行结果如下: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-09-06_57ce5eefbe309.PNG) 注意执行打印出来的一些信息,可以帮助了解脚本的执行过程。 ## 2. Generic***for ***的语义 前面的例子有一个缺陷,每次都需要创建一个新的闭包来初始化一个新的循环。大多数情况下,这不是什么太大的开销。但是,有时也是不能接受的。这时就需要用generic***for ***本身来保存迭代器状态。 Generic***for ***会保存3个值:iterator function, invariant state,control variable。generic***for ***的语法如下: ~~~ for in do end ~~~ 这里,var-list是一个或多个变量的名字,用逗号分隔,exp-list是一个或多个表达式,也用逗号分隔。通常exp-list只有一个元素,对iterator factory的调用。例如: ~~~ for k, v in pairs(t) do print(k, v) end ~~~ var-list是k,v, exp-list是pairs(t)。通常,var-list也只有一个变量,如下: ~~~ for line in io.lines() do io.write(line, "\n") end ~~~ var-list的第一个变量为control variable,它的值为nil时表示循环结束。 ***for ***循环先计算in后面的表达式的值,这些表达式会产生3个值,就是上面写的generic***for* **需要保存的3个值:iterator function, invariant state,control variable 的初始值。跟多赋值语句一样,只有最后一个表达式可以产生多个值;但是所有的表达式的结果最终被调整为3个,多的丢弃,少的补nil (当使用简单的迭代器的时候,factory只返回iterator function,invariant state和control variable的值为nil)。 完成上面的初始化步骤后,***for***用invariant state和control variable作为参数来调用iterator function。然后***for***将iterator function返回的值赋值给var-list中的变量,如果返回的第一个值为nil,那么循环结束。否则,***for***执行循环体代码并再次调用iteration function,重复上面的过程。 下面的伪代码也许能帮助理解: ~~~ for var_1, ..., var_n in do end ~~~ 等价于: ~~~ do local _f, _s, _var = while true do local var_1, ... , var_n = _f(_s, _var) _var = var_1 if _var == nil then break end end end ~~~ 如果iterator function为*f* ,invariant state为*s* , control variable的初始值为*a0*,control variable会如下循环: *a1* =*f* (*s *,*a0 *),*a2* =**f (*s *,*a1 *), *a3* =*f* (*s *,*a2 *), .... 直到ai为nil。 ## 3. 无状态迭代器 顾名思义,无状态迭代器自身不会保存任何state。因此,我们可以在多次循环里面用同一个迭代器,避免了创建新闭包的开销。 每次迭代,for 循环用两个参数 invariant state 和 control variable 来调用 iterator 函数。ipairs 是个典型的此类迭代器: ~~~ a = {"one", "two", "three"} for i, v in ipairs(a) do print(i, v) end ~~~ 迭代器的state 是被遍历的table ,当前的index 是 control variable 。ipairs 和 iterator 实现都比较简单,下面是一个示例: ~~~ local function iter (a, i) i = i + 1 local v = a[i] if v then return i, v end end function ipairs (a) return iter, a, 0 end ~~~ 在for 循环中,Lua调用 ipairs(a) ,得到3个值: iter 函数为iterator , a 为invariant state , 0 是control variable 的初始值。 然后,Lua调用 iter(a,0), 得到1, a[1] 。下一次迭代,调用 iter(a,1), 得到 2, a[2],直到第一个nil值,迭代结束。 pairs 函数跟上面的 ipairs 类似,只是iterator 函数为 next, 不是iter。next 是Lua中的一个基本函数: ~~~ function pairs (t) return next, t, nil end ~~~ next(t, k) 调用,k 是 table t 中的一个key ,返回两个值,next key 和 t[next key],next(t, nil)返回 table 中的第一对值。例如: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-09-06_57ce5eefd7e58.PNG) 很多人比较喜欢直接用next ,而不是用pairs: ~~~ for k, v in next, t do end ~~~ for 循环的exp-list会被调整为3个值,Lua会得到next,t,nil,跟调用pairs(t)得到的结果是一样的。 下面是一个遍历链表的例子,代码有点绕,仔细想一下就会明白的。 ~~~ local function getnext (list, node) return not node and list or node.next end function traverse (list) return getnext, list, nil end list = nil for line in io.lines() do list = {val = line, next = list} end for node in traverse(list) do print(node.val) end ~~~ ## 4. 复合状态的迭代器 很多时候,需要保存的state,除了 invariant state 和 control variable 还有别的。这种情况,用闭包是最简单的方案。还有一个可选方案,用table,把所有需要保存的东西都打包到table 中,想保存什么就把什么打包到table 中。在循环过程中,尽管state 始终是同一个table,但是table中的数据可以在循环过程中更改。迭代器把所有需要的数据到封装到table 中,所有就忽略了generic *for* 提供的第二个参数。 下面把allwords那个示例改写了一下,来展示一下上面所说的用法 ~~~ local iterator function allwords() local state = {line = io.read(), pos = 1} return iterator, state end function iterator(state) while state.line do --search for next word local s, e = string.find(state.line, "%w+", state.pos) if s then -- update next position (after this word) state.pos = e + 1 return string.sub(state.line, s, e) else state.line = io.read() state.pos = 1 end end return nil end for word in allwords() do print(word) end ~~~ 运行结果示例如下: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-09-06_57ce5ef000aa3.PNG) 我们应该尽可能的使用无状态的迭代器,将所有的state都保存到*for* 循环的变量中。在开始新的循环的时候就不需要创建新的对象。当你的迭代器不适合上面说的table的情况时,应该用闭包。用闭包更简洁优美,并且效率更高,因为:1. 创建闭包比创建table开销要小。 2. 访问非局部变量(闭包中)比访问table的域要更快。 后面还会讲讲用*coroutines* 来实现迭代器,更强大,但是代价也更高。 ## 5. 真正的迭代器 “迭代器”这个名字其实有点误导,因为我们的“迭代器”根本不做迭代操作,真正去做迭代操作的是 for 循环。“迭代器”只是为迭代过程提供连续的值。可能更好的名字应该叫“生成器”。 不过,下面展示一种真正去做迭代操作的“迭代器”,再把allwords 重写一次: ~~~ function allwords(f) for line in io.lines() do for word in string.gmatch(line, "%w+") do f(word) -- call the function end end end allwords(print) print("=============================") local count = 0 allwords(function(w) if w == "hello" then count = count + 1 end end) print("the number of 'hello' is " .. count) ~~~ 示例中 的参数f 可以传相关的函数,示例中简单的用了*print* 来显示了一下句子中的word,用了一个匿名函数统计句子中的“hello”个数。 执行结果如下: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-09-06_57ce5ef0185b0.PNG) 这种形式的迭代器在旧版本的Lua中很流行,那是Lua没有*for* 语句。跟“生成器”形式的迭代器比起来,到底哪一种好呢?两种开销差不多,每次迭代都是一次函数调用。从一方面讲,这种旧式迭代器,更容易写。但是“生成器”形式的迭代器更灵活。首先,她可以同时进行两个平行的迭代(例如,比较两个句子中的word,一个一个的比),另外,可以用*break* 在迭代过程中退出。总的来说,“生成器”形式的迭代器也许更受欢迎一点。 水平有限,如果有朋友发现错误,欢迎留言交流。
';