Python 模組介紹 - bisect
Posted on Feb 7, 2021 in Python 程式設計 - 初階 by Amo Chen ‐ 3 min read
談到插入(insert)元素到已排序串列(list) ,最暴力的方法就是每次插入元素後直接排序:
>>> a = [1, 2, 3, 4]
>>> a.insert(0, 5)
>>> a
[5, 1, 2, 3, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]
不過隨著串列越來越長,每次插入元素後再進行排序的方式,將會越來越慢,甚至造成大量不必要的運算,這時可以利用 Python 內建模組 bisect ,透過二元搜尋的方式幫我們插入元素到串列之中,如此一來該串列就不需要在新增元素後進行排序。
p.s bisect 只能運用在已排序過的串列(list)
本文環境
- Python 3.7
bisect, bisect_left, bisect_right
先前提到 bisect 模組能夠透過二元搜尋的方式,插入元素到串列之中。
在此之前,可以先認識 bisect.bisect_left
函式,該函式可以找出元
素的插入索引位置,例如以下使用 bisect.bisect_left
找出整數 3 在串列 [2, 4, 6]
的插入索引為 1 ,也就是串列的第 2 個位置:
>>> import bisect
>>> a = [2, 4, 6]
>>> bisect.bisect_left(a, 3)
1
接著按照該索引 1 將整數 3 插入至串列 a 後,該串列依然維持已排序的狀態:
>>> a.insert(1, 3)
>>> a
[2, 3, 4, 6]
bisect.bisect_left
還有個特性,當串列中含有重複的元素時,如果想再插入一個相同的元素時,例如在 [2, 2, 4, 4, 6, 6, 8, 8]
中再插入 1 個整數 4 , bisect.bisect_left
所回傳的串列索引位置 2 會確保該位置左邊都小於 <
欲插入的值,而該位置右邊的所有值都大於等於 >=
欲插入的值,也就是 [2, 2, 4, 4, 6, 6, 8, 8]
會被分為 [2, 2]
與 [4, 4, 6, 6, 8, 8]
,而索引位置 2 就在重複元素 4 的左邊,這也就是 bisect.bisect_left
會有 _left
的由來:
>>> import bisect
>>> a = [2, 2, 4, 4, 6, 6, 8, 8]
>>> bisect.bisect_left(a, 4)
2
p.s. bisect.bisect_left
可以想像是當有重複元素時,再插入 1 個相同元素的話,該元素會被排到第 1 個
有 bisect.bisect_left
的話,當然就會有 bisect.bisect_right
,也等同於 bisect.bisect
, bisect.bisect_right
所回傳的串列索引位置 2 會確保該位置左邊都小於等於 <=
欲插入的值,而該位置右邊的所有值都大於 >
欲插入的值,例如在 [2, 2, 4, 4, 6, 6, 8, 8]
中再插入 1 個整數 4 , bisect.bisect_right
所回傳的串列索引位置 4 會將 [2, 2, 4, 4, 6, 6, 8, 8]
分為 [2, 2, 4, 4]
與 [6, 6, 8, 8]
,而索引位置 4 就在重複元素 4 的右邊,這也就是 bisect.bisect_right
會有 _right
的由來
>>> import bisect
>>> a = [2, 2, 4, 4, 6, 6, 8, 8]
>>> bisect.bisect(a, 4)
4
p.s. bisect.bisect_right
可以想像是當有重複元素時,再插入 1 個相同元素的話,該元素會被排到最後
>>> import bisect
>>> a = [2, 2, 4, 4, 6, 6, 8, 8]
>>> bisect.bisect_right(a, 4)
4
insort, insort_right, insort_left
了解 bisect
, bisect_left
, bisect_right
的作用之後, insort
, insort_right
, insort_left
等函式就很好理解了。
insort
, insort_right
, insort_left
會直接插入元素到串列之中:
>>> import bisect
>>> a = [2, 4, 6, 8]
>>> bisect.insort_left(a, 4)
>>> a
[2, 4, 4, 6, 8]
>>> import bisect
>>> a = [2, 4, 6, 8]
>>> bisect.insort_left(a, 4)
>>> a
[2, 4, 4, 6, 8]
額外用途
有些時候可能會寫出類似以下多種 if
的判斷式:
price = 80
if price >= 100:
print('偏貴')
elif price >= 90:
print('合理')
elif price >= 80:
print('便宜')
elif price >= 70:
print('超便宜')
else:
print('不合理')
不過上述形式的程式碼也可以用 bisect 進行改寫:
from bisect import bisect
price_thresholds = [70, 80, 90, 100]
results = ['不合理', '超便宜', '便宜', '合理', '偏貴']
idx = bisect(price_thresholds, 80)
print(results[idx])
以上就是 bisect 模組的介紹。
Happy Coding!
References
https://docs.python.org/3/library/bisect.html