记录博客 ZH-BLOG

Python 用bisect管理已排序的序列

时间:2018-07-31 23:13:46分类:python

bisect 模块包含两个主要函数, bisect 和 insort, 两个函数都利用二分查找算法来在有序序列中查找或插入元素。

bisect(haystack, needle) 在 haystack 里搜索 needle 的位置, 该位置满足的条件是, 把 needle 插入这个位置之后, haystack 还能保持升序。 也就是在说这个函数返回的位置前面的值, 都小于或等于 needle 的值(当等于时,默认位置为右边)。 其中 haystack 必须是一个有序的序列。 你可以先用 bisect(haystack, needle) 查找位置 index, 再用 haystack.insert(index, needle) 来插入新值。 但你也可用 insort 来一步到位, 并且后者的速度更快一些。

import bisect,sys

HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]
NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 30, 31]

ROW_FMT='{0:2d} @ {1:2d}    {2}{0:<2d}'

def demo(bisect_fn):
    for needle in reversed(NEEDLES):
        position=bisect_fn(HAYSTACK,needle)
        offset='  |'*position
        print(ROW_FMT.format(needle,position,offset))

if __name__=='__main__':
    if sys.argv[-1]=='left':
        bisect_fn=bisect.bisect_left
    else:
        bisect_fn=bisect.bisect
    print('DEMO:',bisect_fn.__name__)
    print('haystack ->',' '.join('%2d' % n for n in HAYSTACK))
    demo(bisect_fn)

bisect 根据位置索引获取对应的值:

import bisect

# 有序序列中作为 index 的替代, 用
# 来更快地查找一个元素的位置。

# 如果成绩 score<=60F; 60<score<=70D; 70<score<=80C; 80<score<=90B; 90<scoreA;
def grade(score,breakpoint=[60,70,80,90],grades='FDCBA'):
index=bisect.bisect(breakpoint,score)
return grades[index]

gs=[grade(i) for i in [33,67,99,82,40,60]]
print(gs)

用 bisect.insort 插入新元素

>>> import bisect
>>> size = 7
>>> my_list = []
>>> for i in range(size):
	new_item = random.randrange(size * 2)
	bisect.insort(my_list, new_item)
	print('{:2d} ->'.format(new_item), my_list)

	
 7 -> [7]
 8 -> [7, 8]
 4 -> [4, 7, 8]
 8 -> [4, 7, 8, 8]
 2 -> [2, 4, 7, 8, 8]
 7 -> [2, 4, 7, 7, 8, 8]
 8 -> [2, 4, 7, 7, 8, 8, 8]

insort 跟 bisect 一样,都有 left 和 right 两个方法,默认都是 right。