前言

相信大家對(duì)于Python的列表和元組兩種數(shù)據(jù)結(jié)構(gòu)并不陌生了，如果我問(wèn)大家這兩種數(shù)據(jù)結(jié)構(gòu)有什么區(qū)別呢？列表和元組都是數(shù)組，列表是動(dòng)態(tài)的數(shù)組可以修改，元組是靜態(tài)的數(shù)組不可修改。除此之外，大家還能想到其他的區(qū)別嗎？接下來(lái)就讓我來(lái)詳細(xì)給大家介紹一下吧。

列表中高效搜索算法

存儲(chǔ)結(jié)構(gòu)

為了更好的了解列表，先來(lái)看看列表存儲(chǔ)結(jié)構(gòu)，列表其實(shí)也就是數(shù)組。當(dāng)我們創(chuàng)建列表時(shí)，系統(tǒng)就需要給這個(gè)列表分配一塊存儲(chǔ)空間用來(lái)存放地址，地址指向的就是列表中存放的數(shù)據(jù)。

需要注意的是，如果給列表分配了8塊存儲(chǔ)空間，那么實(shí)際上列表能用的空間只有7，第一塊空間是用來(lái)存放列表的長(zhǎng)度。

查詢(xún)?nèi)我庵付ǖ脑貢r(shí)，只需要知道列表存儲(chǔ)的起始位置和元素存儲(chǔ)的位置(這里的位置不是指地址，而是指元素相對(duì)于起始地址的偏移量)，就可以很快到查詢(xún)到。因?yàn)槊繅K存儲(chǔ)空間占用的大小(存儲(chǔ)地址)都是一樣的，占用一個(gè)整形大小的空間用來(lái)指向列表中存放的數(shù)據(jù)，所以在查詢(xún)?cè)氐臅r(shí)候與列表中存放的數(shù)據(jù)類(lèi)型無(wú)關(guān)。

例如：列表的起始位置是M，我們想要列表中的第k個(gè)元素，這時(shí)候只需要將指針移到M+k的位置，然后再讀取數(shù)據(jù)就好了。也就是說(shuō)，只要數(shù)據(jù)保存在一個(gè)連續(xù)的存儲(chǔ)空間中時(shí)，查詢(xún)指定位置元素的時(shí)間復(fù)雜度為O(1)。

列表查詢(xún)

在介紹列表的存儲(chǔ)結(jié)構(gòu)的時(shí)候，已經(jīng)知道了如果指定列表存儲(chǔ)的起始位置，當(dāng)需要查詢(xún)指定位置元素時(shí)的時(shí)間復(fù)雜度為O(1)。那如果是已知元素的值，查詢(xún)?cè)氐奈恢茫藭r(shí)的時(shí)間復(fù)雜度又是多少呢？如果大家對(duì)這段話(huà)不是很理解，下面舉例說(shuō)明一下。

例如：有一個(gè)列表a為[5,3,7,8,2,1,4]，此時(shí)如果想要獲取a[2]的元素值時(shí)的時(shí)間復(fù)雜度為O(1)，此時(shí)查詢(xún)?cè)刂蹬c列表的大小無(wú)關(guān)。當(dāng)我們想知道4是否在列表中，最簡(jiǎn)單的方法就是遍歷數(shù)組中的每一個(gè)元素與我們尋找的元素一一比對(duì)是否相等，這種方法最差的時(shí)間復(fù)雜度為O(n)，也就是沒(méi)有找到符合位置的元素或者元素在列表的最后一個(gè)位置，Python內(nèi)置的list.index()方法正是采用的這種算法。

面對(duì)這種情況，如果想要進(jìn)一步提升算法的查詢(xún)速度，有兩種算法可以解決。第一種，更改數(shù)據(jù)結(jié)構(gòu)，將列表改為字典，然后通過(guò)字典的鍵來(lái)獲取值，此時(shí)也能夠得到O(1)的時(shí)間復(fù)雜度，但是轉(zhuǎn)換過(guò)程需要加入計(jì)算量，，而且字典的鍵不能重復(fù)。第二種方式就是，先對(duì)列表進(jìn)行排序，然后再通過(guò)二分法查找元素是否存在列表中只需要O(log(n))的時(shí)間復(fù)雜度，但是排序還是需要引入一些計(jì)算量，這種先排序后查找算法在某些時(shí)候是最優(yōu)的，當(dāng)列表比較大的時(shí)候。

Python提供了一個(gè)bisect模塊，可以保證你在向列表中插入元素的時(shí)候保持排序的同時(shí)添加元素，還提供了一個(gè)高度優(yōu)化過(guò)的二分查找算法，這就是Python的強(qiáng)大之處，第三方庫(kù)非常豐富，免去了重復(fù)造輪子的麻煩。bisect模塊提供的函數(shù)，可以將添加的新元素插入在列表正確的位置上，使得列表始終滿(mǎn)足排序，以便我們能夠很快的找到元素的位置。

使用bisect模塊向列表中插入元素

import bisect,random
random_list = []
for i in range(10):
    #產(chǎn)生一個(gè)隨機(jī)數(shù)
    random_value = random.randint(0,100)
    #使用bisect模塊向列表中插入元素，并且保持列表排序
    bisect.insort(random_list,random_value)
print(random_list)
#[3, 3, 5, 51, 53, 67, 68, 90, 94, 95]

使用bisect模塊查詢(xún)?cè)氐奈恢?/p>

import bisect,random

def find_list_index(insert_list,find_value):
    """尋找列表中與find_value最接近元素的位置
    :param insert_list: 列表(由小到大排序)
    :param find_value: 尋找的元素
    :return: 列表中與尋找元素最接近的位置
    """
    #bisect_left方法返回，列表中大于或等于該元素的位置
    i = bisect.bisect_left(insert_list,find_value)
    #尋找元素大于列表中最大值,返回列表的長(zhǎng)度
    if i == len(insert_list):
        return i - 1
    #尋找元素剛好等于列表中的這個(gè)元素
    elif insert_list[i] == find_value:
        return i
    #尋找的元素在列表中某兩個(gè)值之間
    elif i > 0:
        j = i - 1
        #返回列表中與尋找元素大小最接近的位置
        if insert_list[i] - find_value > find_value - insert_list[j]:
            return j
    return i

random_list = []
for i in range(10):
    #產(chǎn)生一個(gè)隨機(jī)數(shù)
    random_value = random.randint(0,100)
    #使用bisect模塊向列表中插入元素，并且保持列表排序
    bisect.insort(random_list,random_value)

print(random_list)
#[0, 1, 2, 13, 35, 37, 51, 64, 72, 86]
#查找與50最接近元素的位置
print(find_list_index(random_list,50))
#6

列表和元組的區(qū)別

在前面也簡(jiǎn)單介紹過(guò)了列表和元組的一些區(qū)別，這里我們做個(gè)總結(jié)：

① 列表是動(dòng)態(tài)數(shù)組，列表的長(zhǎng)度可變，內(nèi)容可修改

② 元組是靜態(tài)數(shù)組，長(zhǎng)度不可變，內(nèi)容不可修改

③ 元組緩存在Python的運(yùn)行時(shí)環(huán)境，所以在使用元組的時(shí)候不需要去通過(guò)系統(tǒng)的內(nèi)核來(lái)分配內(nèi)存

所以，對(duì)于不會(huì)改變的數(shù)據(jù)，建議使用元組進(jìn)行存儲(chǔ)，這樣在讀取數(shù)據(jù)的時(shí)候能夠高效。而對(duì)于需要改變的數(shù)據(jù)，則選擇列表進(jìn)行存儲(chǔ)。需要注意的是，列表和元組都可以存儲(chǔ)不同的數(shù)據(jù)類(lèi)型，即保存數(shù)據(jù)的時(shí)候允許混合類(lèi)型，但是這樣操作的壞處就是會(huì)帶來(lái)一些額外的開(kāi)銷(xiāo)。

列表

前面也介紹過(guò)了，列表屬于動(dòng)態(tài)數(shù)組，所以列表的大小是可變的，當(dāng)創(chuàng)建一個(gè)大小為N的列表時(shí)，此時(shí)列表的大小為N，那么如果我使用append方法添加一個(gè)元素時(shí)，此時(shí)列表的大小是N+1嗎？

當(dāng)然不是，實(shí)際上，當(dāng)?shù)谝淮问褂胊ppend方法時(shí)，Python會(huì)先創(chuàng)建一個(gè)列表，用來(lái)存放之前的N個(gè)元素以及額外添加的元素。而分配給這個(gè)列表的大小不是N+1，而是M(M>N)，這樣做的主要目的是為了便于以后使用append的方法添加元素時(shí)，不需要頻繁的去創(chuàng)建列表和復(fù)制數(shù)據(jù)。

列表的超額分配發(fā)生在第一次往列表中添加元素，創(chuàng)建列表時(shí)，是按照所需要的大小創(chuàng)建的，不存在超額分配。

列表的超額分配公式：

注意：并不是每一次append的時(shí)候都會(huì)導(dǎo)致超額分配，第一次添加數(shù)據(jù)的時(shí)候會(huì)發(fā)生超額分配，后面再添加數(shù)據(jù)的時(shí)候，只有當(dāng)N==M的時(shí)候，即列表的空間已經(jīng)滿(mǎn)了沒(méi)法存儲(chǔ)更多的數(shù)據(jù)時(shí)，才會(huì)發(fā)生超額分配。雖然說(shuō)，列表超額分配的空間并不是很多，但是如果列表的數(shù)量很多時(shí)，超額分配的空間還是不容小視的。

元組

元組是靜態(tài)數(shù)組，所以當(dāng)元組被創(chuàng)建之后其長(zhǎng)度和內(nèi)容都無(wú)法修改。雖然說(shuō)，無(wú)法修改元組，但是我們可以將兩個(gè)元組拼接成一個(gè)新的元組，而且不需要為新的元組分配任何額外的空間。這個(gè)操作類(lèi)似于列表的append操作，唯一的區(qū)別在于當(dāng)列表的內(nèi)存耗盡的時(shí)候，再使用append時(shí)會(huì)開(kāi)辟一些額外的內(nèi)存空間，會(huì)導(dǎo)致部分空間的浪費(fèi)。而元組是直接將兩個(gè)元組相加再返回一個(gè)新的元組，這一過(guò)程不會(huì)產(chǎn)生額外的內(nèi)存空間。

主要注意的是，在使用列表和元組保存同樣的數(shù)據(jù)時(shí)，即使列表沒(méi)用使用append操作，列表所需要的內(nèi)存仍然是大于元組的，這是為了使得讓列表能夠記住更多自身的一些信息以便它們能夠進(jìn)行高效的resize。

除此之外，元組還有一個(gè)好處在于，資源緩存。Python也是一門(mén)垃圾收集語(yǔ)言，當(dāng)某些變量我們不再使用的時(shí)候，系統(tǒng)就會(huì)自動(dòng)回收釋放內(nèi)存，以便其他程序或變量使用。對(duì)于長(zhǎng)度為1-20的元組而言，即使不再使用，也不會(huì)馬上釋放內(nèi)存，而是留給以后使用。當(dāng)需要?jiǎng)?chuàng)建新的元組的時(shí)候，就可以直接使用這塊內(nèi)存，而不需要再去向系統(tǒng)申請(qǐng)內(nèi)存。

總結(jié)：要想高效的尋找列表中的某一個(gè)元素是否存在時(shí)，可以讓列表進(jìn)行排序，然后再去查找。對(duì)于不會(huì)改變的數(shù)據(jù)，建議使用元組進(jìn)行保存，如果需要頻繁修改數(shù)據(jù)還是使用列表。

編輯：hfy