数据类型

bisect

bisect 使用二分法在一个 "已排序 (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)  # 如果待查找元素在列表中存在，则返回左侧插入位置。
2

>>> bisect.bisect_right(b, 35)  # 如果待查找元素在列表中存在，则返回右侧插入位置。
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 实现一个 SortedList 非常简单。

>>> 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 来实现 Consistent Hashing 算法，只要找到 Key 在 Ring 上的插入位置，其下一个有效元素就是我们的目标服务器配置。

heapq

最小堆: 完全平衡二叉树，所有节点都小于其子节点。

堆的意义：最快找到最大/最小值。在堆结构中插入或删除最小(最大)元素时进行重新构造时间复杂度为 O(logN)，而其他方法最少为O(N)。堆在实际开发中的更倾向于算法调度而非排序。比如优先级调度时，每次取优先级最高的；时间驱动调度时，取时间最小或等待最长的等等。

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

>>> rand = sample(xrange(1000), 10)    # 生成随机数序列。
>>> rand
[572, 758, 737, 738, 412, 755, 507, 734, 479, 374]

>>> heap = []
>>> for x in rand: heappush(heap, x)    # 将随机数压入堆。
>>> heap        # 堆是树，并非排序列表。
[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

其他相关函数。

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

>>> heapify(d)    # 将列表转换为堆。
>>> 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 个元素。
[9, 8, 7, 6, 5]

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

利用元组 cmp，用数字表示对象优先级，实现优先级队列。

>>> 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 操作符。