python - Python での二分探索 (bisection)

Question

リスト/タプルでバイナリ検索を実行し、見つかった場合はアイテムの位置を返し、そうでない場合は「False」(-1、なしなど) を返すライブラリ関数はありますか?

bisect モジュールで関数 bisect_left/right を見つけましたが、項目がリストにない場合でも位置を返します。それは意図した使用法ではまったく問題ありませんが、アイテムがリストにあるかどうかを知りたいだけです(何も挿入したくない)。

その位置にある項目が検索対象のものと等しいかどうかを使用しbisect_leftて確認することを考えましたが、それは面倒なようです (また、その数がリスト内の最大数よりも大きくなる可能性があるかどうかの境界チェックも行う必要があります)。もっと良い方法があれば、私はそれについて知りたいです。

編集これが必要な理由を明確にするために：辞書がこれに非常に適していることは承知していますが、メモリ消費をできるだけ低く抑えようとしています。私の意図する使用法は、一種の双方向ルックアップテーブルです。テーブルに値のリストがあり、インデックスに基づいて値にアクセスできる必要があります。また、値がリストにない場合は、特定の値または None のインデックスを見つけられるようにしたいと考えています。

これには辞書を使用するのが最も速い方法ですが、メモリ要件が (約) 2 倍になります。

Python ライブラリで何かを見落としている可能性があると考えて、この質問をしていました。Moeが提案したように、私は自分のコードを書かなければならないようです。

score 262 · Accepted Answer

bisect_leftpソートされた順序を維持しながら、指定されたソートされた範囲内で要素を挿入できる最初の位置を見つけます。それが範囲内に存在するx場合の位置にxなります。pが終了位置を過ぎている場合、x見つかりませんでした。xそれ以外の場合は、が見つかったかどうかを確認するためにそこにあるかどうかをテストできますx。

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

score 55 · Accepted Answer

bisect_left/right のコードを見て、目的に合わせて調整してみてください。

このような：

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

score 39 · Accepted Answer

これは少し話題から外れていますが（Moeの答えはOPの質問に対して完全であるように見えるため）、手順全体の複雑さを端から端まで調べる価値があるかもしれません. 並べ替えられたリスト (バイナリ検索が役立つ場所) に物を格納し、存在を確認するだけの場合、(指定されていない限り、最悪の場合):

ソートされたリスト

O( n log n) 最初にリストを作成します (ソートされていないデータの場合は O(n) 、ソートされている場合)
O( log n) ルックアップ (これは二分探索部分です)
O( n ) 挿入/削除 (パターンに応じて、O(1) または O(log n) の平均的なケースになる可能性があります)

一方、を使用すると、発生しset()ます

作成する O(n)
O(1) ルックアップ
O(1) 挿入 / 削除

ソートされたリストが実際に取得するのは、「次」、「前」、および「範囲」(範囲の挿入または削除を含む) であり、開始インデックスが与えられると、O(1) または O(|range|) になります。この種の操作を頻繁に使用しない場合は、セットとして保存し、表示用に並べ替えた方が全体的に良い場合があります。 set()Python では追加のオーバーヘッドがほとんど発生しません。

score 16 · Accepted Answer

bisect ドキュメントが検索の例を提供するようになったことに言及する価値があるかもしれません: http://docs.python.org/library/bisect.html#searching-sorted-lists

(-1 または None を返す代わりに ValueError を上げると、より Pythonic になります。たとえば、list.index() がそれを行います。ただし、もちろん、必要に応じて例を調整できます。)

score 11 · Accepted Answer

最も簡単なのは、バイセクトを使用し、1つの位置をチェックして、アイテムがそこにあるかどうかを確認することです。

def binary_search(a,x,lo=0,hi=-1):
    i = bisect(a,x,lo,hi)
    if i == 0:
        return -1
    elif a[i-1] == x:
        return i-1
    else:
        return -1

score 8 · Accepted Answer

これはマニュアルからのものです：

http://docs.python.org/2/library/bisect.html

8.5.1. ソートされたリストの検索

上記の bisect() 関数は、挿入ポイントを見つけるのに役立ちますが、一般的な検索タスクに使用するのは難しいか扱いにくい場合があります。次の 5 つの関数は、それらをソートされたリストの標準ルックアップに変換する方法を示しています。

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

したがって、わずかな変更により、コードは次のようになります。

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

score 7 · Accepted Answer

これは次のとおりです。

再帰的ではない (これにより、ほとんどの再帰的アプローチよりもメモリ効率が高くなります)
実際に働いている
不要なifや条件なしで実行されるため高速
(low + high)/2 のフロアは常に high より小さく、lowが下限でhighが上限であるという数学的な主張に基づいています。

def binsearch(t, key, low = 0, high = len(t) - 1):
    # bisecting the range
    while low < high:
        mid = (low + high)//2
        if t[mid] < key:
            low = mid + 1
        else:
            high = mid
    # at this point 'low' should point at the place
    # where the value of 'key' is possibly stored.
    return low if t[low] == key else -1

score 6 · Accepted Answer

bisect モジュールを使用した@DaveAbrahamsの回答が正しいアプローチであることに同意します。彼は答えの中で 1 つの重要な詳細について言及しませんでした。

ドキュメントから bisect.bisect_left(a, x, lo=0, hi=len(a))

二分モジュールでは、検索配列を事前に計算する必要はありません。デフォルトのおよびbisect.bisect_leftを使用する代わりに、エンドポイントをに提示するだけです。0len(a)

私の使用にとってさらに重要なことは、特定の関数のエラーが最小化されるような値 X を探すことです。そのためには、代わりに bisect_left のアルゴリズムに私の計算を呼び出させる方法が必要でした。これは本当に簡単です。

__getitem__として定義するオブジェクトを提供するだけですa

たとえば、bisect アルゴリズムを使用して、任意の精度で平方根を見つけることができます。

import bisect

class sqrt_array(object):
    def __init__(self, digits):
        self.precision = float(10**(digits))
    def __getitem__(self, key):
        return (key/self.precision)**2.0

sa = sqrt_array(4)

# "search" in the range of 0 to 10 with a "precision" of 0.0001
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)

score 4 · Accepted Answer

Dave Abrahams のソリューションは優れています。私はそれを最小限にしていただろうが：

def binary_search(L, x):
    i = bisect.bisect_left(L, x)
    if i == len(L) or L[i] != x:
        return -1
    return i

score 4 · Accepted Answer

存在するかどうかだけを確認したい場合は、リストを dict に変換してみてください。

# Generate a list
l = [n*n for n in range(1000)]

# Convert to dict - doesn't matter what you map values to
d = dict((x, 1) for x in l)

count = 0
for n in range(1000000):
    # Compare with "if n in l"
    if n in d:
        count += 1

私のマシンでは、「if n in l」には 37 秒かかりましたが、「if n in d」には 0.4 秒かかりました。

score 2 · Accepted Answer

Python には明示的な二分探索アルゴリズムはありませんがbisect、二分探索を使用してソートされたリスト内の要素の挿入ポイントを見つけるように設計されたモジュールがあります。これは、バイナリ検索を実行するように「だまされる」可能性があります。これの最大の利点は、ほとんどのライブラリコードが持っているのと同じ利点です。パフォーマンスが高く、十分にテストされており、問題なく機能します (特にバイナリ検索は、特にエッジケースが慎重に考慮されていない場合、うまく実装するのが非常に難しい場合があります)。

基本タイプ

String や int などの基本的な型の場合は非常に簡単です。必要なのは、bisectモジュールと並べ替えられたリストだけです。

>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False

これを使用して重複を見つけることもできます。

...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']

明らかに、必要に応じて、そのインデックスの値ではなくインデックスを返すことができます。

オブジェクト

カスタム型またはカスタムオブジェクトの場合、少し複雑です。正しく比較するには、豊富な比較メソッドを実装する必要があります。

>>> import bisect
>>> class Tag(object):  # a simple wrapper around strings
...     def __init__(self, tag):
...         self.tag = tag
...     def __lt__(self, other):
...         return self.tag < other.tag
...     def __gt__(self, other):
...         return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']

これは、少なくとも Python 2.7 -> 3.3 で動作するはずです。

score 1 · Accepted Answer

値は実際のオブジェクトへのポインターにすぎないため、格納しているオブジェクトが非常に小さい場合を除き、dict を使用してもメモリ使用量が 2 倍になることはありません。

>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True

その例では、「foo」は一度だけ保存されます。それはあなたにとって違いがありますか？とにかく、正確にはいくつのアイテムについて話しているのでしょうか?

score 1 · Accepted Answer

ウィキペディアの例を確認してくださいhttp://en.wikipedia.org/wiki/Binary_search_algorithm

def binary_search(a, key, imin=0, imax=None):
    if imax is None:
        # if max amount not set, get the total
        imax = len(a) - 1

    while imin <= imax:
        # calculate the midpoint
        mid = (imin + imax)//2
        midval = a[mid]

        # determine which subarray to search
        if midval < key:
            # change min index to search upper subarray
            imin = mid + 1
        elif midval > key:
            # change max index to search lower subarray
            imax = mid - 1
        else:
            # return index number 
            return mid
    raise ValueError

score 1 · Accepted Answer

このコードは、整数リストを再帰的に処理します。リストの長さが 2 未満の最も単純なシナリオを探します。これは、答えが既に存在し、正しい答えを確認するためにテストが実行されることを意味します。そうでない場合は、中間値が設定され、正しいことがテストされます。そうでない場合は、関数を再度呼び出して二分法が実行されますが、左または右にシフトすることにより、上限または下限として中央値が設定されます。

def binary_search (intList、intValue、lowValue、highValue):
    if(高値 - 低値) < 2:
        return intList[lowValue] == intValue または intList[highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue)/2)
    intList[middleValue] == intValue の場合:
        真を返す
    intList[middleValue] > intValue の場合:
        return binary_search(intList, intValue, lowValue, middleValue - 1)
   return binary_search(intList, intValue, middleValue + 1, highValue)

score 0 · Accepted Answer

'''
Only used if set your position as global
'''
position #set global 

def bst(array,taget): # just pass the array and target
        global position
        low = 0
        high = len(array)
    while low <= high:
        mid = (lo+hi)//2
        if a[mid] == target:
            position = mid
            return -1
        elif a[mid] < target: 
            high = mid+1
        else:
            low = mid-1
    return -1

これははるかに優れていて効果的だと思います。私を訂正してください:)。ありがとうございました

score 0 · Accepted Answer

sリストです。
binary(s, 0, len(s) - 1, find)が最初の呼び出しです。

関数は、クエリされた項目のインデックスを返します。そのような項目がない場合は、返されます-1。

def binary(s,p,q,find):
    if find==s[(p+q)/2]:
        return (p+q)/2
    elif p==q-1 or p==q:
        if find==s[q]:
            return q
        else:
            return -1
    elif find < s[(p+q)/2]:
        return binary(s,p,(p+q)/2,find)
    elif find > s[(p+q)/2]:
        return binary(s,(p+q)/2+1,q,find)

python - Python での二分探索 (bisection)

21 に答える 21

基本タイプ

オブジェクト

Related

Reference