Python列表和字典

• 前面我們了解了 “大O表示法” 以及對(duì)不同的算法的評(píng)估，下面來(lái)討論下 Python 兩種內(nèi)置數(shù)據(jù)類(lèi)型有關(guān)的各種操作的大O數(shù)量級(jí)：列表 list 和字典dict。
• 這是 Python 中兩種非常重要的數(shù)據(jù)類(lèi)型，后面會(huì)用來(lái)實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)，通過(guò)運(yùn)行試驗(yàn)來(lái)估計(jì)其各種操作運(yùn)行時(shí)間數(shù)量級(jí)。

對(duì)比 list 和 dict 操作如下：

List列表數(shù)據(jù)類(lèi)型常用操作性能：

最常用的是：按索引取值和賦值（v=a[i]，a[i]=v），由于列表的隨機(jī)訪問(wèn)特性，這兩個(gè)操作執(zhí)行時(shí)間與列表大小無(wú)關(guān)，均為O(1)。

另一個(gè)是列表增長(zhǎng)，可以選擇 append() 和 “+”：lst.append(v)，執(zhí)行時(shí)間是O(1)；lst= lst+ [v]，執(zhí)行時(shí)間是O(n+k)，其中 k 是被加的列表長(zhǎng)度，選擇哪個(gè)方法來(lái)操作列表，也決定了程序的性能。

測(cè)試 4 種生成 n 個(gè)整數(shù)列表的方法：

創(chuàng)建一個(gè) Timer 對(duì)象，指定需要反復(fù)運(yùn)行的語(yǔ)句和只需要運(yùn)行一次的"安裝語(yǔ)句"。

然后調(diào)用這個(gè)對(duì)象的 timeit 方法，指定反復(fù)運(yùn)行多少次。

# Timer(stmt="pass", setup="pass")   # 這邊只介紹兩個(gè)參數(shù)
# stmt：statement的縮寫(xiě)，就是要測(cè)試的語(yǔ)句，要執(zhí)行的對(duì)象
# setup：導(dǎo)入被執(zhí)行的對(duì)象（就和run代碼前，需要導(dǎo)入包一個(gè)道理） 在主程序命名空間中  導(dǎo)入
time1 = Timer("test1()", "from __main__ import test1") 
print("concat：{} seconds".format(time1.timeit(1000)))
time2 = Timer("test2()", "from __main__ import test2")
print("append：{} seconds".format(time2.timeit(1000)))
time3 = Timer("test3()", "from __main__ import test3")
print("comprehension：{} seconds".format(time3.timeit(1000)))
time4 = Timer("test4()", "from __main__ import test4")
print("list range：{} seconds".format(time4.timeit(1000))

結(jié)果如下：

可以看到，4種方法運(yùn)行時(shí)間差別挺大的，列表連接（concat）最慢，List range最快，速度相差近 100 倍。append要比 concat 快得多。另外，我們注意到列表推導(dǎo)式速度大約是 append 兩倍的樣子。

總結(jié)列表基本操作的大 O 數(shù)量級(jí)：

我們注意到 pop 這個(gè)操作，pop()是從列表末尾移除元素，時(shí)間復(fù)雜度為O(1)；pop(i)從列表中部移除元素，時(shí)間復(fù)雜度為O(n)。
原因在于 Python 所選擇的實(shí)現(xiàn)方法，從中部移除元素的話，要把移除元素后面的元素，全部向前挪位復(fù)制一遍，這個(gè)看起來(lái)有點(diǎn)笨拙
但這種實(shí)現(xiàn)方法能夠保證列表按索引取值和賦值的操作很快，達(dá)到O(1)。這也算是一種對(duì)常用和不常用操作的折中方案。

list.pop()的計(jì)時(shí)試驗(yàn)，通過(guò)改變列表的大小來(lái)測(cè)試兩個(gè)操作的增長(zhǎng)趨勢(shì)：

import timeit

pop_first = timeit.Timer("x.pop(0)", "from __main__ import x")
pop_end = timeit.Timer("x.pop()", "from __main__ import x")
print("pop(0)          pop()")
y_1 = []
y_2 = []
for i in range(1000000, 10000001, 1000000):
    x = list(range(i))
    p_e = pop_end.timeit(number=1000)
    x = list(range(i))
    p_f = pop_first.timeit(number=1000)
    print("{:.6f}        {:.6f}".format(p_f, p_e))
    y_1.append(p_f)
    y_2.append(p_e)

結(jié)果如下：

將試驗(yàn)結(jié)果可視化，可以看出增長(zhǎng)趨勢(shì)：pop()是平坦的常數(shù)，pop(0)是線性增長(zhǎng)的趨勢(shì)。

字典與列表不同，是根據(jù)鍵值（key）找到數(shù)據(jù)項(xiàng)，而列表是根據(jù)索引（index）。最常用的取值和賦值，其性能均為O(1)。另一個(gè)重要操作contains(in)是判斷字典中是否存在某個(gè)鍵值（key），這個(gè)性能也是O(1)。

做一個(gè)性能測(cè)試試驗(yàn)來(lái)驗(yàn)證 list 中檢索一個(gè)值，以及 dict 中檢索一個(gè)值的用時(shí)對(duì)比，生成包含連續(xù)值的 list 和包含連續(xù)鍵值 key 的
dict，用隨機(jī)數(shù)來(lái)檢驗(yàn)操作符 in 的耗時(shí)。

import timeit
import random

y_1 = []
y_2 = []
print("lst_time         dict_time")
for i in range(10000, 1000001, 25000):
    t = timeit.Timer("random.randrange(%d) in x" % i, "from __main__ import random, x")
    x = list(range(i))
    lst_time = t.timeit(number=1000)
    x = {j: 'k' for j in range(i)}
    dict_time = t.timeit(number=1000)
    print("{:.6f}        {:.6f}".format(lst_time, dict_time))
    y_1.append(lst_time)
    y_2.append(dict_time)

結(jié)果如下：

• 可見(jiàn)字典的執(zhí)行時(shí)間與規(guī)模無(wú)關(guān)，是常數(shù)。
• 而列表的執(zhí)行時(shí)間則會(huì)隨著列表的規(guī)模加大而線性上升。

更多 Python 數(shù)據(jù)類(lèi)型操作復(fù)雜度可以參考官方文檔：
https://wiki.python.org/moin/TimeComplexity

到此這篇關(guān)于Python字典和列表性能之間的比較的文章就介紹到這了,更多相關(guān)Python列表和字典內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！