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