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

从上述示例可以清晰看出，集合的查找效率显著高于列表。因此，在不同应用场景下，必须选择合适的数据类型。在数据量较小时，性能差异可能不明显；然而，当数据量增大时，两者之间的性能差异将变得极为显著。

数据存储开销

集合查找效率远高于列表，主要归因于两者存储原理的不同。集合需要消耗更多空间来存储额外信息，即通过牺牲空间来换取时间效率。接下来，我们通过Python sys模块中的getsizeof()函数来查看它们存储开销的具体差异。该函数用于获取对象的内存大小，返回值以字节为单位。

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列表和集合的效率对比的文章就介绍到这了,更多相关Python列表和集合内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！