快捷導(dǎo)航

Python列表和集合的效率大比拼

更新時(shí)間：2022年07月20日 15:58:34 作者：Python編程學(xué)習(xí)圈

程序的運(yùn)行效率分為兩種：第一種是時(shí)間效率，第二種是空間效率，這篇文章主要介紹了Python列表和集合的效率對(duì)比,需要的朋友可以參考下

程序運(yùn)行效率

程序的運(yùn)行效率分為兩種：第一種是時(shí)間效率，第二種是空間效率。時(shí)間效率被稱為時(shí)間復(fù)雜度，而空間效率被稱作空間復(fù)雜度。時(shí)間復(fù)雜度主要衡量的是一個(gè)程序的運(yùn)行速度，而空間復(fù)雜度主要衡量一個(gè)程序所需要的額外存儲(chǔ)空間。

一個(gè)程序執(zhí)行所耗費(fèi)的時(shí)間，從理論上說(shuō)，是不能算出來(lái)的，只有你把程序放在機(jī)器上跑起來(lái)，才能知道，不同機(jī)器不同時(shí)間得出的結(jié)果可能不一樣。但是我們需要每個(gè)程序都上機(jī)測(cè)試嗎？顯然不現(xiàn)實(shí)，所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，一般會(huì)使用大O漸進(jìn)表示法，平時(shí)執(zhí)行次數(shù)為1次的我們就可以說(shuō)時(shí)間復(fù)雜度是O(1)，需要n次的就可以說(shuō)時(shí)間復(fù)雜度是O(n)。

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度?？臻g復(fù)雜度不是程序占用了多少個(gè)字節(jié)的空間，因?yàn)檫@個(gè)實(shí)際運(yùn)行過(guò)程中很難計(jì)算，所以空間復(fù)雜度算的是變量的個(gè)數(shù)?？臻g復(fù)雜度計(jì)算規(guī)則基本跟時(shí)間復(fù)雜度類似，也使用大O漸進(jìn)表示法。

Python組合數(shù)據(jù)類型中常用的主要有元組、列表、集合和字典，每種數(shù)據(jù)類型不同操作的時(shí)間復(fù)雜度可以參考Python的官方鏈接，網(wǎng)頁(yè)中有詳細(xì)的說(shuō)明，

https://wiki.python.org/moin/TimeComplexity

元組和列表都屬于序列類型，他們存儲(chǔ)機(jī)制基本一致；集合和字典也是基本相同，唯一的區(qū)別就是集合每個(gè)元素沒(méi)有對(duì)應(yīng)的值。接下來(lái)我們以集合和列表為例看看他們的查找效率和存儲(chǔ)開銷。

數(shù)據(jù)查找效率

關(guān)于集合和列表數(shù)據(jù)查找效率差距到底有多大？先看一組實(shí)例：

import time
import random
nums = [random.randint(0, 2000000) for i in range(1000)]
list_test = list(range(1000000))
set_test = set(list_test)
count_list, count_set = 0, 0
t1 = time.time()  # 測(cè)試在列表中進(jìn)行查找
for num in nums:
   if num in list_test:
       count_list += 1
t2 = time.time()
for num in nums:  # 測(cè)試在集合中進(jìn)行查找
   if num in set_test:
       count_set += 1
t3 = time.time()  # 測(cè)試在集合中進(jìn)行查找
print('找到個(gè)數(shù)，列表：{}，集合：{}'.format(count_list, count_set))
print('使用時(shí)間，列表：{:.4f}s'.format(t2 - t1))
print('使用時(shí)間，集合：{:.4f}s'.format(t3 - t2))

輸出結(jié)果為：

找到個(gè)數(shù)，列表：515，集合：515
使用時(shí)間，列表：7.7953s
使用時(shí)間，集合：0.0010s

從上面例子可以清楚地看出，集合的查找效率遠(yuǎn)遠(yuǎn)高于列表，因此在不同的應(yīng)用場(chǎng)景下，一定要選擇合適的數(shù)據(jù)類型，在小數(shù)據(jù)量下看不出來(lái)性能區(qū)別，一旦換到大數(shù)據(jù)量下，就會(huì)變得差異性很大。

數(shù)據(jù)存儲(chǔ)開銷

集合的查找效率比列表要快得多，主要就是他們的存儲(chǔ)原理不一樣，集合需要消耗更多的空間來(lái)存儲(chǔ)額外的信息，用空間開銷來(lái)?yè)Q時(shí)間效率，接下來(lái)我們通過(guò)getsizeof()函數(shù)看看他們存儲(chǔ)開銷的差異，getiszeof()函數(shù)是python的sys模塊中用來(lái)獲取對(duì)象內(nèi)存大小的函數(shù)，返回的大小以字節(jié)為單位。

import sys
import random
list_test = list(range(1000000))
set_test = set(range(1000000))
print('列表占用大?。?, sys.getsizeof(list_test))
print('集合占用大?。?, sys.getsizeof(set_test))

輸出結(jié)果為：