1

I have written a binary search function in Lua from my memory of how it works in Python which works on a single array (table).

    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

but then I encountered needing to search a sorted array of arrays (table of tables). They are sorted by index 1

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

In Python I would do something like overload the comparison operator cmp like

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])

What is the fastest way to do this in Lua? I can think of (I presume) slow ways to do it but my functional programming inexperience makes me wonder if there is a way I would never guess.

4

1 回答 1

2

首先，看看第一个示例中的比较器是什么。让我们用一条简单的线：

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 表的性质，访问应该相当快。对其进行编码、配置文件，然后才尝试优化。

Yoy 可以在 Lua 中重载运算符，但在这种情况下，我认为将比较器作为参数并明确命名它更具可读性。

于 2013-10-22T15:57:30.407 回答