前几天在修复一个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 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
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种方式的而且确都可以实现对表元素的删除，但好与不好真的值得商榷。或许事情还可以进一步思考和优化。回到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
封装一下：
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实现了一种更好的方案来取替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)
看到输出，已经百分比确定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好像是个不错的实现，但是看着那一堆判断就头疼，那还有没有更好的实现方法，有，就是先遍历表数组部分，然后改写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，得到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
好了，到此文章已经差不多结束了，上面的内容纯属原创都是本人在工作中的实际见解，水平有限，这也是本人的第一次更博，以后还会继续把自己的经验分享出来，如果有错误的地方还请不吝指出。下面附上本人写的一些拓展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
请发表评论