Python 集合与列表

问题描述：

在 Python 中，哪种数据结构更高效/快速？假设顺序对我来说并不重要，而且我无论如何都会检查重复项，那么 Python 集合是否比 Python 列表慢？

解决方案 1：

这取决于你打算用它做什么。

在确定集合中是否存在某个对象时（如x in s），集合的速度要快得多，但其元素没有排序，因此您无法像在列表中一样通过索引访问项目。在实践中，集合的迭代速度也稍慢一些。

您可以使用timeit 模块来查看哪个模块更适合您的情况。

解决方案 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

解决方案 3：

Set由于近乎即时的“包含”检查而获胜：https://en.wikipedia.org/wiki/Hash_table

列表实现：通常是一个数组，低级接近金属，适合迭代和通过元素索引随机访问。

集合实现：https://en.wikipedia.org/wiki/Hash_table，它不会在列表上进行迭代，而是通过计算键的哈希值来查找元素，因此它取决于键元素的性质和哈希函数。类似于用于字典的。我怀疑list如果元素很少（<5），它可能会更快，元素数量越多，set包含检查的性能就越好。元素添加和删除也很快。另外，请始终记住，构建集合是有成本的！

注意：如果list已经排序，则在小列表上搜索list可能会非常快，但对于更多数据，set包含检查的速度会更快。

解决方案 4：

列出绩效：

>>> import timeit
>>> timeit.timeit(stmt='10**6 in a', setup='a = list(range(10**6))', number=1000)
15.08

设置性能：

>>> timeit.timeit(stmt='10**6 in a', setup='a = set(range(10**6))', number=1000)
3.90e-05

您可能想要考虑元组，因为它们与列表类似但无法修改。它们占用的内存略少，访问速度更快。它们不如列表灵活，但效率更高。它们的正常用途是用作字典键。

集合也是序列结构，但与列表和元组有两个不同之处。虽然集合确实有顺序，但顺序是任意的，不受程序员的控制。第二个不同之处是集合中的元素必须是唯一的。

set根据定义。[ python | wiki ]。

>>> x = set([1, 1, 2, 2, 3, 3])
>>> x
{1, 2, 3}

解决方案 5：

总结

数据结构（DS）很重要，因为它们用于对数据执行操作，这基本上意味着：获取一些输入，处理它，然后返回输出。

在某些特定情况下，某些数据结构比其他数据结构更有用。因此，问哪个（DS）更高效/更快速是很不公平的。这就像问刀和叉之间哪种工具更有效一样。我的意思是一切都取决于情况。

列表

列表是可变的序列，通常用于存储同类项目的集合。

套

集合对象是不同的可哈希对象的无序集合。它通常用于测试成员资格、从序列中删除重复项以及计算数学运算（例如交集、并集、差集和对称差集）。

用法

从一些答案中可以明显看出，在迭代值时，列表比集合快得多。另一方面，在检查某个项目是否包含在集合中时，集合比列表快。因此，您唯一可以说的是，对于某些特定操作，列表比集合更好，反之亦然。

解决方案 6：

当我使用 CPython 检查某个值是否是少数文字之一时，我对结果很感兴趣。set在 Python 3 中胜出，与tuple、list和 相比or：

from timeit import timeit

def in_test1():
  for i in range(1000):
    if i in (314, 628):
      pass

def in_test2():
  for i in range(1000):
    if i in [314, 628]:
      pass

def in_test3():
  for i in range(1000):
    if i in {314, 628}:
      pass

def in_test4():
  for i in range(1000):
    if i == 314 or i == 628:
      pass

print("tuple")
print(timeit("in_test1()", setup="from __main__ import in_test1", number=100000))
print("list")
print(timeit("in_test2()", setup="from __main__ import in_test2", number=100000))
print("set")
print(timeit("in_test3()", setup="from __main__ import in_test3", number=100000))
print("or")
print(timeit("in_test4()", setup="from __main__ import in_test4", number=100000))

输出：

tuple
4.735646052286029
list
4.7308746771886945
set
3.5755991376936436
or
4.687681658193469

3到5个文字，set仍然遥遥领先，并且or成为最慢的。

在 Python 2 中，set总是最慢的。or对于 2 到 3 个文字， 是最快的，而对于 4 个或更多文字，tuple和list更快。我无法区分tuple和的速度list。

当要测试的值被缓存在函数外的全局变量中，而不是在循环内创建文字时，set每次都会获胜，即使在 Python 2 中也是如此。

这些结果适用于 Core i7 上的 64 位 CPython。

解决方案 7：

集合更快，而且你可以用集合获得更多的功能，比如说你有两个集合：

set1 = {"Harry Potter", "James Bond", "Iron Man"}
set2 = {"Captain America", "Black Widow", "Hulk", "Harry Potter", "James Bond"}

我们可以轻松地将两个集合连接起来：

set3 = set1.union(set2)

找出两者的共同点：

set3 = set1.intersection(set2)

找出两者的不同之处：

set3 = set1.difference(set2)

还有更多！试试看吧，它们很有趣！此外，如果您必须处理 2 个列表中的不同值或 2 个列表中的公共值，我更喜欢将您的列表转换为集合，许多程序员都是这样做的。希望这对您有所帮助 :-)

解决方案 8：

我建议使用 Set 实现，其用例仅限于引用或搜索存在性，以及 Tuple 实现，其用例要求您执行迭代。列表是一种低级实现，需要大量内存开销。

解决方案 9：

与@Ellis Percival 的测试类似，我想补充一点，在添加元素时，列表的表现方式与集合类似。

添加元素

>>> def add_test_set(iterable):
...     for i in range(10000):
...         iterable.add(i)
...
>>> def add_test_list(iterable):
...     for i in range(10000):
...         iterable.append(i)
...
>>> timeit("add_test_set(iterable)",
...     setup="from __main__ import add_test_set; iterable = set()",
...     number=10000)
7.073143866999999
>>> timeit("add_test_list(iterable)",
...     setup="from __main__ import add_test_list; iterable = list()",
...     number=10000)
6.80650725000001

（我本来想编辑他的帖子以包含此内容，但编辑队列已满）

解决方案 10：

from datetime import datetime
listA = range(10000000)
setA = set(listA)
tupA = tuple(listA)
#Source Code

def calc(data, type):
start = datetime.now()
if data in type:
print ""
end = datetime.now()
print end-start

calc(9999, listA)
calc(9999, tupA)
calc(9999, setA)

对所有 3 个进行 10 次迭代比较后的输出：
比较

解决方案 11：

与列表相比，集合似乎可以非常快速地查找其中是否存在某个值。

A = list(range(1, 1000000))
A.pop(84559)

def find_in_set(A):
    maxA = max(A)
    for i in range(1,maxA+1):
         if i not in set(A):
            return i

下面的 find+in+list 函数几乎要花很长时间才能从列表“A”中找到缺失的84559。但是上面的 find_in_set 函数只需几秒钟。

def find_in_list(A):
    maxA = max(A)
    for i in range(1,maxA+1):
         if i not in A:
            return i

在这里你可以发现集合和列表的明显区别