2014/05/06

ライブラリ:bisect

Pythonの「 bisect 」というライブラリについてご紹介します。

import bisect

この bisect ライブラリは、名前のとおり bisection search ーーいわゆる二分探索法の関数を提供するライブラリです。

すでにソートされた配列に対して、関数ひとつで二分探索法を行ってくれます。

具体的には、大きく分けて2種類の関数が用意されているので、それらを順番に見ていきます。
bisect_***
insort_***


bisect_***

bisect から始まるメソッドは、二分探索法により指定した値が入るべき箇所の「探索」を行います。探索のみを行い、実際の挿入は行いません。
import bisect

li = [1, 9, 15, 32]
x = 15

print bisect.bisect_left(li, x)
# => 2

print bisect.bisect_right(li, x)
# => 3
bisect_left bisect_right はいずれもふたつの引数を受け取り、ひとつめはソート済みのリスト、ふたつめは単一の値を受け取ります。

いずれも、「ソート済みリストの適切な位置にある値を挿入するとしたら、何番目に挿入することになるか?」というのを調べて返してくれます。元のリストは変更しません。

bisect_left は、同じ値がすでに入っていた場合に、いちばん左に新しい値を挿入すると考えて、その位置を返します。

一方、 bisect_right は、同じ値がすでに入っていた場合に、いちばん右側に挿入するものとして、その位置を返します。

いずれもオプション引数 lo hi を受け取ることができます。 lo はリストの挿入すべき位置の下限を、hiは上限を指定するために使えます。
print bisect.bisect_left(li, x, lo=0, hi=1)
# => 1

left や right のついていない bisect という関数もあり、これは bisect_right と同じ挙動をします。


insort_***

insort から始まるメソッドは、二分探索法により指定した値を適切な位置に「挿入」します。 bisect が探索のみを行うのに対し、こちらの insort は実際の挿入を行います。
bisect.insort_left(li, x)
bisect.insort_right(li, x)

print li  # => [1, 9, 15, 15, 15, 32]
bisect と同様に、 insort_left insort_right もふたつの引数を受け取り、ひとつめにソート済みリストを、ふたつめに挿入したい要素を受け取ります。

いずれも渡されたリストそのものを変更します。

bisect の場合と同様、末尾に left とついている insort_left は挿入できる箇所が複数あったときにいちばん左側に、 insort_right はいちばん右側に挿入します。

left や right のついていない insort というメソッドもあり、こちらは insort_right と同じ挙動をします。
print bisect.insort(li, x)

bisect の場合と同じく insort の場合も挿入する範囲を制限するために lo hi という引数をオプションで与えることができます。

以上です。


参考
8.5. bisect — 配列二分法アルゴリズム — Python 2.7ja1 documentation
The bisect module - (the eff-bot guide to) The Standard Python Library

0 件のコメント: