list、array与set
- 详述
- 测试代码
详述
本文对比 list 与 set 在插入和取值时的性能差异，以提供一条什么时候该选择什么数据类型的建议。先上结果：
array 与 list 的不同：
- 内存方面
- array 是 C array 的包装，它直接存储数据，占用的内存大小 = 元素个数 * 元素类型
- list 是 Python Object，其中存储的每个数据都会被包装成 Python Object，所以内存占用大的多
- 数据类型方面
- array 只能存储相同数据类型
- list 可以存储不同数据类型
- 操作时间
- list 因为存储的就是 PyObject，所以进行各类处理不需要频繁的进行数据转换
- array 存储原始的 C 数据，所以和其他 Python 数据进行操作时，每次都要进行类型转换
选择 list 的场景
- 需要数据是有序的
- 需要存储可变变量（列表、字典）的
- 数据中可能会有重复的
选择 set 的场景
- 当需要频繁判断数据存在性，时间复杂度为 O(1)，list 和 array 均为 O(N)，但是 array 比 list 慢的多，因为每次判断都要对 array 中的元素进行 PyObject 和原始数据类型的转换。而 set 的查询这么快，其本质是在 Python 内部，set 是使用 hash table 来构建的
- 数据是无序的
- 数据是不可变变量的
- 数据没有重复的
- 数据是不可变变量的
选择 array 的场景
- 需要更节省内存
测试结果
结果总结（速度）：
- 插入大量数据 set > list >> array
- 判断存在性 set >>>>>>>>>>>>>> list >> array
- 弹出第一个值 array > list
- 弹出最后一个值 set > array > list
- 在首部插入数据 array >> list
- 在尾部插入数据 array ≈ list
- 追加数据（append 和 add）list > array > set
注意：上述总结中仅涉及对容器自身的操作，若在这些操作之外还有额外操作，主要重点注意array中的数据转换为 PyObject 的性能开销，除非是数据量特别大，内存需要谨慎分配的场景，其他场景均建议使用 list 而非 array
1、插入 100 万数据的速度比
2、判断存在性，判断的第一个值就存在
3、判断存在性，判断的最后一个值才存在
4、弹出第一个值
5、弹出最后一个值
6、在首部插入数据
7、在尾部插入数据
7、追加数据
测试代码
from array import array
from timeit import timeit
number = 100
l = list()
t = timeit("for i in range(100_0000): l.append(i)", number=number, globals=globals())
print(f"[List] List append time: {t:.20f}")
a = array("I")
t = timeit("for i in range(100_0000): a.append(i)", number=number, globals=globals())
print(f"[Array] Array append time: {t:.20f}")
_s = set()
t = timeit("for i in range(100_0000): _s.add(i)", number=number, globals=globals())
print(f"[Set] Set append time: {t:.20f}")
t = timeit("1 in l", number=number, globals=globals())
print(f"[List] First element in list: {t= :.20f}")
t = timeit("1 in a", number=number, globals=globals())
print(f"[Array] First element in array: {t= :.20f}")
t = timeit("1 in _s", number=number, globals=globals())
print(f"[Set] First element in set: {t= :.20f}")
t = timeit("99_9999 in l", number=number, globals=globals())
print(f"[List] Last element in list: {t= :.20f}")
t = timeit("99_9999 in a", number=number, globals=globals())
print(f"[Array] Last element in array: {t= :.20f}")
t = timeit("99_9999 in _s", number=number, globals=globals())
print(f"[Set] Last element in set: {t= :.20f}")
t = timeit("l.pop(0)", number=number, globals=globals())
print(f"[List] List pop 0: {t= :.20f}")
t = timeit("a.pop(0)", number=number, globals=globals())
print(f"[Array] Array pop 0: {t= :.20f}")
t = timeit("l.pop(-1)", number=number, globals=globals())
print(f"[List] List pop -1: {t= :.20f}")
t = timeit("a.pop(-1)", number=number, globals=globals())
print(f"[Array] Array pop -1: {t= :.20f}")
t = timeit("_s.pop()", number=number, globals=globals())
print(f"[Set] Set pop random: {t= :.20f}")
t = timeit("l.insert(0, 0)", number=number, globals=globals())
print(f"[List] List insert first: {t= :.20f}")
t = timeit("a.insert(0, 0)", number=number, globals=globals())
print(f"[Array] Array insert first: {t= :.20f}")
t = timeit("l.insert(-1, 0)", number=number, globals=globals())
print(f"[List] List insert last: {t= :.20f}")
t = timeit("a.insert(-1, 0)", number=number, globals=globals())
print(f"[Array] Array insert last: {t= :.20f}")
t = timeit("l.append(0)", number=number, globals=globals())
print(f"[List] List append: {t= :.20f}")
t = timeit("a.append(0)", number=number, globals=globals())
print(f"[Array] Array append: {t= :.20f}")
t = timeit("_s.add(0)", number=number, globals=globals())
print(f"[Set] Set append: {t= :.20f}")
