pythonのbisectについて色々調べ直したことメモ

pythonのbisectについて

二分探索や、ソートされた順序に保ちつつ挿入する機能をサポートしている。

docs.python.org bisect --- 配列二分法アルゴリズム
このモジュールは、挿入の度にリストをソートすることなく、リストをソートされた順序に保つことをサポートします。大量の比較操作を伴うような、アイテムがたくさんあるリストでは、より一般的なアプローチに比べて、パフォーマンスが向上します。動作に基本的な二分法アルゴリズムを使っているので、 bisect と呼ばれています。ソースコードはこのアルゴリズムの実例として一番役に立つかもしれません (境界条件はすでに正しいです!)。

次の関数が用意されています

import bisect              
bisect.bisect_left(a, x)   # aのリストに対して値xを二分探索して、左側の挿入点を返す
bisect.bisect_right(a, x)  # aのリストに対して値xを二分探索して、右側の挿入点を返す
bisect.bisect(a, x)        # bisect_right(a, x)と同様
bisect.insort_left(a, x)   # ソートされた順序に保ちつつ挿入する
bisect.insort_right(a, x)  # ソートされた順序に保ちつつ挿入する、insort_leftと似ている
bisect.insort(a, x)        # ソートされた順序に保ちつつ挿入する、insort_leftと似ている

bisect_left(a, x)/bisect_right(a, x)

実際に使ってみる。

test.py

import bisect
a = [2, 3, 5, 7, 11, 13, 17, 19]
print(bisect.bisect_left(a, 11))
print(bisect.bisect_right(a, 11))
print(bisect.bisect(a, 11))

$ python test.py
4
5
5

確かに挿入すべき配列のindexが探索できているように見える。indexのみであれば十分であるが、
配列中に比較対象の数値を超える最小の数値は、、等を探索したい場合は少し使い勝手があと一歩である。
この解決のために、以下のような使い方が紹介されている。
ソート済みリストの探索

test.py

import bisect              
def index(a, x):     # 探索したい数値のindexを探索
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):   # 探索したい数値未満のうち最大の数値を探索
    'Find rightmost value less than x'
    i = bisect.bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):   # 探索したい数値以下のうち最大の数値を探索
    'Find rightmost value less than or equal to x'
    i = bisect.bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):   # 探索したい数値を超えるもののうち最小の数値を探索
    'Find leftmost value greater than x'
    i = bisect.bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):   # 探索したい数値以上のうち最小の数値を探索
    'Find leftmost item greater than or equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

a = [2, 3, 5, 7, 11, 13, 17, 19]

print(index(a, 11))
print(find_lt(a, 11))
print(find_le(a, 11))
print(find_gt(a, 11))
print(find_ge(a, 11))

実行

$ python test.py
4
7
11
13
11

bisect.insort_left(a, x)/bisect.insort_right(a, x)/bisect.insort(a, x)

二分探索しつつ挿入までしてくれる。
実際に使ってみる。

一応、bisect.insort_left(a, x)/bisect.insort_right(a, x)には違いがある様子

insort_left() と似ていますが、 a に含まれる x のうち、どのエントリーよりも後ろに x を挿入します。

test.py

import bisect
a = [2, 3, 5, 7, 11, 13, 17, 19]

bisect.insort_left(a, 11)
print(a)
bisect.insort_right(a, 10)
print(a)
bisect.insort(a, 12)
print(a)

$ python test.py
[2, 3, 5, 7, 11, 11, 13, 17, 19]
[2, 3, 5, 7, 10, 11, 11, 13, 17, 19]
[2, 3, 5, 7, 10, 11, 11, 12, 13, 17, 19]

他にも、部分文字列を指定可能のようである。
これってどんな時に使うのだろうか、使う機会があれば本記事も更新するかもしれない。

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
リストの中から検索する部分集合を指定するには、パラメータの lo と hi を使います。デフォルトでは、リスト全体が使われます。

現場からは以上です

追記

from bisect import bisect_right, bisect_left, insort_left, insort_rightとしておくと便利である。

from bisect import bisect_right, bisect_left, insort_left, insort_right
import bisect
a = [2, 3, 5, 7, 11, 13, 17, 19]

insort_left(a, 11)
print(a)
insort_right(a, 10)
print(a)
print(bisect_left(a, 11))
print(bisect_right(a, 11))

参考

docs.python.org bisect --- 配列二分法アルゴリズム