bisect

bisect 使用二分法在一個(gè) "已排序 (sorted) 序列" 中查找合適的插入位置。

>>> import bisect

>>> b = [ 20, 34, 35, 65, 78 ]

>>> bisect.bisect(b, 25)  # 查找 25 在列表中的合適插入位置。
1

>>> bisect.bisect(b, 40)  # 查找 40 在列表中的合適插入位置。
3

>>> bisect.bisect_left(b, 35)  # 如果待查找元素在列表中存在，則返回左側(cè)插入位置。
2

>>> bisect.bisect_right(b, 35)  # 如果待查找元素在列表中存在，則返回右側(cè)插入位置。
3

還可以直接用 insort_left() 直接插入元素而非查找。

>>> bisect.insort_left(b, 25)

>>> b
[20, 25, 34, 35, 65, 78]

>>> bisect.insort_left(b, 40)

>>> b
[20, 25, 34, 35, 40, 65, 78]

用 bisect 實(shí)現(xiàn)一個(gè) SortedList 非常簡(jiǎn)單。

>>> def SortedList(list, *elements):
...     for e in elements:
...         bisect.insort_right(list, e)
...
...     return list

>>> SortedList([], 3, 7, 4, 1)
[1, 3, 4, 7]

>>> o = SortedList([], 3, 7, 4, 1)

>>> o
[1, 3, 4, 7]

>>> SortedList(o, 8, 2, 6, 0)
[0, 1, 2, 3, 4, 6, 7, 8]

可以考慮用 bisect 來(lái)實(shí)現(xiàn) Consistent Hashing 算法，只要找到 Key 在 Ring 上的插入位置，其下一個(gè)有效元素就是我們的目標(biāo)服務(wù)器配置。

heapq

最小堆: 完全平衡二叉樹(shù)，所有節(jié)點(diǎn)都小于其子節(jié)點(diǎn)。

堆的意義：最快找到最大/最小值。在堆結(jié)構(gòu)中插入或刪除最小(最大)元素時(shí)進(jìn)行重新構(gòu)造時(shí)間復(fù)雜度為 O(logN)，而其他方法最少為O(N)。堆在實(shí)際開(kāi)發(fā)中的更傾向于算法調(diào)度而非排序。比如優(yōu)先級(jí)調(diào)度時(shí)，每次取優(yōu)先級(jí)最高的；時(shí)間驅(qū)動(dòng)調(diào)度時(shí)，取時(shí)間最小或等待最長(zhǎng)的等等。

>>> from heapq import *
>>> from random import *

>>> rand = sample(xrange(1000), 10)    # 生成隨機(jī)數(shù)序列。
>>> rand
[572, 758, 737, 738, 412, 755, 507, 734, 479, 374]

>>> heap = []
>>> for x in rand: heappush(heap, x)    # 將隨機(jī)數(shù)壓入堆。
>>> heap        # 堆是樹(shù)，并非排序列表。
[374, 412, 507, 572, 479, 755, 737, 758, 734, 738]

>>> while heap: print heappop(heap)    # 總是彈出最小元素。
374
412
479
507
572
734
737
738
755
758

其他相關(guān)函數(shù)。

>>> d = sample(xrange(10), 10)
>>> d
[9, 7, 3, 4, 0, 2, 5, 1, 8, 6]

>>> heapify(d)    # 將列表轉(zhuǎn)換為堆。
>>> d
[0, 1, 2, 4, 6, 3, 5, 9, 8, 7]

>>> heappushpop(d, -1)    # 先 push(item)，后 pop。彈出值肯定小于或等于 item。
-1

>>> heapreplace(d, -1)    # 先 pop，后 push(item)。彈出值可能大于 item。
0

... ...

>>> a = range(1, 10, 2)
>>> b = range(2, 10, 2)
>>> [x for x in merge(a, b)]   # 合并有序序列。
[1, 2, 3, 4, 5, 6, 7, 8, 9]

... ...

>>> d = sample(range(10), 10)
>>> d
[9, 0, 3, 4, 5, 6, 1, 2, 8, 7]

>>> nlargest(5, list)    # 從列表(不一定是堆)有序返回最大的 n 個(gè)元素。
[9, 8, 7, 6, 5]

>>> nsmallest(5, list)    # 有序返回最小的 n 個(gè)元素。
[0, 1, 2, 3, 4]

利用元組 cmp，用數(shù)字表示對(duì)象優(yōu)先級(jí)，實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列。

>>> from string import *

>>> data = map(None, sample(xrange(100), 10), sample(letters, 10))
>>> data
[(31, 'Z'),
(71, 'S'),
(94, 'r'),
(65, 's'),
(98, 'B'),
(10, 'U'),
(8, 'u'),
(25, 'p'),
(11, 'v'),
(29, 'i')]

>>> for item in data: heappush(heap, item)
>>> heap
[(8, 'u'),
(11, 'v'),
(10, 'U'),
(25, 'p'),
(29, 'i'),
(94, 'r'),
(31, 'Z'),
(71, 'S'),
(65, 's'),
(98, 'B')]

>>> while heap: print heappop(heap)
(8, 'u')
(10, 'U')
(11, 'v')
(25, 'p')
(29, 'i')
(31, 'Z')
(65, 's')
(71, 'S')
(94, 'r')
(98, 'B')

或者重載自定義類型的 cmp 操作符。