Python集vs列表

在Python中，哪种数据结构更高效/快速?假设顺序对我来说不重要，无论如何我都会检查重复，Python集比Python列表慢吗?

221343 次浏览
小开
最佳答案

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

当涉及到确定一个对象是否存在于set中时(如在x in s中)，set的速度要快得多，但它的元素是没有顺序的，所以你不能像在列表中那样通过索引访问项目。在实践中，迭代集的速度也比较慢。

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

小开

当您只想遍历值时，列表比集合略快。

但是，如果您想检查一个项是否包含在集合中，那么集合要比列表快得多。但是它们只能包含独特的项目。

事实证明，元组的执行方式几乎与列表完全相同，除了它们的不可变性。

迭代

>>> 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
小开

列表性能:

>>> 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定义。[__abc1 | __abc2]。

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

Set胜出，因为接近即时的“包含”检查:https://en.wikipedia.org/wiki/Hash_table

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

集实现:https://en.wikipedia.org/wiki/Hash_table，它不会在列表上迭代，而是通过从键计算哈希来查找元素，因此它取决于键元素和哈希函数的性质。类似于dict的用法。我怀疑list可以更快，如果你有很少的元素(<5)，元素计数越大，set对contains检查执行得越好。它还可以快速添加和删除元素。同时也要记住，创造一套游戏是有成本的!

请注意:如果list已经排序，那么在小列表中搜索list可能非常快，但对于更多数据，set用于包含检查更快。

小开

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

小开

博士tl;

数据结构(DS)很重要，因为它们用于对数据执行操作，这些操作基本上包含:获取一些输入、处理它和返回输出。

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

Lists

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

集合

set对象是不同哈希对象的无序集合。它通常用于测试成员关系，从序列中删除重复项，并计算数学操作，如交集，并，差，和对称差。

使用

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

小开 
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次后的输出: 比较 < / p >

小开

我感兴趣的结果时，检查与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个字面值是最快的，而tuple和list对于4个或更多字面值是最快的。我无法区分tuple和list的速度。

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

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

小开

集合更快，而且你可以得到更多有集合的函数，比如你有两个集合:

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)

还有更多!试试吧，很有趣的!此外，如果你必须处理两个列表中的不同值或两个列表中的通用值，我更喜欢将列表转换为集合，许多程序员都是这样做的。 希望它能帮助你:-)

小开

与@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

(我本来想编辑他的帖子，但编辑队列已经满了)


提交答案