Perbandingan kecekapan senarai dan set Python

Kecekapan pengendalian program

Terdapat dua jenis kecekapan pengendalian program: pertama ialah kecekapan masa, dan kedua ialah kecekapan ruang. Kecekapan masa dipanggil kerumitan masa, manakala kecekapan ruang dipanggil kerumitan ruang. Kerumitan masa terutamanya mengukur kelajuan berjalan program, manakala kerumitan ruang terutamanya mengukur ruang storan tambahan yang diperlukan oleh program.

Secara teorinya, masa yang diperlukan untuk melaksanakan program tidak boleh dikira Hanya apabila anda menjalankan program pada mesin anda boleh tahu bahawa hasil yang diperoleh oleh mesin yang berbeza pada masa yang berbeza mungkin berbeza. Tetapi adakah kita perlu menguji setiap program pada komputer? Ia jelas tidak realistik, jadi kaedah analisis kerumitan masa dibangunkan. Dalam amalan, apabila kita mengira kerumitan masa, kita tidak semestinya perlu mengira bilangan eksekusi yang tepat, tetapi hanya anggaran bilangan pelaksanaan Kita biasanya menggunakan perwakilan asimptotik O Besar Jika bilangan pelaksanaan biasanya 1, kita boleh katakan kerumitan masa Ia adalah O(1).

Kerumitan ruang ialah ukuran jumlah ruang storan yang diduduki sementara oleh algoritma semasa operasi. Kerumitan ruang bukanlah berapa banyak bait ruang yang diduduki oleh program, kerana sukar untuk dikira semasa operasi sebenar, jadi kerumitan ruang mengira bilangan pembolehubah. Peraturan pengiraan kerumitan ruang pada dasarnya serupa dengan kerumitan masa, dan juga menggunakan tatatanda asimptotik O besar.

Jenis data gabungan yang biasa digunakan dalam Python ialah tuple, senarai, set dan kamus Untuk kerumitan masa operasi yang berbeza bagi setiap jenis data, sila rujuk pautan rasmi Python Terdapat arahan terperinci pada halaman web.

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

Tuple dan senarai ialah jenis jujukan, dan mekanisme penyimpanannya pada asasnya adalah sama; adalah juga pada asasnya sama, satu-satunya perbezaan ialah tiada nilai yang sepadan untuk setiap elemen koleksi. Seterusnya, kami mengambil set dan senarai sebagai contoh untuk melihat kecekapan carian dan overhed storan mereka.

Kecekapan carian data

Berapa besar jurang antara kecekapan carian data set dan senarai? Mari kita lihat satu set contoh dahulu:

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))

Hasil keluarannya ialah:

找到个数，列表：515，集合：515
使用时间，列表：7.7953s
使用时间，集合：0.0010s

Daripada contoh di atas, dapat dilihat dengan jelas bahawa kecekapan carian set adalah banyak. lebih tinggi daripada senarai, jadi dalam senario aplikasi yang berbeza, anda mesti memilih jenis data yang sesuai Jika anda menggunakan jumlah data yang kecil, anda tidak akan melihat sebarang perbezaan dalam prestasi Setelah anda bertukar kepada jumlah data yang besar. perbezaan akan menjadi sangat berbeza.

Overhed storan data

Kecekapan carian set adalah lebih pantas daripada senarai Sebab utama ialah prinsip storan set perlu menggunakan lebih banyak ruang untuk menyimpan maklumat tambahan gunakan ruang. Overhed datang sebagai pertukaran untuk kecekapan masa Seterusnya, kami menggunakan fungsi getsizeof() untuk melihat perbezaan dalam overhed storan mereka Fungsi getiszeof() ialah fungsi yang digunakan dalam modul sys untuk mendapatkan saiz memori objek saiz yang dikembalikan adalah dalam bait.

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

Hasil output ialah:

列表占用大小：9000112
集合占用大小：33554656

Seperti yang dapat dilihat daripada keputusan, untuk kandungan data yang sama, kos penyimpanan koleksi adalah beberapa kali ganda daripada senarai.

Atas ialah kandungan terperinci Perbandingan kecekapan senarai dan set Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!