[[402075]]

前言

bisect實(shí)現(xiàn)了一個(gè)算法來向列表中插入元素，同時(shí)仍保持列表有序。

本篇，將詳細(xì)介紹bisect庫高效率的玩轉(zhuǎn)列表。

有序插入

首先，我們來看看bisect庫是如何實(shí)現(xiàn)列表的插入的。具體代碼如下所示：

import bisect 
 
a = [7, 5, 4, 1, 9, 8, 2, 3, 6, 0, 5] 
print(a) 
new_a = [] 
for i in a: 
    position = bisect.bisect(new_a, i) 
    bisect.insort(new_a, i) 
    print(position, new_a) 

 運(yùn)行之后，效果如下：

可以看到，bisect會(huì)自動(dòng)排序進(jìn)行插入，position為插入的索引位置。當(dāng)然，對(duì)于此類插入如果直接構(gòu)建列表，然后排序，可能速度更快。不過這只僅僅對(duì)于短列表而言非常的快，對(duì)于非常長的列表而言，使用上面這種插入排序方式可以大大節(jié)省時(shí)間和內(nèi)存，尤其是比較兩個(gè)列表成員的操作需要開銷很大的計(jì)算量時(shí)。

重復(fù)值處理

在實(shí)際的列表處理中，我們可能處理重復(fù)的值。如前文所示，多余的5是默認(rèn)插入到重復(fù)值右邊的，也就是說相當(dāng)于使用insort_right()函數(shù)。同理，那么左邊我們就可以用insort_left()函數(shù)。

import bisect 
 
a = [7, 5, 4, 1, 9, 8, 2, 3, 6, 0, 5] 
print(a) 
new_a = [] 
for i in a: 
    position = bisect.bisect_left(new_a, i) 
    bisect.insort_left(new_a, i) 
    print(position, new_a) 

 運(yùn)行之后，效果如下：

讀者可以對(duì)比一下上面兩個(gè)圖片，最后一行的索引變化?？梢钥吹?，一個(gè)是6，一個(gè)是5，因?yàn)槲覀冎鲃?dòng)變更，把重復(fù)值默認(rèn)插入到左邊了。