bisectは下記を実現するモジュールです。
- リストに対象の値を挿入した場合に、リストの順序性が保たれる様なインデックスを返す。
- リストの順序性が保たれる様なインデックスに対象の値を挿入する。
モジュールの各関数で使用するリストは、昇順にソートされている必要があります。
二分法(bisection)アルゴリズムを使用しているため、モジュールはbisectと呼ばれています。
bisectの基本的な使用方法
基本的な使用方法は下記です。
- モジュールをインポートする
- (ソートしていない場合は、)リストを昇順にソートする。
- bisectの任意の関数を呼び出す。※ここでは、bisect_leftを呼び出しています。
import bisect l = [9, 7, 5, 3, 1] x = 5 l = sorted(l) print (bisect.bisect_left(l, x)) """出力 2 """
昇順でソートすべき理由
降順でソートされていると、下記の様に誤った値が返されます。誤っていることは、bisect_leftを確認することでわかります。
l = [9, 7, 5, 5, 3, 1] x = 5 print (bisect.bisect_left(l, x)) """出力 0 """
各種関数の使い方
bisect_left
リストに対象の値を挿入した場合に、リストの順序性が保たれる様なインデックスを返します。
リストに既に対象の値が存在する場合は、 リストの順序性が保たれる様なインデックスのうち最も左にあるものを返します(*1)。
(*1)最も左にある既存要素のインデックスと一致します。
下記では、lの中から、xを挿入できるインデックスを探しています。
import bisect l = [9, 7, 5, 5, 3, 1] x = 5 l = sorted(l) print(l) """出力 [1, 3, 5, 5, 7, 9] """ print (bisect.bisect_left(l, x)) """出力 2 """
bisect_leftで2を返している理由を説明します。
- x=5をリストlに挿入する場合、リストの順序性が保たれるインデックスは2, 3, 4です(インデックスは0からです)。
- リストの順序性が保たれる様なインデックスのうち最も左にあるものを返すので、2を返します。
bisect_right
リストに対象の値を挿入した場合に、リストの順序性が保たれる様なインデックスを返します。
リストに既に対象の値が存在する場合は、 リストの順序性が保たれる様なインデックスのうち最も右にあるものを返します(*1)。
(*1)最も右にある既存要素のインデックス+1と一致します。
下記では、lの中から、xを挿入できるインデックスを探しています。
import bisect l = [9, 7, 5, 5, 3, 1] x = 5 l = sorted(l) print(l) """出力 [1, 3, 5, 5, 7, 9] """ print (bisect.bisect_right(l, x)) """出力 4 """
bisect_rightで4を返している理由を説明します。
- x=5をリストlに挿入する場合、リストの順序性が保たれるインデックスは2, 3, 4です(インデックスは0からです)。
- リストの順序性が保たれる様なインデックスのうち最も右にあるものを返すので、4を返します。
insort_left
bisect_leftで返されるインデックスと同じ位置に、対象の値を挿入します。
import bisect l = [9, 7, 5, 5, 3, 1] x = 2 l = sorted(l) print(l) """出力 [1, 3, 5, 5, 7, 9] """ print (bisect.bisect_left(l, x)) """出力 1 """ bisect.insort_left(l, x) print(l) """出力 [1, 2, 3, 5, 5, 7, 9] """
insort_right
bisect_rightで返されるインデックス と同じ位置 に、対象の値を挿入します。
import bisect l = [9, 7, 5, 5, 3, 1] x = 5 l = sorted(l) print(l) """出力 [1, 3, 5, 5, 7, 9] """ print (bisect.bisect_right(l, x)) """出力 4 """ bisect.insort_right(l, x) print(l) """出力 [1, 3, 5, 5, 5, 7, 9] """
Japanese 
English
コメント