Python列表和集合的效率對比

WBOY
發布: 2023-04-12 11:13:05
轉載
1960 人瀏覽過

Python列表和集合的效率對比

程式運作效率

程式的運作效率分為兩種:第一種是時間效率,第二種是空間效率。時間效率稱為時間複雜度,而空間效率被稱為空間複雜度。時間複雜度主要衡量的是一個程式的運行速度,而空間複雜度則主要衡量一個程式所需的額外儲存空間。

一個程式執行所耗費的時間,從理論上說,是不能算出來的,只有你把程式放在機器上跑起來,才能知道,不同機器不同時間得出的結果可能不一樣。但是我們需要每個程式都上機測試嗎?顯然不現實,所以才有了時間複雜度這個分析方式。實際中我們計算時間複雜度時,其實不一定要計算精確的執行次數,而只需要大概執行次數,一般會使用大O漸進表示法,平時執行次數為1次的我們就可以說時間複雜度是O(1),需要n次的就可以說時間複雜度是O(n)。

空間複雜度是對演算法在運作過程中暫時佔用儲存空間大小的量度。空間複雜度不是程式佔用了多少個位元組的空間,因為這個實際運行過程中很難計算,所以空間複雜度算的是變數的個數。空間複雜度計算規則基本上跟時間複雜度類似,也使用大O漸進表示法。

Python組合資料類型中常用的主要有元組、列表、集合和字典,每種資料類型不同操作的時間複雜度可以參考Python的官方鏈接,網頁中有詳細的說明,

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

元組和列表都屬於序列類型,他們儲存機制基本上一致;集合和字典也基本上相同,唯一的差別就是集合每個元素沒有對應的值。接下來我們以集合和清單為例看看他們的查找效率和儲存開銷。

資料查找效率

關於集合和清單資料查找效率差距到底有多大?先看一組實例:

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()# 测试在列表中进行查找
for num in nums:
 if num in list_test:
 count_list += 1
t2 = time.time()
for num in nums:# 测试在集合中进行查找
 if num in set_test:
 count_set += 1
t3 = time.time()# 测试在集合中进行查找
print('找到个数,列表:{},集合:{}'.format(count_list, count_set))
print('使用时间,列表:{:.4f}s'.format(t2 - t1))
print('使用时间,集合:{:.4f}s'.format(t3 - t2))
登入後複製

輸出結果為:

找到个数,列表:515,集合:515
使用时间,列表:7.7953s
使用时间,集合:0.0010s
登入後複製

從上面例子可以清楚地看出,集合的查找效率遠高於列表,因此在不同的應用場景下,一定要選擇合適的資料類型,在小資料量下看不出來效能區別,一旦換到大數據量下,就會變得差異性很大。

資料儲存開銷

集合的查找效率比列表要快得多,主要是他們的儲存原理不一樣,集合需要消耗更多的空間來儲存額外的信息,用空間開銷來換時間效率,接下來我們透過getsizeof()函數看看他們儲存開銷的差異,getiszeof()函數是python的sys模組中用來取得物件記憶體大小的函數,傳回的大小以位元組為單位。

import sys
import random
list_test = list(range(1000000))
set_test = set(range(1000000))
print('列表占用大小:', sys.getsizeof(list_test))
print('集合占用大小:', sys.getsizeof(set_test))
登入後複製

輸出結果為:

列表占用大小:9000112
集合占用大小:33554656
登入後複製

從結果可以看出,同樣的資料內容,集合儲存的開銷是清單的好幾倍。

以上是Python列表和集合的效率對比的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:51cto.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板