1

単一の配列 (テーブル) で動作する Python での動作の記憶から、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でこれを行う最速の方法は何ですか? 私はそれを行うための遅い方法を考えることはできますが (私は推測します)、関数型プログラミングの経験がないため、決して推測できない方法があるかどうか疑問に思います。

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 に答える