7.Iterators and the Generic for
在這一章我們討論為范性for寫迭代器,?我們從一個簡單的迭代器開始,然后我們學(xué)習(xí)如何通過利用范性for的強大之處寫出更高效的迭代器.
7.1?迭代器與閉包
?迭代器是一種支持指針類型的結(jié)構(gòu),它可以使遍歷集合的每一個元素.在Lua中我們常常使用函數(shù)來描述迭代器,每次調(diào)用該函數(shù)就返回集合的下一個元素.
?
迭代器需要保留上一次成功調(diào)用的狀態(tài)和下一次成功調(diào)用的狀態(tài),也就是他知道來自于哪里和將要前往哪里.閉包提供的機制可以很容易實現(xiàn)這個任務(wù).記住:閉包
是一個內(nèi)部函數(shù),它可以訪問一個或者多個外部函數(shù)的外部局部變量.每次閉包的成功調(diào)用后這些外部局部變量都保存他們的值(狀態(tài)).當(dāng)然如果要創(chuàng)建一個閉包
必須要創(chuàng)建其外部局部變量.所以一個典型的閉包的結(jié)構(gòu)包含兩個函數(shù):一個是閉包自己;另一個是工廠(創(chuàng)建閉包的函數(shù)).
?舉一個簡單的例子,我們?yōu)橐粋€list寫一個簡單的迭代器,與ipairs()不同的是我們實現(xiàn)的這個迭代器返回元素的值而不是索引下標(biāo):
??function list_iter (t)
??? ?? local i = 0
??? ?? local n = table.getn(t)
??? ?? return function ()
??? ??????????? i = i + 1
??? ??????????? if i <= n then return t[i] end
??? ????????? end
??? ?end
?這個例子中l(wèi)ist_iter 是一個工廠,每次調(diào)用他都會創(chuàng)建一個新的閉包(迭代器本身).閉包包村內(nèi)部局部變量(t,i,n),因此每次調(diào)用他返回list中的下一個元素值,當(dāng)list中沒有值時,返回nil.我們可以在while語句中使用這個迭代器:
??t = {10, 20, 30}
??? ?iter = list_iter(t)??? -- creates the iterator
??? ?while true do
??? ?? local element = iter()?? -- calls the iterator
??? ?? if element == nil then break end
??? ?? print(element)
??? ?end
?我們設(shè)計的這個迭代器也很容易用于范性for語句
??t = {10, 20, 30}
??? ?for element in list_iter(t) do
??? ?? print(element)
??? ?end
?范性for為迭代循環(huán)處理所有的薄記(bookkeeping):首先調(diào)用迭代工廠;內(nèi)部保留迭代函數(shù),因此我們不需要iter變量;然后在每一個新的迭代處調(diào)用迭代器函數(shù);當(dāng)?shù)鞣祷豱il時循環(huán)結(jié)束(后面我們將看到范性for能勝任更多的任務(wù)).
?下面看一個稍微高級一點的例子:我們寫一個迭代器遍歷一個文件內(nèi)的所有匹配的單詞.為了實現(xiàn)目的,我們需要保留兩個值:當(dāng)前行和在當(dāng)前行的偏移量,我們使用兩個外部局部變量line,pos保存這兩個值.
??function allwords ()
??? ?? local line = io.read()? -- current line
??? ?? local pos = 1?????????? -- current position in the line
??? ?? return function ()????? -- iterator function
??? ???? while line do???????? -- repeat while there are lines
??? ?????? local s, e = string.find(line, "%w+", pos)
??? ?????? if s then?????????? -- found a word?
??? ???????? pos = e + 1?????? -- next position is after this word
??? ???????? return string.sub(line, s, e)???? -- return the word
??? ?????? else
??? ???????? line = io.read()? -- word not found; try next line
??? ???????? pos = 1?????????? -- restart from first position
??? ?????? end
??? ???? end
??? ???? return nil??????????? -- no more lines: end of traversal
??? ?? end
??? ?end
?
迭代函數(shù)的主體部分調(diào)用了string.find函數(shù),string.find在當(dāng)前行從當(dāng)前位置開始查找匹配的單詞,例子中匹配的單詞使用模式'%w+
'描述的;如果查找到一個單詞,迭代函數(shù)更新當(dāng)前位置pos為單詞后的第一個位置,并且返回這個單詞(string.sub函數(shù)從line中提取兩個位置
參數(shù)之間的子串).否則迭代函數(shù)讀取新的一行并重新搜索.如果沒有l(wèi)ine可讀返回nil結(jié)束.
?盡管迭代函數(shù)有些復(fù)雜,但使用起來是很直觀的:?
??for word in allwords() do
????? ??print(word)
??? ?end
??? 通常情況下,迭代函數(shù)都難寫易用.這不是一個大問題:一般Lua編程不需要自己定義迭代函數(shù),而是使用語言提供的,除非確實需要自己定義.
7.2?范性for的語義?
?
前面我們看到的迭代器有一個缺點:每次調(diào)用都需要創(chuàng)建一個閉包,大多數(shù)情況下這種做法都沒什么問題,例如在allwords迭代器中創(chuàng)建一個閉包的代價比
起讀整個文件來說微不足道,然后在有些情況下創(chuàng)建閉包的代價是不能忍受的.在這些情況下我們可以使用范性for本身來保存迭代的狀態(tài).
?前面我們看到在循環(huán)過程中范性for在自己內(nèi)部保存迭代函數(shù),實際上它保存三個值:迭代函數(shù),狀態(tài)常量和控制變量.下面詳細說明.
?范性for的文法如下:
??for <var-list> in <exp-list> do
??? ?? <body>
??? ?end
?<var-list>是一個或多個以逗號分割變量名的列表,<exp-list>是一個或多個以逗號分割的表達式列表,通常情況下exp-list只有一個值:迭代工廠的調(diào)用.
??for k, v in pairs(t) do
?????? print(k, v)?????
??????? end???????
??? 變量列表k,v;表達式列表pair(t),在很多情況下變量列表也只有一個變量,比如:
??? ?for line in io.lines() do????????
??????? ?io.write(line, '\n')
??????? end??????????????
??? 我們稱變量列表中第一個變量為控制變量,其值為nil時循環(huán)結(jié)束.
??? 下面我們看看范性for的執(zhí)行過程:
??? 首先,初始化,計算in后面表達式的值,表達式應(yīng)該返回范性for需要的三個值:迭代函數(shù),狀態(tài)常量和控制變量;與多值賦值一樣,如果表達式返回的結(jié)果個數(shù)不足三個會自動用nil補足，多出部分會被忽略.
??? 第二,將狀態(tài)常量和控制變量作為參數(shù)調(diào)用迭代函數(shù)(注意:對于for結(jié)構(gòu)來說,狀態(tài)常量沒有用處,僅僅在初始化時獲取他的值并傳遞給迭代函數(shù)).
??? 第三,將迭代函數(shù)返回的值賦給變量列表.
??? 第四,如果返回的第一個值為nil循環(huán)結(jié)束,否則執(zhí)行循環(huán)體.
??? 第五,回到第二步再次調(diào)用迭代函數(shù).
??? 更精確的來說:
??? ?for var_1, ..., var_n in explist do block end
?等價于
??do
??? ?? local _f, _s, _var = explist
??? ?? while true do
??? ???? local var_1, ... , var_n = _f(_s, _var)
??? ???? _var = var_1
??? ???? if _var == nil then break end
??? ???? block
??? ?? end
??? ?end
?如果我們的迭代函數(shù)是f，狀態(tài)常量是s,控制變量的初始值是a0,那么控制變量將循環(huán):a1=f(s,a0);a2=f(s,a1);...直到ai=nil
7.3?無狀態(tài)的迭代器
? ?無狀態(tài)的迭代器是指不保留任何狀態(tài)的迭代器,因此在循環(huán)中我們可以利用無狀態(tài)迭代器避免創(chuàng)建閉包花費額外的代價.
? ?每一次迭代,迭代函數(shù)都是用兩個變量(狀態(tài)常量和控制變量)的值作為參數(shù)被調(diào)用,一個無狀態(tài)的迭代器只利用這兩個值可以獲取下一個元素.這種無狀態(tài)迭代器的典型的簡單的例子是ipairs,他遍歷數(shù)組的每一個元素.
? ??a = {"one", "two", "three"}
??? ?for i, v in ipairs(a) do
??? ?? print(i, v)
??? ?end
?迭代的狀態(tài)包括被遍歷的表(循環(huán)過程中不會改變的狀態(tài)常量)和當(dāng)前的索引下標(biāo)(控制變量),ipairs和迭代函數(shù)都很簡單,我們在Lua中可以這樣實現(xiàn):
??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
?
當(dāng)Lua調(diào)用ipairs(a)開始循環(huán)時,他獲取三個值:迭代函數(shù)iter,狀態(tài)常量a和控制變量初始值0;然后Lua調(diào)用iter(a,0)返回1,
a[1](除非a[1]=nil);第二次迭代調(diào)用iter(a,1)返回2,a[2]...直到第一個非nil元素.
?Lua庫中實現(xiàn)的pairs是一個用next實現(xiàn)的原始方法:
??function pairs (t)
??? ?? return next, t, nil
??? ?end
?還可以不使用ipairs直接使用next
??for k, v in next, t do
??? ?? ...
??? ?end
?記住:exp-list返回結(jié)果會被調(diào)整為三個,所以Lua獲取next,t,nil;確切地說當(dāng)他調(diào)用pairs時獲取.
7.4?多狀態(tài)的迭代器
?
很多情況下,迭代器需要保存多個狀態(tài)信息而不是簡單的狀態(tài)常量和控制變量,最簡單的方法是使用閉包,還有一種方法就是將所有的狀態(tài)信息封裝到table
內(nèi),將table作為迭代器的狀態(tài)常量,因為這種情況下可以將所有的信息存放在table內(nèi),所以迭代函數(shù)通常不需要第二個參數(shù).
?下面我們重寫allwords迭代器,這一次我們不是使用閉包而是使用帶有兩個域(line,pos)的table.
?開始迭代的函數(shù)是很簡單的,他必須返回迭代函數(shù)和初始狀態(tài):
??local iterator?? -- to be defined later
??? ?
??? ?function allwords ()
??? ?? local state = {line = io.read(), pos = 1}
??? ?? return iterator, state
??? ?end
?真正的處理工作是在迭代函數(shù)內(nèi)完成:
??function iterator (state)
??? ?? while state.line do??????? -- repeat while there are lines
??? ???? -- search for next word
??? ???? local s, e = string.find(state.line, "%w+", state.pos)
??? ???? if s then??????????????? -- found a word?
??? ?????? -- update next position (after this word)
??? ?????? state.pos = e + 1
??? ?????? return string.sub(state.line, s, e)
??? ???? else??? -- word not found
??? ?????? state.line = io.read() -- try next line...
??? ?????? state.pos = 1????????? -- ... from first position
??? ???? end
??? ?? end
??? ?? return nil???????????????? -- no more lines: end loop
??? ?end
?
我們應(yīng)該盡可能的寫無狀態(tài)的迭代器,因為這樣循環(huán)的時候由for來保存狀態(tài),不需要創(chuàng)建對象花費的代價小;如果不能用無狀態(tài)的迭代器實現(xiàn),應(yīng)盡可能使用閉
包;盡可能不要使用table這種方式,因為創(chuàng)建閉包的代價要比創(chuàng)建table小,另外Lua處理閉包要比處理table速度快些.后面我們還將看到另一
種使用協(xié)同來創(chuàng)建迭代器的方式,這種方式功能更強但更復(fù)雜.
7.4?真正的迭代器
?迭代器的名字有一些誤導(dǎo),因為它并沒有迭代,完成迭代功能的是for語句,也許更好的叫法應(yīng)該是'生成器';但是在其他語言比如java,C++迭代器的說法已經(jīng)很普遍了,我們也將沿用這種術(shù)語.
?有一種方式創(chuàng)建一個在內(nèi)部完成迭代的迭代器.這樣當(dāng)我們使用迭代器的時候就不需要使用循環(huán)了;我們僅僅使用每一次迭代需要處理的任務(wù)作為參數(shù)調(diào)用迭代器即可,具體地說,迭代器接受一個函數(shù)作為參數(shù),并且這個函數(shù)在迭代器內(nèi)部被調(diào)用.
?作為一個具體的例子,我們使用上述方式重寫allwords迭代器:
??function allwords (f)
??? ?? -- repeat for each line in the file
??? ?? for l in io.lines() do
??? ???? -- repeat for each word in the line
??? ???? for w in string.gfind(l, "%w+") do
??? ?????? -- call the function
??? ?????? f(w)
??? ???? end
??? ?? end
??? ?end
?如果我們想要打印出單詞,只需要
??allwords(print)
?更一般的做法是我們使用匿名函數(shù)作為作為參數(shù),下面的例子打印出單詞'hello'出現(xiàn)的次數(shù):
??local count = 0
??? ?allwords(function (w)
??? ?? if w == "hello" then count = count + 1 end
??? ?end)
??? ?print(count)
?用for結(jié)構(gòu)完成同樣的任務(wù):
??local count = 0
??? ?for w in allwords() do
??? ?? if w == "hello" then count = count + 1 end
??? ?end
??? ?print(count)
?真正的迭代器風(fēng)格的寫法在Lua老版本中很流行,那時還沒有for循環(huán).
?兩種風(fēng)格的寫法相差不大,但也有區(qū)別:一方面,第二種風(fēng)格更容易書寫和理解;另一方面,for結(jié)構(gòu)更靈活,可以使用break和continue語句 ;在真正的迭代器風(fēng)格寫法中return語句只是從匿名函數(shù)中返回而不是退出循環(huán).