bisect 庫

語言: CN / TW / HK

本來是想自己實現但是複雜度太高,偶然搜到 python 中有一個庫 bisect 可以實現真的是太妙了 。

bisect

基本用法,使用起來很方便,其實就是在找可以插入的位置,但是不會真的插入:

import bisect

l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] 
bisect.bisect(l, 55) # returns 7

耗時測試,從結果來看 bisect 的速度最快:

import timeit 
import bisect

print(timeit.timeit('bisect.bisect([1, 4, 9, 16, 25, 36, 49, 64, 81, 100], 55)','import bisect'))  
# 0.2991909169941209
print(timeit.timeit('next(i for i,n in enumerate([1, 4, 9, 16, 25, 36, 49, 64, 81, 100]) if n > 55)'))  
# 0.7511563330190256
print(timeit.timeit('next(([1, 4, 9, 16, 25, 36, 49, 64, 81, 100].index(n) for n in [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] if n > 55))')) 
# 0.6965440830099396

bisect_left 和 bisect_right

另外還有兩種常用方法,bisect_left 和 bisect_right 函式,用入處理將會插入重複數值的情況,返回將會插入的位置。

  • bisect_left(seq, x) x 存在時返回 x 左側的位置
  • bisect_right(seq, x) x 存在時返回 x 右側的位置

舉例:

print(bisect.bisect_left([2,4,7,9],2)) 
# 0
print(bisect.bisect_left([2,4,7,9],3)) 
# 1
print(bisect.bisect_right([2,4,7,9],2)) 
# 1
print(bisect.bisect_right([2,4,7,9],3)) 
# 1

insort

把目標值插入到有序序列中,並能保持有序順序

arr=[2,4,7,9]
bisect.insort(arr,6)
arr # [2, 4, 6, 7, 9]