在Python中,哪种数据结构更高效/快速?假设顺序对我来说不重要,无论如何我都会检查重复,Python集比Python列表慢吗?
当前回答
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次后的输出: 比较
其他回答
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次后的输出: 比较
设置因近即时“包含”检查而获胜:https://en.wikipedia.org/wiki/Hash_table
列表实现:通常是一个数组,低层接近金属,适合迭代和随机访问的元素索引。
Set implementation: https://en.wikipedia.org/wiki/Hash_table, it does not iterate on a list, but finds the element by computing a hash from the key, so it depends on the nature of the key elements and the hash function. Similar to what is used for dict. I suspect list could be faster if you have very few elements (< 5), the larger element count the better the set will perform for a contains check. It is also fast for element addition and removal. Also always keep in mind that building a set has a cost !
注意:如果列表已经排序,那么在小列表上搜索列表可能会非常快,但是对于更多的数据集,对于包含检查会更快。
集合更快,而且你可以得到更多有集合的函数,比如你有两个集合:
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
(我本来想编辑他的帖子,但编辑队列已经满了)
当您只想遍历值时,列表比集合略快。
但是,如果您想检查一个项是否包含在集合中,那么集合要比列表快得多。但是它们只能包含独特的项目。
事实证明,元组的执行方式几乎与列表完全相同,除了它们的不可变性。
迭代
>>> 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