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']です。バイセクト検索の比較方法を変更できる場合は、name.startswith('bob')を使用してこれを行うことができます。

例として、Javaでは簡単です。

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

ここで 'myCustomComparator'は、startswithメソッド（および追加のロジック）を利用するコンパレータです。

これをPythonでどうやって行うのですか？

Answer 1

bisectはあなたの択一のカスタムコンパレータを使用して、インスタンスを使用して、カスタム比較を使用して、だまされてはいけできます。右の二等分は機能したが、左のものは明らかにそうではなかった。 "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'を追加し、それらの要素を取ることです。

>>> 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：

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

関数プログラミングのバックグラウンドからは、カスタム比較関数を提供できる共通のバイナリ検索抽象は存在しないという点を誇張しています。何度も何度もその事を複製または総額と読めないOOPのハックを使用してから自分自身を防ぐため

、私は単にあなたが言及したArrays.binarySearch(names, "bob", myCustomComparator);機能の同等書いた：

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 

一般的な部分でした。そして、ここであなたのケースのための具体的なコンパレータです：

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

それは

のPython 2とPython 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