bisect --- 陣列二分演算法 (Array bisection algorithm)

原始碼：Lib/bisect.py

這個模組維護一個已經排序過的 list ，當我們每次做完插入後不需要再次排序整個 list 。一個很長的 list 的比較操作很花費時間，可以透過線性搜尋或頻繁地詢問來改善。

這個模組被稱為bisect 是因為它使用基本二分演算法來完成其工作。不像其它搜尋特定值的二分法工具，本模組中的函式旨在定位插入點。因此，這些函式永遠不會呼叫__eq__() 方法來確認是否找到一個值。相反地，這些函式只呼叫__lt__() 方法，並在陣列中的值回傳一個插入點。

此模組提供下面的函式：

bisect.bisect_left(a,x,lo=0,hi=len(a),*,key=None)

在a 當中找到一個位置，讓x 插入後a 仍然是排序好的。參數lo 和hi 用來指定 list 中應該被考慮的子區間，預設是考慮整個 list 。如果a 裡面已經有x 出現，插入的位置會在所有x 的前面（左邊）。回傳值可以被當作list.insert() 的第一個參數，但列表a 必須先排序過。

回傳的插入點ip 將陣列a 劃分為左右兩個切片，使得對於左切片而言all(elem<xforelemina[lo:ip]) 為真，對於右切片而言all(elem>=xforelemina[ip:hi]) 為真。

key 可指定一個單一參數的key function。函式將套用此 function 在陣列所有元素以得到比較值來計算順位。注意此 function 只會套用在陣列中的元素，不會套用在x。

若key 為None，元素將直接進行比較，不會呼叫任何鍵函式。

在 3.10 版的變更:新增key 參數。

bisect.bisect_right(a,x,lo=0,hi=len(a),*,key=None)
bisect.bisect(a,x,lo=0,hi=len(a),*,key=None)

類似bisect_left()，但回傳的插入位置會在所有a 當中的x 的後面（右邊）。

回傳的插入點ip 將陣列a 劃分為左右兩個切片，使得對於左切片而言all(elem<=xforelemina[lo:ip]) 為真，對於右切片而言all(elem>xforelemina[ip:hi]) 為真。

在 3.10 版的變更:新增key 參數。

bisect.insort_left(a,x,lo=0,hi=len(a),*,key=None)

將元素x 插入 lista，並維持順序。

此函式先使用bisect_left() 搜尋插入位置，接著用insert() 於a 以將x 插入，並維持添加元素後的順序。

此函式只有在搜尋時會使用key 函式，插入時不會。

注意雖然搜尋是O(logn)，但插入是O(n)，因此此函式整體時間複雜度是O(n)。

在 3.10 版的變更:新增key 參數。

bisect.insort_right(a,x,lo=0,hi=len(a),*,key=None)
bisect.insort(a,x,lo=0,hi=len(a),*,key=None)

類似insort_left()，但插入的位置會在所有a 當中的x 的後面（右邊）。

此函式先使用bisect_right() 搜尋插入位置，接著用insert() 於a 以將x 插入，並維持添加元素後的順序。

此函式只有在搜尋時會使用key 函式，插入時不會。

注意雖然搜尋是O(logn)，但插入是O(n)，因此此函式整體時間複雜度是O(n)。

在 3.10 版的變更:新增key 參數。

效能考量

若在需要關注寫入時間的程式當中使用bisect() 和insort()，請特別注意幾個事項：

  • 二分法在一段範圍的數值中做搜尋的效率較佳，但若是要存取特定數值，使用字典的表現還是比較好。

  • insort() 函式的複雜度為O(n)，因為對數搜尋是以線性時間的插入步驟所主導 (dominate)。

  • 搜尋函式為無狀態的 (stateless)，且鍵函式會在使用過後被丟棄。因此，如果搜尋函式被使用於迴圈當中，鍵函式會不斷被重複呼叫於相同的 list 元素。如果鍵函式執行速度不快，請考慮將其以functools.cache() 包裝起來以減少重複的計算。另外，也可以透過搜尋預先計算好的鍵列表 (array of precomputed keys) 來定位插入點（如下方範例所示）。

也參考

  • 有序容器 (Sorted Collections) 是一個使用bisect 來管理資料之有序集合的高效能模組。

  • SortedCollection recipe 使用二分法來建立一個功能完整的集合類別 (collection class) 並帶有符合直覺的搜尋方法 (search methods) 與支援鍵函式。鍵會預先被計算好，以減少搜尋過程中多餘的鍵函式呼叫。

搜尋一個已排序的 list

上面的bisect functions 在找到數值插入點上很有用，但一般的數值搜尋任務上就不是那麼的方便。以下的五個函式展示了如何將其轉換成標準的有序列表查找函式：

defindex(a,x):'Locate the leftmost value exactly equal to x'i=bisect_left(a,x)ifi!=len(a)anda[i]==x:returniraiseValueErrordeffind_lt(a,x):'Find rightmost value less than x'i=bisect_left(a,x)ifi:returna[i-1]raiseValueErrordeffind_le(a,x):'Find rightmost value less than or equal to x'i=bisect_right(a,x)ifi:returna[i-1]raiseValueErrordeffind_gt(a,x):'Find leftmost value greater than x'i=bisect_right(a,x)ifi!=len(a):returna[i]raiseValueErrordeffind_ge(a,x):'Find leftmost item greater than or equal to x'i=bisect_left(a,x)ifi!=len(a):returna[i]raiseValueError

範例

bisect() 函式可用於數值表中的查找 (numeric table lookup)，這個範例使用bisect() 以基於一組有序的數值分界點來為一個考試成績找到相對應的字母等級：90 以上是 'A'、80 到 89 為 'B'，依此類推：

>>>defgrade(score,breakpoints=[60,70,80,90],grades='FDCBA'):...i=bisect(breakpoints,score)...returngrades[i]...>>>[grade(score)forscorein[33,99,77,70,89,90,100]]['F', 'A', 'C', 'C', 'B', 'A', 'A']

bisect() 與insort() 函式也適用於內容為 tuples（元組）的 lists，key 引數可被用以取出在數值表中作為排序依據的欄位：

>>>fromcollectionsimportnamedtuple>>>fromoperatorimportattrgetter>>>frombisectimportbisect,insort>>>frompprintimportpprint>>>Movie=namedtuple('Movie',('name','released','director'))>>>movies=[...Movie('Jaws',1975,'Spielberg'),...Movie('Titanic',1997,'Cameron'),...Movie('The Birds',1963,'Hitchcock'),...Movie('Aliens',1986,'Cameron')...]>>># Find the first movie released after 1960>>>by_year=attrgetter('released')>>>movies.sort(key=by_year)>>>movies[bisect(movies,1960,key=by_year)]Movie(name='The Birds', released=1963, director='Hitchcock')>>># Insert a movie while maintaining sort order>>>romance=Movie('Love Story',1970,'Hiller')>>>insort(movies,romance,key=by_year)>>>pprint(movies)[Movie(name='The Birds', released=1963, director='Hitchcock'), Movie(name='Love Story', released=1970, director='Hiller'), Movie(name='Jaws', released=1975, director='Spielberg'), Movie(name='Aliens', released=1986, director='Cameron'), Movie(name='Titanic', released=1997, director='Cameron')]

如果鍵函式會消耗較多運算資源，那可以在預先計算好的鍵列表中搜尋該紀錄的索引值，以減少重複的函式呼叫：

>>>data=[('red',5),('blue',1),('yellow',8),('black',0)]>>>data.sort(key=lambdar:r[1])# Or use operator.itemgetter(1).>>>keys=[r[1]forrindata]# Precompute a list of keys.>>>data[bisect_left(keys,0)]('black', 0)>>>data[bisect_left(keys,1)]('blue', 1)>>>data[bisect_left(keys,5)]('red', 5)>>>data[bisect_left(keys,8)]('yellow', 8)