• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

谈谈lua中的table.remove()以及loop+table.remove()误区

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

  前几天在修复一个bug的时候发现代码中使用了泛型for+ipairs()+table.remove()删除元素,毫无疑问,这是一种错误的做法,但因为历史配置内容原因,导致这个BUG在之前一直没表现出来。lua中,在for循环中调用函数ipairs时,ipairs会返回3个值,迭代函数、不可变状态表、初始控制变量0,for的每次调用,都会把状态表和控制变量传入迭代函数,调用迭代函数,把控制变量+1,再获取状态表中相应元素,并把两者返回,直至遇到nil结束;而函数table.remove除了删除、返回指定序列上的元素,还会把后面的元素往前移动。故而知,当表中相邻的两个元素都需要删除的时候,就会发生删除不干净的情况。表是肯定需要遍历一遍的,现在问题就是,该以怎样一种方式去遍历表,达到正确删除元素的目的。首先,如果是无序表,直接把对应位置上的元素置nil;如果是有序表,比较常用的方法有以下3种:

1 local a = {1, 1, 2, 3, 4, 4}
2 for i = #a, 1, -1 do
3     if a % 2 == 0 then
4         table.remove(a, i)
5     end
6 end
1.数值型for从后往前遍历
 1 local a = {1, 1, 2, 3, 4, 4}
 2 local index = 1
 3 local v = a[index]
 4 while v do
 5     if v % 2 == 0 then
 6         table.remove(a, index)
 7     else
 8         index = index + 1
 9     end
10 
11     v = a[index]
12 end
2.while控制下标方式
1 local a = {1, 1, 2, 3, 4, 4}
2 local tmp = {}
3 for k, v in ipairs(a) do
4     if v % 2 == 0 then
5         table.insert(tmp, v)
6     end
7 end
8 a = tmp
3.构建临时表方式

这3种方式的而且确都可以实现对表元素的删除,但好与不好真的值得商榷。或许事情还可以进一步思考和优化。回到table.remove()本身,上面说到,table.remove()删除位置上的元素后还会把此位置后面的元素往前移,这里涉及到了一个效率问题。如果是有序表,在某个时刻仅需要删除一个位置上的元素且继续保持有序,table.remove()是必然选择,但是,如果需要遍历表删除,选择table.remove()是否还是正确的做法?答案肯定是否定的,每一次remove,都移动了大量元素,而loop+table.remove(),明显做了很多没有意义的工作。那上面的方式3是否就成了最佳选择,答案也是否定。因为表的构造也需要时间,虽然基本可以忽略不计,但更重要的是,如果因为原表较大,触发了新表的luaH_resize,即内存重新分配,这开销就变的大了,在c中,内存申请这方面一直是性能短板。那应该以怎样一种方式更好地实现上面loop+table.remove()?

  我们知道,在lua中回收一个元素,直接把它置nil即可。于是,对于有序表,可以得出以下实现:

 1 local a = {1, 1, 2, 3, 4, 4}
 2 local index, r_index, length = 1, 1, #a
 3 while index <= length do
 4     local v = a[index]
 5     a[index] = nil
 6     if not (v % 2 == 0) then
 7         a[r_index] = v
 8         r_index = r_index + 1
 9     end
10 
11     index = index + 1
12 end
Achieve1

封装一下:

 1 local tb = {}
 2 
 3 function tb.remove(obj, rm_func)
 4     if type(obj) ~= "table" or type(rm_func) ~= "function" then
 5         return
 6     end
 7 
 8     local index, r_index, length = 1, 1, #obj
 9     while index <= length do
10         local v = obj[index]
11         obj[index] = nil
12         if not rm_func(v) then
13             obj[r_index] = v
14             r_index = r_index + 1
15         end
16 
17         index = index + 1
18     end
19 end
20 
21 return tb
Achieve2

到这里,我们仿佛已经通过Achieve2实现了一种更好的方案来取替loop+table.remove(),下面附上测试代码来看看运行时间对比:

 1 local tb = {}
 2 
 3 function tb.remove(obj, rm_func)
 4     if type(obj) ~= "table" or type(rm_func) ~= "function" then
 5         return
 6     end
 7 
 8     local index, r_index, length = 1, 1, #obj
 9     while index <= length do
10         local v = obj[index]
11         obj[index] = nil
12         if not rm_func(v) then
13             obj[r_index] = v
14             r_index = r_index + 1
15         end
16 
17         index = index + 1
18     end
19 end
20 
21 local a = {}
22 local b = {}
23 local c = {}
24 local d = {}
25 local length = 1024*128
26 for i = 1, length do
27     a[i] = i
28     b[i] = i
29     c[i] = i
30     d[i] = i
31 end
32 
33 rm_func = function(value)
34     return value % 2 == 0
35 end
36 local start_time = os.clock()
37 
38 --test-(1.数值型for从后往前遍历)
39 for i = #a, 1, -1 do
40     if rm_func(a[i]) then
41         table.remove(a, i)
42     end
43 end
44 print("1.数值型for从后往前遍历 time:", os.clock() - start_time)
45 
46 --test-(2.while控制下标方式)
47 start_time = os.clock()
48 local index = 1
49 local v = b[index]
50 while v do
51     if rm_func(v) then
52         table.remove(b, index)
53     else
54         index = index + 1
55     end
56     
57     v = b[index]
58 end
59 print("2.while控制下标方式 time:", os.clock() - start_time)
60 
61 --test-(3.构建临时表方式)
62 start_time = os.clock()
63 local tmp = {}
64 for k, v in ipairs(c) do
65     if v % 2 == 0 then
66         table.insert(tmp, v)
67     end
68 end
69 c = tmp
70 print("3.构建临时表方式 time:", os.clock() - start_time)
71 
72 --test-(tb.remove)
73 start_time = os.clock()
74 tb.remove(d, rm_func)
75 print("tb.remove time:", os.clock() - start_time)
Test Code

看到输出,已经百分比确定Achieve2是更好的做法,即使是通过构建临时表的方式3依然比Achieve2差了9倍左右,而且毫无疑问方式3内存占用更高;当然,实际测试时间还受到具体环境影响,但是Achieve2比loop+table.remove()效率更高已经可以盖棺定论,由此可以想到,loop+table.remove()本身就是一个极其不合格的做法,是一个误区,table.remove()的设计初衷肯定不是让你在loop中使用。


  文章到这里已经明确Achieve2是更好的替代方案,但是否可以让Achieve2变得更健全一点?如果表是无序表,或者表既有无序部分也有有序部分,当中的元素都需要遍历判断删除怎么办,上述的Achieve2只能用于有序表,就是表的元素只存在于table的数组部分,哈希部分为空的情况下,那么是否能进一步更改Achieve2的实现使适用于所有情况?首先,要明确的是,lua提供的运算符和表标准库函数都只能获取表数组部分长度,对于总体长度,是获取不了的,所以不在事先遍历一次表的情况下无法判断一个表到底是有序表还是无序表;其次,要使Achieve2适用所有情况,必须使用pairs()遍历,使用pairs()遍历,具体算法是否依然能把Achieve2的时间复杂度控制在O(n)?

  详细了解一下函数pairs机制,函数pairs在调用的时候会返回lua的一个基本函数next和不可变状态表t,调用next(t, key)时,该函数会以随机次序返回表中的下一个key及其对应的值,调用next(t, nil)时,返回表中的第一个键值对,所有元素遍历完时,函数next返回nil,for循环总是会把表达式列表的结果调整为3个值,所以,在调用pairs()的时候,得到的相当于next, t, nil;next函数的底层lua实现lua_next中,总是先遍历数组部分,再遍历哈希部分,基于pairs的这些具体行为,我们可以得到Achieve3:

 1 local tb = {}
 2 
 3 function tb.remove(obj, rm_func)
 4     if type(obj) ~= "table" or type(rm_func) ~= "function" then
 5         return
 6     end
 7 
 8     local r_index, length = 1, #obj
 9     for k, v in pairs(obj) do        --lua5.3可以通过math.type(k)判断
10         if type(k) == "number" and math.floor(k) == k and k > 0 and k <= length then
11             local tmp = v
12             obj[k] = nil
13             if not rm_func(tmp) then
14                 obj[r_index] = tmp
15                 r_index = r_index + 1
16             end
17         else
18             if rm_func(v) then
19                 obj[k] = nil
20             end
21         end
22     end
23 end
24 
25 return tb
Achieve3

Achieve3好像是个不错的实现,但是看着那一堆判断就头疼,那还有没有更好的实现方法,有,就是先遍历表数组部分,然后改写pairs行为,使只遍历哈希部分,下面是Achieve4:

 1 local tb = {}
 2 
 3 function tb.remove(obj, rm_func)
 4     if type(obj) ~= "table" or type(rm_func) ~= "function" then
 5         return
 6     end
 7 
 8     local index, r_index, length = 1, 1, #obj
 9     while index <= length do
10         local v = obj[index]
11         obj[index] = nil
12         if not rm_func(v) then
13             obj[r_index] = v
14             r_index = r_index + 1
15         end
16 
17         index = index + 1
18     end
19 
20     local function _pairs(tb)
21         if length == 0 then
22             return next, tb, nil
23         else
24             return next, tb, length
25         end
26     end
27 
28     for k, v in _pairs(obj) do
29         if rm_func(v) then
30             obj[k] = nil
31         end
32     end
33 end
34 
35 return tb
Achieve4

但是到此我们依然面临着一种具体情况,那就是我们希望在表的有序部分删除元素后,后面的元素保持不动,于是再度改写Achieve4,得到Achieve5:

 1 local tb = {}
 2 
 3 function tb.remove(obj, rm_func, to_sequence)
 4     if type(obj) ~= "table" or type(rm_func) ~= "function" then
 5         return
 6     end
 7 
 8     local length = 0
 9     if to_sequence then
10         length = #obj
11         local index, r_index = 1, 1
12         while index <= length do
13             local v = obj[index]
14             obj[index] = nil
15             if not rm_func(v) then
16                 obj[r_index] = v
17                 r_index = r_index + 1
18             end
19 
20             index = index + 1
21         end
22     end
23 
24     local function _pairs(tb)
25         if length == 0 then
26             return next, tb, nil
27         else
28             return next, tb, length
29         end
30     end
31 
32     for k, v in _pairs(obj) do
33         if rm_func(v) then
34             obj[k] = nil
35         end
36     end
37 end
38 
39 return tb
Achieve5

  好了,到此文章已经差不多结束了,上面的内容纯属原创都是本人在工作中的实际见解,水平有限,这也是本人的第一次更博,以后还会继续把自己的经验分享出来,如果有错误的地方还请不吝指出。下面附上本人写的一些拓展table函数(主要用于个人测试):

  1 local tb = {}
  2 
  3 --to_sequence可选且只会在表有序部分起作用,时间复杂度O(n)
  4 function tb.remove(obj, rm_func, to_sequence)
  5     if type(obj) ~= "table" or type(rm_func) ~= "function" then
  6         return
  7     end
  8 
  9     local length = 0
 10     if to_sequence then
 11         length = #obj
 12         local index, r_index = 1, 1
 13         while index <= length do
 14             local v = obj[index]
 15             obj[index] = nil
 16             if not rm_func(v) then
 17                 obj[r_index] = v
 18                 r_index = r_index + 1
 19             end
 20 
 21             index = index + 1
 22         end
 23     end
 24 
 25     local function _pairs(tb) --lua_next实现是迭代完数组部分再迭代哈希部分
 26         if length == 0 then
 27             return next, tb, nil
 28         else
 29             return next, tb, length
 30         end
 31     end
 32 
 33     for k, v in _pairs(obj) do
 34         if rm_func(v) then
 35             obj[k] = nil
 36         end
 37     end
 38 end
 39 
 40 function tb.duplicate(obj)
 41     local tb_note = {} --使指向行为与原表一致
 42     local copy_func
 43     copy_func = function(obj)
 44         if type(obj) ~= "table" then
 45             return obj
 46         elseif tb_note[obj] then
 47             return tb_note[obj]
 48         end
 49 
 50         local dup = {}
 51         tb_note[obj] = dup
 52         for k, v in pairs(obj) do
 53             dup[copy_func(k)] = copy_func(v)
 54         end
 55         setmetatable(dup, getmetatable(obj))
 56         return dup
 57     end
 58 
 59     return copy_func(obj)
 60 end
 61 
 62 function tb.tostring(obj)
 63     local tb_note = {} --防止相同表转换多次
 64     local function serialize(value)
 65         if tb_note[value] then
 66             return tb_note[value]
 67         elseif type(value) == "number" then
 68             return string.format("%d", value) --%a
 69         elseif type(value) == "string" then
 70             return string.format("%q", value) --5.3.3版本后可以使用%q转化number,nil,boolean
 71         elseif type(value) == "table" then
 72             local str = "{"
 73             local index_tb = tb.getsortedindexlist(value)
 74             for _, v in ipairs(index_tb) do
 75                 str = str.."["..serialize(v).."]="..serialize(value[v])..","
 76             end
 77             local mt = getmetatable(value)
 78             if mt then str = str.."[\"metatable\"]="..serialize(mt).."," end
 79             str = str.."}"
 80             
 81             tb_note[value] = str
 82             return str
 83         else
 84             return tostring(value)
 85         end
 86     end
 87 
 88     return serialize(obj)
 89 end
 90 
 91 local type_value = {["number"] = 1, ["string"] = 2, ["userdata"] = 3, ["function"] = 4, ["table"] = 5}
 92 function tb.getsortedindexlist(obj)
 93     local index_tb = {}
 94     for k in pairs(obj) do
 95         table.insert(index_tb, k)
 96     end
 97 
 98     local sort_func = function(a, b)
 99         local type_a = type_value[type(a)]
100         local type_b = type_value[type(b)]
101         if type_a ~= type_b then
102             return type_a < type_b
103         else
104             if type_a == 1 or type_a == 2 then
105                 return a < b
106             elseif type_a == 5 then
107                 return tb.getlen(a) < tb.getlen(b)
108             else
109                 return false
110             end
111         end
112     end
113 
114     table.sort(index_tb, function(a, b) return sort_func(a, b) end)
115     return index_tb
116 end
117 
118 function tb.getlen(obj)
119     local count = 0
120     for k, v in pairs(obj) do
121         count = count + 1
122     end
123 
124     return count
125 end
126 
127 function tb.show(obj)
128     for k, v in pairs(obj) do
129         print(k, v)
130     end
131     local mt = getmetatable(obj)
132     if mt then
133         print("metatable", mt)
134     end
135 end
136 
137 return tb
Table Code

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Unity3D热更新之LuaFramework篇[05]--Lua脚本调用c#以及如何在Lua中使用Dotween ...发布时间:2022-07-22
下一篇:
Lua与C的交互发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap