## 2012年4月2日 星期一

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

Preface :

bisect.bisect_left(axlo=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(axlo=0, hi=len(a))
bisect.bisect(axlo=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(axlo=0, hi=len(a))
Insert x in a in sorted order. This is equivalent to a.insert(bisect.bisect_left(axlohi), 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(axlo=0, hi=len(a))
bisect.insort(axlo=0, hi=len(a))
Similar to insort_left(), but inserting x in a after any existing entries of x.

Searching Sorted Lists :

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 :

>>> 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

### [ Python 文章收集 ] List Comprehensions and Generator Expressions

Source From  Here   Preface   Do you know the difference between the following syntax?  view plain copy to clipboard print ? [x  for ...