Python集与列表

Question

在Python中,哪种数据结构更有效/更快？假设顺序对我来说并不重要,无论如何我会检查重复项,Python设置是否比Python列表慢？

Answer 1

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

在确定对象是否存在于集合中时(如在x in s)中,集合明显更快,但在迭代其内容时比列表慢.

您可以使用timeit模块查看哪种情况更快.

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

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

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

设置实现：https : //en.wikipedia.org/wiki/Hash_table，它不迭代列表，而是通过从键计算散列来找到元素，因此它取决于键元素和散列的性质功能。类似于用于 dict 的内容。我怀疑list如果元素很少（< 5）可能会更快，元素数量越大，set包含检查的性能越好。元素添加和删除也很快。还要记住，建立一个集合是有成本的！

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

Answer 4

太长了；博士

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

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

列表

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

套

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

用法

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

Answer 5

清单表现:

>>> import timeit
>>> timeit.timeit(stmt='10**6 in a', setup='a = range(10**6)', number=100000)
0.008128150348026608

设定表现:

>>> timeit.timeit(stmt='10**6 in a', setup='a = set(range(10**6))', number=100000)
0.005674857488571661

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

集合也是序列结构,但与列表和元组有两个不同.虽然集合确实有订单,但该顺序是任意的,不受程序员的控制.第二个区别是集合中的元素必须是唯一的.

set根据定义.[ python | 维基 ].

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

Answer 6

在使用 CPython 检查某个值是否是少数文字之一时，我对结果很感兴趣。set在 Python 3 vs 中获胜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文本和tuple和list是具有4个或多个文字更快。我无法区分tuplevs的速度list。

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

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