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