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

从结果可以看出，同样的数据内容，集合存储的开销是列表的好几倍。