[Python Std Library] Data Types : bisect — Array bisection algorithm

翻譯自 這裡
Preface :
這個模組提供 basic bisection algorithm 來維護一個 Ordered list, 每次插入 element 後都不必重新 sorting 以減少 comparison 的 effort. 先來看看這個模組上提供的方法 :
- bisect.bisect_left(a, x, lo=0, hi=len(a))

Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.

The returned insertion point i partitions the array a into two halves so that all(val < x for val in a[lo:i]) for the left side and all(val >= x for val in a[i:hi]) for the right side. Check example :
>>> h = [1, 2, 4, 6, 7, 7, 8, 9]
>>> bisect_left(h, 7)
4
>>> h[0:4]
[1, 2, 4, 6]
>>> h[4:]
[7, 7, 8, 9]

- bisect.bisect_right(a, x, lo=0, hi=len(a))
- bisect.bisect(a, x, lo=0, hi=len(a))

Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.
>>> h = [1, 2, 4, 6, 7, 7, 8, 9]
>>> bisect(h, 7)
6
>>> h[0:6] # 在位置 6 以前的值會小於等於 7
[1, 2, 4, 6, 7, 7]
>>> h[6:] # 在位置 6 (含) 以後的位置大於 7
[8, 9]

- bisect.insort_left(a, x, lo=0, hi=len(a))

Insert x in a in sorted order. This is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x) assuming that a is already sorted. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.
>>> h = [1, 2, 4, 6, 7, 7, 8, 9]
>>> insort_left(h, 6)
>>> h
[1, 2, 4, 6, 6, 7, 7, 8, 9]
>>> insort_left(h, 6, lo=6) # 從位置 6 到 len(h) 中進行插入.
>>> h
[1, 2, 4, 6, 6, 7, 6, 7, 8, 9]

- bisect.insort_right(a, x, lo=0, hi=len(a))
- bisect.insort(a, x, lo=0, hi=len(a))

Similar to insort_left(), but inserting x in a after any existing entries of x.

Searching Sorted Lists :
透過下面的函數包裝, 讓你輕鬆從 sorted list 進行搜尋 :

view plaincopy to clipboardprint?

1. def index(a, x):  
2.     'Locate the leftmost value exactly equal to x'  
3.     i = bisect_left(a, x)  
4.     if i != len(a) and a[i] == x:  
5.         return i  
6.     raise ValueError  
7.   
8. def find_lt(a, x):  
9.     'Find rightmost value less than x'  
10.     i = bisect_left(a, x)  
11.     if i:  
12.         return a[i-1]  
13.     raise ValueError  
14.   
15. def find_le(a, x):  
16.     'Find rightmost value less than or equal to x'  
17.     i = bisect_right(a, x)  
18.     if i:  
19.         return a[i-1]  
20.     raise ValueError  
21.   
22. def find_gt(a, x):  
23.     'Find leftmost value greater than x'  
24.     i = bisect_right(a, x)  
25.     if i != len(a):  
26.         return a[i]  
27.     raise ValueError  
28.   
29. def find_ge(a, x):  
30.     'Find leftmost item greater than or equal to x'  
31.     i = bisect_left(a, x)  
32.     if i != len(a):  
33.         return a[i]  
34.     raise ValueError  

使用範例如下 :

>>> d = [1, 2, 3, 4, 4, 6, 7, 9]
>>> index(d, 5)
Traceback (most recent call last):
File "", line 1, in
File "bisect_ser.py", line 8, in index
raise ValueError
ValueError
>>> index(d, 4) # 如果有數字4, 傳回最左邊位置 
3
>>> find_le(d, 6) # 小於等於 6
6
>>> find_lt(d, 6) # 小於 6
4
>>> find_gt(d, 6) # 大於 6
7
>>> find_ge(d, 6) # 大於等於 6
6

Other Examples :
考慮我們要為成績分等 : 60 以下為 F ; 60~69為D ; 70~79為C ; 80~89為B ; 90~100為A. 透過模組 bisect 便可以很輕鬆辦到. 透過函數 bisect() 來對 [60, 70, 80, 90] 進行 indexing ; 可以知道小於 60 會得到 0 ; 60~69會得到1 ; 70~79會得到2 以此類推. 因此我們可以透過返回的 index 取出 'FDCBA' 對應位置的字元便可以達成 :


另外再使用函數 sorted() 與 bisect() 上的差別是 bisect() 並沒有所謂的 reverse 的功能且使用上是在參數已經是 ordered 條件下才有意義. 因此在使用上彼此是相輔相成, 來看看下面的範例 :

>>> from bisect import *
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1]) # 使用 tuple 的數字對 data 進行 sorting
>>> data
[('black', 0), ('blue', 1), ('red', 5), ('yellow', 8)]
>>> keys = [r[1] for r in data] # 取出 data 中的 sorted 數字
>>> keys
[0, 1, 5, 8]
>>> data[bisect_left(keys, 0)] # 取出數字 0 的位置, 並利用該位置取出 data 數字是 0 的 tuple
('black', 0)
>>> data[bisect_left(keys, 2)] # 取出大於等於 2 的位置, 再以該位置取出 data 中的 tuple
('red', 5)

This message was edited 14 times. Last update was at 03/04/2012 09:24:08