Python集合与列表

Question

在Python中，哪种数据结构更高效、更快呢？假设我不太在乎顺序，而且我会检查重复项，那么Python的集合（set）会比Python的列表（list）慢吗？

Answer 1

集合（Set）的优势在于几乎可以瞬间检查某个元素是否存在：https://en.wikipedia.org/wiki/Hash_table

列表（List）的实现：通常是一个数组，底层操作比较接近硬件，适合遍历和通过元素索引随机访问。

集合（Set）的实现：https://en.wikipedia.org/wiki/Hash_table，它不是通过遍历列表来查找元素，而是通过计算一个哈希值来找到元素，这个过程依赖于键的特性和哈希函数。这个方法和字典（dict）使用的类似。我猜如果元素很少（少于5个），列表（list）可能会更快，但当元素数量增多时，集合（set）在检查元素是否存在时会表现得更好。它在添加和删除元素时也很快。不过，记住构建一个集合是有成本的！

注意：如果列表（list）已经排好序，那么在小型列表中查找可能会很快，但随着数据量增大，集合（set）在检查元素是否存在时会更快。

Answer 2

列表在你只是想遍历值的时候，速度稍微快一点。

但是，如果你想检查某个项目是否在里面，集合的速度就比列表快很多。不过，集合里只能放独一无二的项目。

其实，元组的表现和列表几乎一模一样，唯一的不同就是元组是不可改变的。

遍历

>>> def iter_test(iterable):
...     for i in iterable:
...         pass
...
>>> from timeit import timeit
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = set(range(10000))",
...     number=100000)
12.666952133178711
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = list(range(10000))",
...     number=100000)
9.917098999023438
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = tuple(range(10000))",
...     number=100000)
9.865639209747314

判断一个对象是否存在

>>> def in_test(iterable):
...     for i in range(1000):
...         if i in iterable:
...             pass
...
>>> from timeit import timeit
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = set(range(1000))",
...     number=10000)
0.5591847896575928
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = list(range(1000))",
...     number=10000)
50.18339991569519
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = tuple(range(1000))",
...     number=10000)
51.597304821014404

Answer 3

这要看你打算怎么使用它。

当你想检查一个对象是否在集合里时，集合的速度要快很多（比如说 x in s），但是集合里的元素是没有顺序的，所以你不能像在列表里那样通过索引来访问某个元素。实际上，遍历集合的速度也会稍微慢一些。

你可以使用 timeit模块 来看看在你的情况下哪个更快。