二进制搜索阵列在Lua

数组的我已经从我的它是如何工作在Python内存，单个阵列（表）的工作书面lua二进制搜索功能。二进制搜索阵列在Lua

function bisect_left(a, x, lo, hi) 
     lo = lo or 1 
     hi = hi or nil 
     if lo < 0 then 
      error('lo must be non-negative') 
     end 
     if hi == nil then 
      hi = #a 
     end 
     while lo < hi do 
      mid = math.floor((lo+hi)/2) 
      if a[mid] < x then 
       lo = mid+1 
      else 
       hi = mid 
      end 
     end 
     return lo 
    end

但后来我遇到了需要搜索排序数组（表的表）。它们是由指数1

squares = {{300, 400, 123456, 9}, {400, 500, 323456, 9}, {420, 610, 5123456, 9}, {530, 700, 8123456, 9}, {840, 960, 9123456, 1}}

排序在Python我会做类似超载的比较操作CMP像

Class overload(object): 
    def __init__(self, value, index): 
     self.value = value 
     self.index = index 
    def __cmp__(self, other): 
     return cmp(self.value, other[self.index])

什么是在Lua做到这一点的最快方法？我可以想到（我认为）慢的方法来做到这一点，但我的功能编程经验不足让我怀疑是否有一种我永远不会猜到的方式。

来源

2013-10-22 Handloomweaver

不应返回LO是在循环后，没有在循环里？ – dasblinkenlight

我猜测，你可以使用'__eq'，'__le'和'__lt' [元表事件]（http://lua-users.org/wiki/MetatableEvents）用于这一目的。和'__newindex'用于生成适当的表。试图拿出简略说明代码段。 – Kamiccolo

谢谢dasblinkenlight！一连写了lua一天，所有的“结束”都不停地绊倒我 – Handloomweaver

首先，看看什么是你的第一个例子比较。让我们举一个简单的一行：

if lo < 0 then

这可以写成这样：

if numericCompare(lo, 0) then

numericCompare是明显function numericCompare(a,b) return a < b end。

那么，相当快改变所有比较的东西，你可以称之为tableCompare，并实施上述比较，大概是作为

function tableCompare(a,b) 
    return a[1] < b[1] 
end

一般来说，tab[1]访问应该是由于lua的表的性质。编码，配置文件，然后才尝试优化。

同比可以在Lua重载运营商，但在这种情况下，我认为，走的是比较作为参数，并明确地将其命名为稍微更具可读性。

来源

2013-10-22 15:57:30

二进制搜索阵列在Lua

回答

相关问题