前言

相信大家對于Python的列表和元組兩種數據結構并不陌生了，如果我問大家這兩種數據結構有什么區別呢？列表和元組都是數組，列表是動態的數組可以修改，元組是靜態的數組不可修改。除此之外，大家還能想到其他的區別嗎？接下來就讓我來詳細給大家介紹一下吧。

列表中高效搜索算法

存儲結構

為了更好的了解列表，先來看看列表存儲結構，列表其實也就是數組。當我們創建列表時，系統就需要給這個列表分配一塊存儲空間用來存放地址，地址指向的就是列表中存放的數據。

需要注意的是，如果給列表分配了8塊存儲空間，那么實際上列表能用的空間只有7，第一塊空間是用來存放列表的長度。

查詢任意指定的元素時，只需要知道列表存儲的起始位置和元素存儲的位置(這里的位置不是指地址，而是指元素相對于起始地址的偏移量)，就可以很快到查詢到。因為每塊存儲空間占用的大小(存儲地址)都是一樣的，占用一個整形大小的空間用來指向列表中存放的數據，所以在查詢元素的時候與列表中存放的數據類型無關。

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

列表查詢

在介紹列表的存儲結構的時候，已經知道了如果指定列表存儲的起始位置，當需要查詢指定位置元素時的時間復雜度為O(1)。那如果是已知元素的值，查詢元素的位置，此時的時間復雜度又是多少呢？如果大家對這段話不是很理解，下面舉例說明一下。

例如：有一個列表a為[5,3,7,8,2,1,4]，此時如果想要獲取a[2]的元素值時的時間復雜度為O(1)，此時查詢元素值與列表的大小無關。當我們想知道4是否在列表中，最簡單的方法就是遍歷數組中的每一個元素與我們尋找的元素一一比對是否相等，這種方法最差的時間復雜度為O(n)，也就是沒有找到符合位置的元素或者元素在列表的最后一個位置，Python內置的list.index()方法正是采用的這種算法。

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

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

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

import bisect,random
random_list = []
for i in range(10):
    #產生一個隨機數
    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模塊查詢元素的位置

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)
    #尋找元素大于列表中最大值,返回列表的長度
    if i == len(insert_list):
        return i - 1
    #尋找元素剛好等于列表中的這個元素
    elif insert_list[i] == find_value:
        return i
    #尋找的元素在列表中某兩個值之間
    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):
    #產生一個隨機數
    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

列表和元組的區別

在前面也簡單介紹過了列表和元組的一些區別，這里我們做個總結：

① 列表是動態數組，列表的長度可變，內容可修改

② 元組是靜態數組，長度不可變，內容不可修改

③ 元組緩存在Python的運行時環境，所以在使用元組的時候不需要去通過系統的內核來分配內存

所以，對于不會改變的數據，建議使用元組進行存儲，這樣在讀取數據的時候能夠高效。而對于需要改變的數據，則選擇列表進行存儲。需要注意的是，列表和元組都可以存儲不同的數據類型，即保存數據的時候允許混合類型，但是這樣操作的壞處就是會帶來一些額外的開銷。

列表

前面也介紹過了，列表屬于動態數組，所以列表的大小是可變的，當創建一個大小為N的列表時，此時列表的大小為N，那么如果我使用append方法添加一個元素時，此時列表的大小是N+1嗎？

當然不是，實際上，當第一次使用append方法時，Python會先創建一個列表，用來存放之前的N個元素以及額外添加的元素。而分配給這個列表的大小不是N+1，而是M(M>N)，這樣做的主要目的是為了便于以后使用append的方法添加元素時，不需要頻繁的去創建列表和復制數據。

列表的超額分配發生在第一次往列表中添加元素，創建列表時，是按照所需要的大小創建的，不存在超額分配。

列表的超額分配公式：

注意：并不是每一次append的時候都會導致超額分配，第一次添加數據的時候會發生超額分配，后面再添加數據的時候，只有當N==M的時候，即列表的空間已經滿了沒法存儲更多的數據時，才會發生超額分配。雖然說，列表超額分配的空間并不是很多，但是如果列表的數量很多時，超額分配的空間還是不容小視的。

元組

元組是靜態數組，所以當元組被創建之后其長度和內容都無法修改。雖然說，無法修改元組，但是我們可以將兩個元組拼接成一個新的元組，而且不需要為新的元組分配任何額外的空間。這個操作類似于列表的append操作，唯一的區別在于當列表的內存耗盡的時候，再使用append時會開辟一些額外的內存空間，會導致部分空間的浪費。而元組是直接將兩個元組相加再返回一個新的元組，這一過程不會產生額外的內存空間。

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

除此之外，元組還有一個好處在于，資源緩存。Python也是一門垃圾收集語言，當某些變量我們不再使用的時候，系統就會自動回收釋放內存，以便其他程序或變量使用。對于長度為1-20的元組而言，即使不再使用，也不會馬上釋放內存，而是留給以后使用。當需要創建新的元組的時候，就可以直接使用這塊內存，而不需要再去向系統申請內存。

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

編輯：hfy