Python에서 문자열 접두어에 대한 이진 검색 수행

Question

주어진 하위 문자열로 시작하는 모든 요소에 대해 정렬 된 문자열 목록을 검색하려고합니다. ['bob', 'bob', 'bob']를 인쇄

import bisect 
names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
names.sort() 
leftIndex = bisect.bisect_left(names, 'bob') 
rightIndex = bisect.bisect_right(names, 'bob') 
print(names[leftIndex:rightIndex]) 

:

다음은 정확한 모든 일치를 발견하는 예입니다.

대신 이으로 시작하고 'bob'인 모든 이름을 검색하고 싶습니다. 원하는 출력은 ['bob', 'bob', 'bob', 'bobby', 'bobert']입니다. bisect 검색의 비교 방법을 수정할 수 있다면 name.startswith('bob')을 사용하면됩니다.

예를 들어, Java에서는 쉽게 할 수 있습니다. 나는 다음과 같이 사용할 것이다 :

Arrays.binarySearch(names, "bob", myCustomComparator); 

여기서 'myCustomComparator'는 startswith 메소드 (및 몇 가지 추가 로직)를 이용하는 비교기이다.

어떻게 이것을 파이썬에서 할 수 있습니까?

Answer 1

bisect은 당신의 chosing의 사용자 정의 비교를 사용하는 인스턴스를 사용하여 사용자 지정 비교를 사용에 속지 할 수 있습니다

>>> class PrefixCompares(object): 
...  def __init__(self, value): 
...   self.value = value 
...  def __lt__(self, other): 
...   return self.value < other[0:len(self.value)] 
... 
>>> import bisect 
>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
>>> names.sort() 
>>> key = PrefixCompares('bob') 
>>> leftIndex = bisect.bisect_left(names, key) 
>>> rightIndex = bisect.bisect_right(names, key) 
>>> print(names[leftIndex:rightIndex]) 
['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert'] 
>>> 

DOH. 오른쪽 이등분은 효과가 있었지만 왼쪽 하나는 분명히 그렇지 않았습니다. "adam"에는 "bob"이라는 접두어가 붙지 않습니다! 그것을 고치려면 순서를 변경해야합니다.

>>> class HasPrefix(object): 
...  def __init__(self, value): 
...   self.value = value 
...  def __lt__(self, other): 
...   return self.value[0:len(other.value)] < other.value 
... 
>>> class Prefix(object): 
...  def __init__(self, value): 
...   self.value = value 
...  def __lt__(self, other): 
...   return self.value < other.value[0:len(self.value)] 
... 
>>> class AdaptPrefix(object): 
...  def __init__(self, seq): 
...   self.seq = seq 
...  def __getitem__(self, key): 
...   return HasPrefix(self.seq[key]) 
...  def __len__(self): 
...   return len(self.seq) 
... 
>>> import bisect 
>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
>>> names.sort() 
>>> needle = Prefix('bob') 
>>> haystack = AdaptPrefix(names) 
>>> leftIndex = bisect.bisect_left(haystack, needle) 
>>> rightIndex = bisect.bisect_right(haystack, needle) 
>>> print(names[leftIndex:rightIndex]) 
['bob', 'bob', 'bob', 'bobby', 'bobert'] 
>>> 

Answer 2

불행히도 bisect은 key 기능을 지정할 수 없습니다. 당신이 할 수있는 일은 가장 높은 색인을 찾기 위해 문자열을 사용하기 전에 문자열에 '\xff\xff\xff\xff'을 추가 한 다음 그 요소들을 취하는 것입니다.

Answer 3

다음은 아직 제공되지 않은 해결책입니다. 이진 검색 알고리즘을 다시 구현하십시오.

코드를 반복하고 있기 때문에 (대개 이진 검색이 엉망이되기 쉽기 때문에) 일반적으로 피해야하지만 좋은 해결책은없는 것 같습니다.

bisect_left()는 이미 원하는 결과를 제공하므로 bisect_right() 만 변경하면됩니다. 참조 용 원래 구현은 다음과 같습니다.

def bisect_right(a, x, lo=0, hi=None): 
    if lo < 0: 
     raise ValueError('lo must be non-negative') 
    if hi is None: 
     hi = len(a) 
    while lo < hi: 
     mid = (lo+hi)//2 
     if x < a[mid]: hi = mid 
     else: lo = mid+1 
    return lo 

다음은 새 버전입니다. 유일한 변화는 내가 and not a[mid].startswith(x) 추가하는 것이 있고, 나는 "bisect_right_prefix"호출 :

def bisect_right_prefix(a, x, lo=0, hi=None): 
    if lo < 0: 
     raise ValueError('lo must be non-negative') 
    if hi is None: 
     hi = len(a) 
    while lo < hi: 
     mid = (lo+hi)//2 
     if x < a[mid] and not a[mid].startswith(x): hi = mid 
     else: lo = mid+1 
    return lo 

지금의 코드는 다음과 같습니다

예상 된 결과 생산

names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
names.sort() 
leftIndex = bisect.bisect_left(names, 'bob') 
rightIndex = bisect_right_prefix(names, 'bob') 
print(names[leftIndex:rightIndex]) 

:

['bob', 'bob', 'bob', 'bobby', 'bobert'] 

을

당신은 어떻게 생각합니까, 이것이 갈 길입니까?

Answer 4

IfLoop의 대답에 대한 대안으로 __gt__을 내장하지 않으시겠습니까?함수형 프로그래밍 배경에서 오는

>>> class PrefixCompares(object): 
...  def __init__(self, value): 
...   self.value = value 
...  def __lt__(self, other): 
...   return self.value < other[0:len(self.value)] 
...  def __gt__(self, other): 
...   return self.value[0:len(self.value)] > other 
>>> import bisect 
>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
>>> names.sort() 
>>> key = PrefixCompares('bob') 
>>> leftIndex = bisect.bisect_left(names, key) 
>>> rightIndex = bisect.bisect_right(names, key) 
>>> print(names[leftIndex:rightIndex]) 
['bob', 'bob', 'bob', 'bobby', 'bobert'] 

Answer 5

, 난 당신이 사용자 정의 비교 함수를 제공 할 수 있습니다하는 것이 일반적 이진 검색 추상화가 아니라고 깜짝 놀라게 해요.

class BisectRetVal(): 
    LOWER, HIGHER, STOP = range(3) 

def generic_bisect(arr, comparator, lo=0, hi=None): 
    if lo < 0: 
     raise ValueError('lo must be non-negative') 
    if hi is None: 
     hi = len(arr) 
    while lo < hi: 
     mid = (lo+hi)//2 
     if comparator(arr, mid) == BisectRetVal.STOP: return mid 
     elif comparator(arr, mid) == BisectRetVal.HIGHER: lo = mid+1 
     else: hi = mid 
    return lo 

일반 부분이었다 : 또 다시 그 일을 복제 또는 중대한 읽을 OOP 해킹을 사용하는 자신을 방지하기 위해

는, 간단히 말해서 나는 당신이 언급 한 Arrays.binarySearch(names, "bob", myCustomComparator); 기능의 동등한를 작성했습니다.

>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
>>> names.sort() 
>>> leftIndex = generic_bisect(names, string_prefix_comparator_left("bob")) 
>>> rightIndex = generic_bisect(names, string_prefix_comparator_right("bob")) 
>>> names[leftIndex:rightIndex] 
['bob', 'bob', 'bob', 'bobby', 'bobert'] 

그것은 파이썬이 파이썬 3

모두에서 변경되지 않은 작동 : 다음은이 기능에 적응하여 제공된 스 니펫 코드의

def string_prefix_comparator_right(prefix): 
    def parametrized_string_prefix_comparator_right(array, mid): 
     if array[mid][0:len(prefix)] <= prefix: 
      return BisectRetVal.HIGHER 
     else: 
      return BisectRetVal.LOWER 
    return parametrized_string_prefix_comparator_right 


def string_prefix_comparator_left(prefix): 
    def parametrized_string_prefix_comparator_left(array, mid): 
     if array[mid][0:len(prefix)] < prefix: # < is the only diff. from right 
      return BisectRetVal.HIGHER 
     else: 
      return BisectRetVal.LOWER 
    return parametrized_string_prefix_comparator_left 

: 그리고 여기에 특정 사건에 대한 비교기이다 이 작동 방식과 더 많은 비교 자에 대한 자세한 내용은이 요지를 확인하십시오. https://gist.github.com/Shnatsel/e23fcd2fe4fbbd869581