脚本之家,脚本语言编程技术及教程分享平台!
分类导航

Python|VBS|Ruby|Lua|perl|VBA|Golang|PowerShell|Erlang|autoit|Dos|bat|

服务器之家 - 脚本之家 - Lua - Lua性能优化技巧(三):关于表

Lua性能优化技巧(三):关于表

2020-04-22 10:37脚本之家 Lua

这篇文章主要介绍了Lua性能优化技巧(三):关于表,本文讲解了一些关于表的优化技巧,需要的朋友可以参考下

一般情况下,你不需要知道Lua实现表的细节,就可以使用它。实际上,Lua花了很多功夫来隐藏内部的实现细节。但是,实现细节揭示了表操作的性能开销情况。因此,要优化使用表的程序(这里特指Lua程序),了解一些表的实现细节是很有好处的。

Lua的表的实现使用了一些很聪明的算法。每个Lua表的内部包含两个部分:数组部分和哈希部分。数组部分以从1到一个特定的n之间的整数作为键来保存元素(我们稍后即将讨论这个n是如何计算出来的)。所有其他元素(包括在上述范围之外的整数键)都被存放在哈希部分里。

正如其名,哈希部分使用哈希算法来保存和查找键。它使用被称为开放地址表的实现方式,意思是说所有的元素都保存在哈希数组中。用一个哈希函数来获取一个键对应的索引;如果存在冲突的话(意即,如果两个键产生了同一个哈希值),这些键将会被放入一个链表,其中每个元素对应一个数组项。当Lua需要向表中添加一个新的键,但哈希数组已满时,Lua将会重新哈希。重新哈希的第一步是决定新的数组部分和哈希部分的大小。因此,Lua遍历所有的元素,计数并对其进行归类,然后为数组部分选择一个大小,这个大小相当于能使数组部分超过一半的空间都被填满的2的最大的幂;然后为哈希部分选择一个大小,相当于正好能容纳哈希部分所有元素的2的最小的幂。

当Lua创建空表时,两个部分的大小都是0。因此,没有为其分配数组。让我们看一看当执行下面的代码时会发生什么:

复制代码 代码如下:

local a = {}
for i = 1, 3 do
    a[i] = true
end


这段代码始于创建一个空表。在循环的第一次迭代中,赋值语句

复制代码 代码如下:

a[1] = true


触发了一次重新哈希;Lua将数组部分的大小设为1,哈希部分依然为空;第二次迭代时

复制代码 代码如下:

a[2] = true


触发了另一次重新哈希,将数组部分扩大为2.最终,第三次迭代又触发了一次重新哈希,将数组部分的大小扩大为4。

 

类似下面的代码

复制代码 代码如下:

a = {}
a.x = 1; a.y = 2; a.z = 3


做的事情类似,只不过增加的是哈希部分的大小。

 

对于大的表来说,初期的几次重新哈希的开销被分摊到整个表的创建过程中,一个包含三个元素的表需要三次重新哈希,而一个有一百万个元素的表也只需要二十次。但是当创建几千个小表的时候,重新哈希带来的性能影响就会非常显著。

旧版的Lua在创建空表时会预选分配大小(4,如果我没有记错的话),以防止在初始化小表时产生的这些开销。但是这样的实现方式会浪费内存。例如,如果你要创建数百万个点(表现为包含两个元素的表),每个都使用了两倍于实际所需的内存,就会付出高昂的代价。这也是为什么Lua不再为新表预分配数组。

如果你使用C编程,可以通过Lua的API函数lua_createtable来避免重新哈希;除lua_State之外,它还接受两个参数:数组部分的初始大小和哈希部分的初始大小[1]。只要指定适当的值,就可以避免初始化时的重新哈希。需要警惕的是,Lua只会在重新哈希时收缩表的大小,因此如果在初始化时指定了过大的值,Lua可能永远不会纠正你浪费的内存空间。

当使用Lua编程时,你可能可以使用构造式来避免初始化时的重新哈希。当你写下

复制代码 代码如下:

{true, true, true}


时,Lua知道这个表的数组部分将会有三个元素,因此会创建相应大小的数组。类似的,如果你写下

复制代码 代码如下:

{x = 1, y = 2, z = 3}


Lua也会为哈希部分创建一个大小为4的数组。例如,执行下面的代码需要2.0秒:

复制代码 代码如下:

for i = 1, 1000000 do
    local a = {}
    a[1] = 1; a[2] = 2; a[3] = 3
end


如果在创建表时给定正确的大小,执行时间可以缩减到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还不够聪明,无法识别表达式(在本例中是数值字面量)指定的数组索引,因此它会为哈希部分创建一个大小为4的数组,浪费内存和CPU时间。

 

两个部分的大小只会在Lua重新哈希时重新计算,重新哈希则只会发生在表完全填满后,Lua需要插入新的元素之时。因此,如果你遍历一个表并清除其所有项(也就是全部设为nil),表的大小不会缩小。但是此时,如果你需要插入新的元素,表的大小将会被调整。多数情况下这都不会成为问题,但是,不要指望能通过清除表项来回收内存:最好是直接把表自身清除掉。

一个可以强制重新哈希的猥琐方法是向表中插入足够多的nil。例如:

 

复制代码 代码如下:

a = {}
lim = 10000000
for i = 1, lim do a[i] = i end              -- 创建一个巨表
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 -- 创建一堆nil元素
print(collectgarbage("count"))              --> 17

 

除非是在特殊情况下,我不推荐使用这个伎俩:它很慢,并且没有简单的方法能知道要插入多少nil才够。

你可能会好奇Lua为什么不会在清除表项时收缩表。首先是为了避免测试写入表中的内容。如果在赋值时检查值是否为nil,将会拖慢所有的赋值操作。第二,也是最重要的,允许在遍历表时将表项赋值为nil。例如下面的循环:

复制代码 代码如下:

for k, v in pairs(t) do
    if some_property(v) then
        t[k] = nil – 清除元素
    end
end


如果Lua在每次nil赋值后重新哈希这张表,循环就会被破坏。

 

如果你想要清除一个表中的所有元素,只需要简单地遍历它:

复制代码 代码如下:

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

 

但是,对于大表来说,这个循环将会非常慢。调用函数next时,如果没有给定前一个键,将会返回表的第一个元素(以某种随机的顺序)。在此例中,next将会遍历这个表,从开始寻找一个非nil元素。由于循环总是将找到的第一个元素置为nil,因此next函数将会花费越来越长的时间来寻找第一个非nil元素。这样的结果是,这个“聪明”的循环需要20秒来清除一个有100,000个元素的表,而使用pairs实现的循环则只需要0.04秒。

[1] 尽管重新哈希算法始终设置数组的大小为2的幂,数组的大小依然可以为任何自然数值。而哈希的大小必须为2的幂,所以第二个参数总是会被圆整为不小于原值的最小的2的幂。

延伸 · 阅读

精彩推荐
  • LuaLua简介、编译安装教程及变量等语法介绍

    Lua简介、编译安装教程及变量等语法介绍

    这篇文章主要介绍了Lua简介、编译安装教程及变量等语法介绍,本文同时讲解了lua注释语法、Lua命令行方式等内容,需要的朋友可以参考下 ...

    junjie3632020-04-14
  • LuaLua实现__add方法重载示例

    Lua实现__add方法重载示例

    这篇文章主要介绍了Lua实现__add方法重载示例,本文直接给出实现代码,需要的朋友可以参考下 ...

    脚本之家7452020-04-24
  • Lua深入探究Lua中的解析表达式

    深入探究Lua中的解析表达式

    这篇文章主要介绍了深入探究Lua中的解析表达式,对于其语法部分的说明和示例都超详细,极力推荐此文!需要的朋友可以参考下 ...

    脚本之家3542020-05-05
  • LuaLua和C语言的交互详解

    Lua和C语言的交互详解

    这篇文章主要介绍了Lua和C语言的交互详解,Lua和C语言通过栈完成交互,本文结合代码实例详细讲解了交互的方法,需要的朋友可以参考下 ...

    果冻想3702020-04-14
  • LuaLua中的元方法__newindex详解

    Lua中的元方法__newindex详解

    这篇文章主要介绍了Lua中的元方法__newindex详解,本文讲解了查询与更新、监控赋值、通过table给另一个table赋值等内容,需要的朋友可以参考下 ...

    笨木头8872020-04-09
  • LuaLua中计算、执行字符串中Lua代码的方法

    Lua中计算、执行字符串中Lua代码的方法

    这篇文章主要介绍了Lua中计算、执行字符串中Lua代码的方法,类似JavaScript中eval函数的功能,在Lua中也可以实现,需要的朋友可以参考下 ...

    脚本之家6322020-04-30
  • LuaLua教程(二):基础知识、类型与值介绍

    Lua教程(二):基础知识、类型与值介绍

    这篇文章主要介绍了Lua教程(二):基础知识、类型与值介绍,本文讲解了Hello World程序、代码规范、全局变量、类型与值等内容,需要的朋友可以参考下 ...

    脚本之家5922020-04-28
  • LuaLua中table库函数方法介绍

    Lua中table库函数方法介绍

    这篇文章主要介绍了Lua中table库函数方法介绍,本文讲解了concat、insert、maxn、remove、sort、foreachi等方法,需要的朋友可以参考下 ...

    脚本之家2502020-04-17