루아의 배열 배열에 대한 이진 검색

Question

단일 배열 (테이블)에서 작동하는 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 

그러나 배열의 정렬 된 배열 (테이블 테이블)을 검색해야합니다. 그들은

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

루아에서이 작업을 수행하는 가장 빠른 방법은 무엇입니까 같은 비교 연산자 CMP 과부하처럼 뭔가를 할 것 파이썬에서 인덱스 1

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

으로 분류되어 있습니다? 느린 방법으로 생각할 수는 있지만 기능 프로그래밍에 익숙하지 않은 것은 내가 결코 추측 할 수없는 방법이 있는지 궁금하게 만든다.

Answer 1

먼저, 첫 번째 예에서 비교자를 살펴보십시오. 의 간단한 라인을 보자 :

if numericCompare(lo, 0) then 

numericCompare 분명히 function numericCompare(a,b) return a < b end되는 :

if lo < 0 then 

이 같은 무언가로 기록 될 수있다.

음은, 때문에 루아의 테이블의 특성으로 오히려 빠른 tab[1] 접근해야한다, 아마도 일반적으로

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

로 말했다 비교기를 당신이 tableCompare 부를 수있는 뭔가 모든 비교를 변경하고 구현합니다. 코드를 작성하고 프로필을 작성한 다음 최적화를 시도하십시오.

Yoy는 루아에서 연산자를 오버로드 할 수 있지만 그 경우 매개 변수로 비교자를 가져 와서 명시 적으로 명명하면 약간 더 읽기 쉽다고 생각합니다.