二進制搜索陣列在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

回答

相關問題