|
table是Lua中唯一的數(shù)據(jù)結(jié)構(gòu)，其他語(yǔ)言所提供的數(shù)據(jù)結(jié)構(gòu)，如：arrays、records、lists、queues、sets等，Lua都是通過(guò)table來(lái)實(shí)現(xiàn)，并且在lua中table很好的實(shí)現(xiàn)了這些數(shù)據(jù)結(jié)構(gòu)。 在傳統(tǒng)的C語(yǔ)言或者Pascal語(yǔ)言中我們經(jīng)常使用arrays和lists（record+pointer）來(lái)實(shí)現(xiàn)大部分的數(shù)據(jù)結(jié)構(gòu)，在Lua中不僅可以用table完成同樣的功能，而且table的功能更加強(qiáng)大。通過(guò)使用table很多算法的實(shí)現(xiàn)都簡(jiǎn)化了，比如你在lua中很少需要自己去實(shí)現(xiàn)一個(gè)搜索算法，因?yàn)閠able本身就提供了這樣的功能。 我們需要花一些時(shí)間去學(xué)習(xí)如何有效的使用table，下面通過(guò)一些例子，我們來(lái)看看如果通過(guò) table來(lái)實(shí)現(xiàn)一些常用的數(shù)據(jù)結(jié)構(gòu)。首先，我們從arrays和lists開始，因?yàn)閮烧呤瞧渌麛?shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，大家也比較熟悉。前面章節(jié)，我們已接觸了table的一些內(nèi)容，本章，我們將徹底了解它。 11.1 數(shù)組 在lua中通過(guò)整數(shù)下標(biāo)訪問(wèn)table中元素，即是數(shù)組。并且數(shù)組大小不固定，可動(dòng)態(tài)增長(zhǎng)。 通常我們初始化數(shù)組時(shí)，就間接地定義了數(shù)組的大小，例如： a = {} -- new array for i=1, 1000 do a = 0 end 數(shù)組a的大小為1000，訪問(wèn)1-1000范圍外的值，將返回nil。數(shù)組下標(biāo)可以根據(jù)需要，從任意值開始，比如： -- creates an array with indices from -5 to 5 a = {} for i=-5, 5 do a = 0 end 然而習(xí)慣上，Lua的下標(biāo)從1開始。Lua的標(biāo)準(zhǔn)庫(kù)遵循此慣例，因此你的數(shù)組下標(biāo)必須也是從1開始，才可以使用標(biāo)準(zhǔn)庫(kù)的函數(shù)。 我們可以用構(gòu)造器在創(chuàng)建數(shù)組的同時(shí)初始化數(shù)組： squares = {1, 4, 9, 16, 25, 36, 49, 64, 81} 這樣的語(yǔ)句中，數(shù)組的大小可以任意的大。 11.2 矩陣和多維數(shù)組 Lua中有兩種表示矩陣的方法，一是“數(shù)組的數(shù)組”。也就是說(shuō)，table的每個(gè)元素是另一個(gè)table。例如，可以使用下面代碼創(chuàng)建一個(gè)n行m列的矩陣： mt = {} -- create the matrix for i=1,N do mt = {} -- create a new row for j=1,M do mt[j] = 0 end end 由于Lua中table是對(duì)象，所以每一行我們必須顯式地創(chuàng)建一個(gè)table，比起c或pascal，這顯得冗余，但另一方面也提供了更多的靈活性，例如可修改前面的例子創(chuàng)建一個(gè)三角矩陣： for j=1,M do 改成 for j=1,i do 這樣實(shí)現(xiàn)的三角矩陣比起整個(gè)矩陣，僅使用一半的內(nèi)存空間。 表示矩陣的另一方法，是將行和列組合起來(lái)。如果索引下標(biāo)都是整數(shù)，通過(guò)第一個(gè)索引乘于一個(gè)常量（列）再加上第二個(gè)索引，看下面的例子實(shí)現(xiàn)創(chuàng)建n行m列的矩陣： mt = {} -- create the matrix for i=1,N do for j=1,M do mt[i*M + j] = 0 end end 如果索引是字符串，可用一個(gè)單字符將兩個(gè)字符串索引連接起來(lái)構(gòu)成一個(gè)單一的索引下標(biāo)，例如一個(gè)矩陣m，索引下標(biāo)為s和t，假定s和t都不包含冒號(hào)，代碼為：m[s..':'..t]，如果s或者t包含冒號(hào)將導(dǎo)致混淆，比如("a:", "b") 和("a", ":b")，當(dāng)對(duì)這種情況有疑問(wèn)的時(shí)候可以使用控制字符來(lái)連接兩個(gè)索引字符串，比如'\0'。 實(shí)際應(yīng)用中常常使用稀疏矩陣，稀疏矩陣指矩陣的大部分元素都為空或者0的矩陣。例如，我們通過(guò)圖的鄰接矩陣來(lái)存儲(chǔ)圖，也就是說(shuō)：當(dāng)m,n兩個(gè)節(jié)點(diǎn)有連接時(shí)，矩陣的m,n值為對(duì)應(yīng)的x，否則為nil。如果一個(gè)圖有10000個(gè)節(jié)點(diǎn)，平均每個(gè)節(jié)點(diǎn)大約有5條邊，為了存儲(chǔ)這個(gè)圖需要一個(gè)行列分別為10000的矩陣，總計(jì)10000*10000個(gè)元素，實(shí)際上大約只有50000個(gè)元素非空（每行有五列非空，與每個(gè)節(jié)點(diǎn)有五條邊對(duì)應(yīng)）。很多數(shù)據(jù)結(jié)構(gòu)的書上討論采用何種方式才能節(jié)省空間，但是在Lua中你不需要這些技術(shù)，因?yàn)橛胻able實(shí)現(xiàn)的數(shù)據(jù)本身天生的就具有稀疏的特性。如果用我們上面說(shuō)的第一種多維數(shù)組來(lái)表示，需要10000個(gè)table，每個(gè)table大約需要五個(gè)元素（table）；如果用第二種表示方法來(lái)表示，只需要一張大約50000個(gè)元素的表，不管用那種方式，你只需要存儲(chǔ)那些非nil的元素。 11.3 鏈表 Lua中用tables很容易實(shí)現(xiàn)鏈表，每一個(gè)節(jié)點(diǎn)是一個(gè)table，指針是這個(gè)表的一個(gè)域（field），并且指向另一個(gè)節(jié)點(diǎn)（table）。例如，要實(shí)現(xiàn)一個(gè)只有兩個(gè)域：值和指針的基本鏈表，代碼如下： 根節(jié)點(diǎn)： list = nil 在鏈表開頭插入一個(gè)值為v的節(jié)點(diǎn)： list = {next = list, value = v} 要遍歷這個(gè)鏈表只需要： local l = list while l do print(l.value) l = l.next end 其他類型的鏈表，像雙向鏈表和循環(huán)鏈表類似的也是很容易實(shí)現(xiàn)的。然后在Lua中在很少情況下才需要這些數(shù)據(jù)結(jié)構(gòu)，因?yàn)橥ǔＧ闆r下有更簡(jiǎn)單的方式來(lái)替換鏈表。比如，我們可以用一個(gè)非常大的數(shù)組來(lái)表示棧，其中一個(gè)域n指向棧頂。 11.4 隊(duì)列和雙向隊(duì)列 雖然可以使用Lua的table庫(kù)提供的insert和remove操作來(lái)實(shí)現(xiàn)隊(duì)列，但這種方式實(shí)現(xiàn)的隊(duì)列針對(duì)大數(shù)據(jù)量時(shí)效率太低，有效的方式是使用兩個(gè)索引下標(biāo)，一個(gè)表示第一個(gè)元素，另一個(gè)表示最后一個(gè)元素。 function ListNew () return {first = 0, last = -1} end 為了避免污染全局命名空間，我們重寫上面的代碼，將其放在一個(gè)名為list的table中： List = {} function List.new () return {first = 0, last = -1} end 下面，我們可以在常量時(shí)間內(nèi)，完成在隊(duì)列的兩端進(jìn)行插入和刪除操作了。 function List.pushleft (list, value) local first = list.first - 1 list.first = first list[first] = value end function List.pushright (list, value) local last = list.last + 1 list.last = last list[last] = value end function List.popleft (list) local first = list.first if first > list.last then error("list is empty") end local value = list[first] list[first] = nil -- to allow garbage collection list.first = first + 1 return value end function List.popright (list) local last = list.last if list.first > last then error("list is empty") end local value = list[last] list[last] = nil -- to allow garbage collection list.last = last - 1 return value end 對(duì)嚴(yán)格意義上的隊(duì)列來(lái)講，我們只能調(diào)用pushright和popleft，這樣以來(lái)，first和last的索引值都隨之增加，幸運(yùn)的是我們使用的是 Lua的table實(shí)現(xiàn)的，你可以訪問(wèn)數(shù)組的元素，通過(guò)使用下標(biāo)從1到20，也可以16,777,216 到 16,777,236。另外，Lua使用雙精度表示數(shù)字，假定你每秒鐘執(zhí)行100萬(wàn)次插入操作，在數(shù)值溢出以前你的程序可以運(yùn)行200年。 11.5 集合和包 假定你想列出在一段源代碼中出現(xiàn)的所有標(biāo)示符，某種程度上，你需要過(guò)濾掉那些語(yǔ)言本身的保留字。一些C程序員喜歡用一個(gè)字符串?dāng)?shù)組來(lái)表示，將所有的保留字放在數(shù)組中，對(duì)每一個(gè)標(biāo)示符到這個(gè)數(shù)組中查找看是否為保留字，有時(shí)候?yàn)榱颂岣卟樵冃?，?duì)數(shù)組存儲(chǔ)的時(shí)候使用二分查找或者h(yuǎn)ash算法。 Lua中表示這個(gè)集合有一個(gè)簡(jiǎn)單有效的方法，將所有集合中的元素作為下標(biāo)存放在一個(gè)table里，下面不需要查找table，只需要測(cè)試看對(duì)于給定的元素，表的對(duì)應(yīng)下標(biāo)的元素值是否為nil。比如： reserved = { ["while"] = true, ["end"] = true, ["function"] = true, ["local"] = true, } for w in allwords() do if reserved[w] then -- `w' is a reserved word ... 還可以使用輔助函數(shù)更加清晰的構(gòu)造集合： function Set (list) local set = {} for _, l in ipairs(list) do set[l] = true end return set end reserved = Set{"while", "end", "function", "local", } 11.6 字符串緩沖 假定你要拼接很多個(gè)小的字符串為一個(gè)大的字符串，比如，從一個(gè)文件中逐行讀入字符串。你可能寫出下面這樣的代碼： -- WARNING: bad code ahead!! local buff = "" for line in io.lines() do buff = buff .. line .. "\n" end 盡管這段代碼看上去很正常，但在Lua中他的效率極低，在處理大文件的時(shí)候，你會(huì)明顯看到很慢，例如，需要花大概1分鐘讀取350KB的文件。（這就是為什么Lua專門提供了io.read(*all)選項(xiàng)，她讀取同樣的文件只需要0.02s） 為什么這樣呢？Lua使用真正的垃圾收集算法，但他發(fā)現(xiàn)程序使用太多的內(nèi)存他就會(huì)遍歷他所有的數(shù)據(jù)結(jié)構(gòu)去釋放垃圾數(shù)據(jù)，一般情況下，這個(gè)算法有很好的性能（Lua的快并非偶然的），但是上面那段代碼loop使得算法的效率極其低下。 為了理解現(xiàn)象的本質(zhì)，假定我們身在loop中間，buff已經(jīng)是一個(gè)50KB的字符串，每一行的大小為20bytes，當(dāng)Lua執(zhí)行 buff..line.."\n"時(shí)，她創(chuàng)建了一個(gè)新的字符串大小為50,020 bytes，并且從buff中將50KB的字符串拷貝到新串中。也就是說(shuō)，對(duì)于每一行，都要移動(dòng)50KB的內(nèi)存，并且越來(lái)越多。讀取100行的時(shí)候（僅僅 2KB），Lua已經(jīng)移動(dòng)了5MB的內(nèi)存，使情況變?cè)獾氖窍旅娴馁x值語(yǔ)句： buff = buff .. line .. "\n" 老的字符串變成了垃圾數(shù)據(jù)，兩輪循環(huán)之后，將有兩個(gè)老串包含超過(guò)100KB的垃圾數(shù)據(jù)。這個(gè)時(shí)候Lua會(huì)做出正確的決定，進(jìn)行他的垃圾收集并釋放100KB的內(nèi)存。問(wèn)題在于每?jī)纱窝h(huán)Lua就要進(jìn)行一次垃圾收集，讀取整個(gè)文件需要進(jìn)行200次垃圾收集。并且它的內(nèi)存使用是整個(gè)文件大小的三倍。 這個(gè)問(wèn)題并不是Lua特有的：其它的采用垃圾收集算法的并且字符串不可變的語(yǔ)言也都存在這個(gè)問(wèn)題。Java是最著名的例子，Java專門提供StringBuffer來(lái)改善這種情況。 在繼續(xù)進(jìn)行之前，我們應(yīng)該做個(gè)注釋的是，在一般情況下，這個(gè)問(wèn)題并不存在。對(duì)于小字符串，上面的那個(gè)循環(huán)沒有任何問(wèn)題。為了讀取整個(gè)文件我們可以使用 io.read(*all)，可以很快的將這個(gè)文件讀入內(nèi)存。但是在某些時(shí)候，沒有解決問(wèn)題的簡(jiǎn)單的辦法，所以下面我們將介紹更加高效的算法來(lái)解決這個(gè)問(wèn)題。 我們最初的算法通過(guò)將循環(huán)每一行的字符串連接到老串上來(lái)解決問(wèn)題，新的算法避免如此：它連接兩個(gè)小串成為一個(gè)稍微大的串，然后連接稍微大的串成更大的串。。。算法的核心是：用一個(gè)棧，在棧的底部用來(lái)保存已經(jīng)生成的大的字符串，而小的串從棧定入棧。棧的狀態(tài)變化和經(jīng)典的漢諾塔問(wèn)題類似：位于棧下面的串肯定比上面的長(zhǎng)，只要一個(gè)較長(zhǎng)的串入棧后比它下面的串長(zhǎng)，就將兩個(gè)串合并成一個(gè)新的更大的串，新生成的串繼續(xù)與相鄰的串比較如果長(zhǎng)于底部的將繼續(xù)進(jìn)行合并，循環(huán)進(jìn)行到?jīng)]有串可以合并或者到達(dá)棧底。 function newStack () return {""} -- starts with an empty string end function addString (stack, s) table.insert(stack, s) -- push 's' into the the stack for i=table.getn(stack)-1, 1, -1 do if string.len(stack) > string.len(stack[i+1]) then break end stack = stack .. table.remove(stack) end end 要想獲取最終的字符串，我們只需要從上向下一次合并所有的字符串即可。table.concat函數(shù)可以將一個(gè)列表的所有串合并。 使用這個(gè)新的數(shù)據(jù)結(jié)構(gòu)，我們重寫我們的代碼： local s = newStack() for line in io.lines() do addString(s, line .. "\n") end s = toString(s) 最終的程序讀取350KB的文件只需要0.5s，當(dāng)然調(diào)用io.read("*all")仍然是最快的只需要0.02s。 實(shí)際上，我們調(diào)用io.read("*all")的時(shí)候，io.read就是使用我們上面的數(shù)據(jù)結(jié)構(gòu)，只不過(guò)是用C實(shí)現(xiàn)的，在Lua標(biāo)準(zhǔn)庫(kù)中，有些其他函數(shù)也是用C實(shí)現(xiàn)的，比如table.concat，使用table.concat我們可以很容易的將一個(gè)table的中的字符串連接起來(lái)，因?yàn)樗褂肅實(shí)現(xiàn)的，所以即使字符串很大它處理起來(lái)速度還是很快的。 Concat接受第二個(gè)可選的參數(shù)，代表插入的字符串之間的分隔符。通過(guò)使用這個(gè)參數(shù)，我們不需要在每一行之后插入一個(gè)新行： local t = {} for line in io.lines() do table.insert(t, line) end s = table.concat(t, "\n") .. "\n" io.lines迭代子返回不帶換行符的一行，concat在字符串之間插入分隔符，但是最后一字符串之后不會(huì)插入分隔符，因此我們需要在最后加上一個(gè)分隔符。最后一個(gè)連接操作復(fù)制了整個(gè)字符串，這個(gè)時(shí)候整個(gè)字符串可能是很大的。我們可以使用一點(diǎn)小技巧，插入一個(gè)空串： table.insert(t, "") s = table.concat(t, "\n") |
|
|
