Lua性能優(yōu)化技巧（三）：關(guān)于表
一般情況下，你不需要知道Lua實現(xiàn)表的細節(jié)，就可以使用它。實際上，Lua花了很多功夫來隱藏內(nèi)部的實現(xiàn)細節(jié)。但是，實現(xiàn)細節(jié)揭示了表操作的性能開銷情況。因此，要優(yōu)化使用表的程序（這里特指Lua程序），了解一些表的實現(xiàn)細節(jié)是很有好處的。
Lua的表的實現(xiàn)使用了一些很聰明的算法。每個Lua表的內(nèi)部包含兩個部分：數(shù)組部分和哈希部分。數(shù)組部分以從1到一個特定的n之間的整數(shù)作為鍵來保存元素（我們稍后即將討論這個n是如何計算出來的）。所有其他元素（包括在上述范圍之外的整數(shù)鍵）都被存放在哈希部分里。
正如其名，哈希部分使用哈希算法來保存和查找鍵。它使用被稱為開放地址表的實現(xiàn)方式，意思是說所有的元素都保存在哈希數(shù)組中。用一個哈希函數(shù)來獲取一個鍵對應(yīng)的索引；如果存在沖突的話（意即，如果兩個鍵產(chǎn)生了同一個哈希值），這些鍵將會被放入一個鏈表，其中每個元素對應(yīng)一個數(shù)組項。當(dāng)Lua需要向表中添加一個新的鍵，但哈希數(shù)組已滿時，Lua將會重新哈希。重新哈希的第一步是決定新的數(shù)組部分和哈希部分的大小。因此，Lua遍歷所有的元素，計數(shù)并對其進行歸類，然后為數(shù)組部分選擇一個大小，這個大小相當(dāng)于能使數(shù)組部分超過一半的空間都被填滿的2的最大的冪；然后為哈希部分選擇一個大小，相當(dāng)于正好能容納哈希部分所有元素的2的最小的冪。
當(dāng)Lua創(chuàng)建空表時，兩個部分的大小都是0。因此，沒有為其分配數(shù)組。讓我們看一看當(dāng)執(zhí)行下面的代碼時會發(fā)生什么：
local a = {}
for i = 1, 3 do
a[i] = true
end
這段代碼始于創(chuàng)建一個空表。在循環(huán)的第一次迭代中，賦值語句
a[1] = true
觸發(fā)了一次重新哈希；Lua將數(shù)組部分的大小設(shè)為1，哈希部分依然為空；第二次迭代時
a[2] = true
觸發(fā)了另一次重新哈希，將數(shù)組部分擴大為2.最終，第三次迭代又觸發(fā)了一次重新哈希，將數(shù)組部分的大小擴大為4。
類似下面的代碼
a = {}
a.x = 1; a.y = 2; a.z = 3
做的事情類似，只不過增加的是哈希部分的大小。
對于大的表來說，初期的幾次重新哈希的開銷被分攤到整個表的創(chuàng)建過程中，一個包含三個元素的表需要三次重新哈希，而一個有一百萬個元素的表也只需要二十次。但是當(dāng)創(chuàng)建幾千個小表的時候，重新哈希帶來的性能影響就會非常顯著。
舊版的Lua在創(chuàng)建空表時會預(yù)選分配大?。?，如果我沒有記錯的話），以防止在初始化小表時產(chǎn)生的這些開銷。但是這樣的實現(xiàn)方式會浪費內(nèi)存。例如，如果你要創(chuàng)建數(shù)百萬個點（表現(xiàn)為包含兩個元素的表），每個都使用了兩倍于實際所需的內(nèi)存，就會付出高昂的代價。這也是為什么Lua不再為新表預(yù)分配數(shù)組。
如果你使用C編程，可以通過Lua的API函數(shù)lua_createtable來避免重新哈希；除lua_State之外，它還接受兩個參數(shù)：數(shù)組部分的初始大小和哈希部分的初始大小[1]。只要指定適當(dāng)?shù)闹担涂梢员苊獬跏蓟瘯r的重新哈希。需要警惕的是，Lua只會在重新哈希時收縮表的大小，因此如果在初始化時指定了過大的值，Lua可能永遠不會糾正你浪費的內(nèi)存空間。
當(dāng)使用Lua編程時，你可能可以使用構(gòu)造式來避免初始化時的重新哈希。當(dāng)你寫下
{true, true, true}
時，Lua知道這個表的數(shù)組部分將會有三個元素，因此會創(chuàng)建相應(yīng)大小的數(shù)組。類似的，如果你寫下
{x = 1, y = 2, z = 3}
Lua也會為哈希部分創(chuàng)建一個大小為4的數(shù)組。例如，執(zhí)行下面的代碼需要2.0秒：
for i = 1, 1000000 do
local a = {}
a[1] = 1; a[2] = 2; a[3] = 3
end
如果在創(chuàng)建表時給定正確的大小，執(zhí)行時間可以縮減到0.7秒：
for i = 1, 1000000 do
local a = {true, true, true}
a[1] = 1; a[2] = 2; a[3] = 3
end
但是，如果你寫類似于
{[1] = true, [2] = true, [3] = true}
的代碼，Lua還不夠聰明，無法識別表達式（在本例中是數(shù)值字面量）指定的數(shù)組索引，因此它會為哈希部分創(chuàng)建一個大小為4的數(shù)組，浪費內(nèi)存和CPU時間。
兩個部分的大小只會在Lua重新哈希時重新計算，重新哈希則只會發(fā)生在表完全填滿后，Lua需要插入新的元素之時。因此，如果你遍歷一個表并清除其所有項（也就是全部設(shè)為nil），表的大小不會縮小。但是此時，如果你需要插入新的元素，表的大小將會被調(diào)整。多數(shù)情況下這都不會成為問題，但是，不要指望能通過清除表項來回收內(nèi)存：最好是直接把表自身清除掉。
一個可以強制重新哈希的猥瑣方法是向表中插入足夠多的nil。例如：
a = {}
lim = 10000000
for i = 1, lim do a[i] = i end -- 創(chuàng)建一個巨表
print(collectgarbage("count")) --> 196626
for i = 1, lim do a[i] = nil end -- 清除所有元素
print(collectgarbage("count")) --> 196626
for i = lim + 1, 2 * lim do a[i] = nil end -- 創(chuàng)建一堆nil元素
print(collectgarbage("count")) --> 17
除非是在特殊情況下，我不推薦使用這個伎倆：它很慢，并且沒有簡單的方法能知道要插入多少nil才夠。
你可能會好奇Lua為什么不會在清除表項時收縮表。首先是為了避免測試寫入表中的內(nèi)容。如果在賦值時檢查值是否為nil，將會拖慢所有的賦值操作。第二，也是最重要的，允許在遍歷表時將表項賦值為nil。例如下面的循環(huán)：
for k, v in pairs(t) do
if some_property(v) then
t[k] = nil – 清除元素
end
end
如果Lua在每次nil賦值后重新哈希這張表，循環(huán)就會被破壞。
如果你想要清除一個表中的所有元素，只需要簡單地遍歷它：
for k in pairs(t) do
t[k] = nil
end
一個“聰明”的替代解決方案：
while true do
local k = next(t)
if not k then break end
t[k] = nil
end
但是，對于大表來說，這個循環(huán)將會非常慢。調(diào)用函數(shù)next時，如果沒有給定前一個鍵，將會返回表的第一個元素（以某種隨機的順序）。在此例中，next將會遍歷這個表，從開始尋找一個非nil元素。由于循環(huán)總是將找到的第一個元素置為nil，因此next函數(shù)將會花費越來越長的時間來尋找第一個非nil元素。這樣的結(jié)果是，這個“聰明”的循環(huán)需要20秒來清除一個有100,000個元素的表，而使用pairs實現(xiàn)的循環(huán)則只需要0.04秒。
[1] 盡管重新哈希算法始終設(shè)置數(shù)組的大小為2的冪，數(shù)組的大小依然可以為任何自然數(shù)值。而哈希的大小必須為2的冪，所以第二個參數(shù)總是會被圓整為不小于原值的最小的2的冪。
相關(guān)文章
這篇文章主要介紹了Lua多行注釋和取消多行注釋的方法,本文分別給出代碼示例,請注意細節(jié)~,需要的朋友可以參考下2015-06-06
這篇文章主要介紹了Lua中訪問table里函數(shù)的方法示例,本文例子超級簡單,算是入門實例吧,其實只需要表名.方法名即可訪問,重要的還是其它代碼寫法,本文給出了一個完整的代碼示例,需要的朋友可以參考下2015-04-04
這篇文章主要介紹了Lua編程示例（五）： C語言對Lua表的讀取和添加,本文直接給出代碼實例,需要的朋友可以參考下2015-07-07
這篇文章主要為大家介紹了Golang使用ChatGPT生成單元測試實踐詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03
Lua中的閉合函數(shù)、非全局函數(shù)與函數(shù)的尾調(diào)用詳解
這篇文章主要介紹了Lua中的閉合函數(shù)、非全局函數(shù)與函數(shù)的尾調(diào)用詳解,本文對這2種函數(shù)和尾調(diào)用做了深入研究,需要的朋友可以參考下2014-09-09
今天小編就為大家分享一篇關(guān)于Lua一維數(shù)組與多維數(shù)組的使用示例，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要介紹了Lua判斷一個目錄或文件是否存在的方法,Lua中可以使用io.open判斷文件或目錄是否存在,本文總結(jié)了判斷方法,并給出了一個自定義函數(shù),需要的朋友可以參考下2015-04-04
這篇文章主要介紹了Lua中的源代碼預(yù)編譯淺析,Lua確實允許在運行源代碼之前,將源代碼預(yù)編譯成一種中間形式（類比Python的.pyc）,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了Lua極簡入門指南（一）：函數(shù)篇,本文講解了函數(shù)的定義、函數(shù)多值返回、變長參數(shù)、閉包（closures）等內(nèi)容,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了Lua中的協(xié)同程序詳解,本文非常詳細的講解了Lua中的協(xié)同程序,同時講解了生產(chǎn)者-消費者問題,需要的朋友可以參考下2014-09-09