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

Lua 自己实现排序sort比较方法,抛出错误invalid order function for sorting ...

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

明天新功能就要上了,结果刚刚突然QA说项目抛出了错误。握草,吓得立马出了一身汗。

查了一下错误,发现可能是自己写的不稳定排序造成的。自己感觉应该就是。把排序方法写成稳定的之后,代码分离编译进手机,跑了一下木有错误了。脑残的自己为何要对服务器传过来的有序数据进行排序呢?脑抽不明。

下文为转的别人总结的lua库。(该学习的地方还太多)

lua的table库

 

函数列表: 
table.insert(table,[ pos,] value) 
table.remove(table[, pos]) 
table.concat(table[, sep[, i[, j]]]) 
table.sort(table[, comp])



1. insert 和 remove 只能用于数组元素的插入和移出, 进行插入和移出时,会将后面的元素对齐起来。 
    所以在 for 循环中进行 insert 和 remove 的时候要注意插入和移除时是否漏掉了某些项: 
        local t = {1,2,3,3,5,3,6} 
        for i,v in ipairs(t) do 
            if v == 3 then 
                table.remove(t,i) 
            end 
        end 
        -- 错误,第四个 3 没有被移除,ipairs 内部会维护一个变量记录遍历的位置,remove 掉第三个数字 3 之后,ipairs 下一个返回的值是 5 而不是 3 
        
        local t = {1,2,3,3,5,3,6} 
        for i=1, #t do 
            if t[i] == 3 then 
                table.remove(t,i) 
                i = i-1 
            end 
        end 
        -- 错误,i=i-1 这段代码没有用,i 的值始终是从 1 到 #t,for 循环里修改 i 的值不起作用 
        
        local t = {1,2,3,3,5,3,6} 
        for i=#t, 1, -1 do 
            if t[i] == 3 then 
                table.remove(t,i) 
            end 
        end 
        -- 正确,从后往前遍历 
        
        local t = {1,2,3,3,5,3,6} 
        local i = 1 
        while t[i] do 
            if t[i] == 3 then 
                table.remove(t,i) 
            else 
                i = i+1 
            end 
        end 
        -- 正确,自己控制 i 的值是否增加 
     


   
2. concat 可以将 table 的数组部分拼接成一个字符串,中间用 seq 分隔。 
    lua 中字符串的存储方式与 C 不一样,lua 中的每个字符串都是单独的一个拷贝,拼接两个字符串会产生一个新的拷贝,如果拼接操作特别多,就会影响性能: 
        local beginTime = os.clock() 
        local str = "" 
        for i=1, 30000 do 
            str = str .. i 
        end 
        local endTime = os.clock() 
        print(endTime - beginTime) 
        -- 消耗 0.613 秒,产生了 30000 个字符串拷贝,但只有最后一个是有用的

        local beginTime = os.clock() 
        local t = {} 
        for i=1, 30000 do 
            t[i] = i 
        end 
        local str = table.concat(t, "") 
        local endTime = os.clock() 
        print(endTime - beginTime) 
        -- 消耗 0.024 秒,利用 concat,一次性把字符串拼接出来,只产生了一个字符串拷贝 
       



3. sort 可以将 table 数组部分的元素进行排序,需要提供 comp 函数,comp(a, b) 如果 a 应该排到 b 前面,则 comp 要返回 true 。    
    注意,对于 a==b 的情况,一定要返回 false : 
        local function comp(a,b) 
            return a <= b 
        end 
        table.sort(t,comp) 
        -- 错误,可能出现异常:attempt to compare number with nil 
        
        local function comp(a,b) 
            if a == nil or b == nil then 
                return false 
            end 
            return a <= b 
        end 
        table.sort(t,comp) 
        -- 错误,可能出现异常:invalid order function for sorting 
        -- 也可能不报这个异常,但结果是错误的; 
    之所以 a==b 返回true 会引发这些问题,是因为 table.sort 在实现快速排序时没有做边界检测: 
        for (;;) { 
          while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {  // 未检测边界, i 会一直增加 
            if (i>=u) luaL_error(L, "invalid order function for sorting"); 
            lua_pop(L, 1); 
          } 
          while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {  // 未检测边界, j 会一直减少 
            if (j<=l) luaL_error(L, "invalid order function for sorting"); 
            lua_pop(L, 1); 
          } 
          if (j<i) { 
            lua_pop(L, 3); 
            break; 
          } 
          set2(L, i, j); 
        } 
    看以上代码,如果 a==b 时返回 true 且边界上的几个值是相等的话, sort_comp 就无法阻止 i 继续增长,直到超出边界引发异常 attempt to compare number with nil;即使我们对 a 和 b 进行非空判断,也会因为 i 超过边界而引发异常 invalid order function for sorting 
    快速排序是什么,lua 如何实现快速排序,可以参考 lua 源码中的描述,这里不多介绍; 

 

 

---------------------------------------------

所以代码可以写成

  local function comp(a,b) 
            if a == nil or b == nil then 
                return false 
            end 
            if a == b then
         return false
    end
            return a < b
  end 
  table.sort(t,comp) 

意思就是,在a == b 时,不进行交换就可以了。交换的话,就会导致不稳定。

   

 

函数列表: 
table.insert(table,[ pos,] value) 
table.remove(table[, pos]) 
table.concat(table[, sep[, i[, j]]]) 
table.sort(table[, comp])



1. insert 和 remove 只能用于数组元素的插入和移出, 进行插入和移出时,会将后面的元素对齐起来。 
    所以在 for 循环中进行 insert 和 remove 的时候要注意插入和移除时是否漏掉了某些项: 
        local t = {1,2,3,3,5,3,6} 
        for i,v in ipairs(t) do 
            if v == 3 then 
                table.remove(t,i) 
            end 
        end 
        -- 错误,第四个 3 没有被移除,ipairs 内部会维护一个变量记录遍历的位置,remove 掉第三个数字 3 之后,ipairs 下一个返回的值是 5 而不是 3 
        
        local t = {1,2,3,3,5,3,6} 
        for i=1, #t do 
            if t[i] == 3 then 
                table.remove(t,i) 
                i = i-1 
            end 
        end 
        -- 错误,i=i-1 这段代码没有用,i 的值始终是从 1 到 #t,for 循环里修改 i 的值不起作用 
        
        local t = {1,2,3,3,5,3,6} 
        for i=#t, 1, -1 do 
            if t[i] == 3 then 
                table.remove(t,i) 
            end 
        end 
        -- 正确,从后往前遍历 
        
        local t = {1,2,3,3,5,3,6} 
        local i = 1 
        while t[i] do 
            if t[i] == 3 then 
                table.remove(t,i) 
            else 
                i = i+1 
            end 
        end 
        -- 正确,自己控制 i 的值是否增加 
     


   
2. concat 可以将 table 的数组部分拼接成一个字符串,中间用 seq 分隔。 
    lua 中字符串的存储方式与 C 不一样,lua 中的每个字符串都是单独的一个拷贝,拼接两个字符串会产生一个新的拷贝,如果拼接操作特别多,就会影响性能: 
        local beginTime = os.clock() 
        local str = "" 
        for i=1, 30000 do 
            str = str .. i 
        end 
        local endTime = os.clock() 
        print(endTime - beginTime) 
        -- 消耗 0.613 秒,产生了 30000 个字符串拷贝,但只有最后一个是有用的

        local beginTime = os.clock() 
        local t = {} 
        for i=1, 30000 do 
            t[i] = i 
        end 
        local str = table.concat(t, "") 
        local endTime = os.clock() 
        print(endTime - beginTime) 
        -- 消耗 0.024 秒,利用 concat,一次性把字符串拼接出来,只产生了一个字符串拷贝 
       



3. sort 可以将 table 数组部分的元素进行排序,需要提供 comp 函数,comp(a, b) 如果 a 应该排到 b 前面,则 comp 要返回 true 。    
    注意,对于 a==b 的情况,一定要返回 false : 
        local function comp(a,b) 
            return a <= b 
        end 
        table.sort(t,comp) 
        -- 错误,可能出现异常:attempt to compare number with nil 
        
        local function comp(a,b) 
            if a == nil or b == nil then 
                return false 
            end 
            return a <= b 
        end 
        table.sort(t,comp) 
        -- 错误,可能出现异常:invalid order function for sorting 
        -- 也可能不报这个异常,但结果是错误的; 
    之所以 a==b 返回true 会引发这些问题,是因为 table.sort 在实现快速排序时没有做边界检测: 
        for (;;) { 
          while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {  // 未检测边界, i 会一直增加 
            if (i>=u) luaL_error(L, "invalid order function for sorting"); 
            lua_pop(L, 1); 
          } 
          while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {  // 未检测边界, j 会一直减少 
            if (j<=l) luaL_error(L, "invalid order function for sorting"); 
            lua_pop(L, 1); 
          } 
          if (j<i) { 
            lua_pop(L, 3); 
            break; 
          } 
          set2(L, i, j); 
        } 
    看以上代码,如果 a==b 时返回 true 且边界上的几个值是相等的话, sort_comp 就无法阻止 i 继续增长,直到超出边界引发异常 attempt to compare number with nil;即使我们对 a 和 b 进行非空判断,也会因为 i 超过边界而引发异常 invalid order function for sorting 
    快速排序是什么,lua 如何实现快速排序,可以参考 lua 源码中的描述,这里不多介绍; 

 

 

---------------------------------------------

所以代码可以写成

  local function comp(a,b) 
            if a == nil or b == nil then 
                return false 
            end 
            if a == b then
         return false
    end
            return a < b
  end 
  table.sort(t,comp) 

意思就是,在a == b 时,不进行交换就可以了。交换的话,就会导致不稳定。

   


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
【原】lua的table深拷贝发布时间:2022-07-22
下一篇:
openresty开发系列16--lua中的控制结构if-else/repeat/for/while发布时间: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