len()关于集合和列表的复杂性

Question

len()关于集合和列表的复杂性同样是O(1).为什么需要更多时间来处理集合？

~$ python -m timeit "a=[1,2,3,4,5,6,7,8,9,10];len(a)"
10000000 loops, best of 3: 0.168 usec per loop
~$ python -m timeit "a={1,2,3,4,5,6,7,8,9,10};len(a)"
1000000 loops, best of 3: 0.375 usec per loop

它是否与特定基准相关,因为它需要更多时间来构建集而不是列表,基准也考虑到了这一点？

如果创建set对象比创建列表需要更多时间,那么潜在的原因是什么？

Answer 1

首先,你还没有测量的速度len(),你已经测量创建列表/套的速度加上速度len().

使用以下--setup参数timeit:

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)"
10000000 loops, best of 3: 0.0369 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)"
10000000 loops, best of 3: 0.0372 usec per loop

传递给的语句--setup在测量速度之前运行len().

其次,你应该注意到这len(a)是一个非常快速的陈述.测量其速度的过程可能受到"噪音"的影响.考虑到timeit执行(和测量)的代码等效于以下内容:

for i in itertools.repeat(None, number):
    len(a)

因为这两个len(a)和itertools.repeat(...).__next__()是快速的操作和他们的速度可能是相似的,速度itertools.repeat(...).__next__()可能会影响时序.

出于这个原因,你最好测量len(a); len(a); ...; len(a)(重复100次左右),以便for循环体比迭代器花费更多的时间:

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.2 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.3 usec per loop

(结果仍然表示len()在列表和集合上具有相同的性能,但现在您确定结果是正确的.)

第三, "复杂性"和"速度"确实是相关的,但我相信你会产生一些困惑.列表和集合len()具有O(1)复杂性的事实并不意味着它必须以相同的速度在列表和集合上运行.

这意味着,平均而言,无论列表有多长a,都len(a)执行相同的渐近步数.无论集合多长b,len(b)执行相同的渐近步数.但是用于计算列表和集合的大小的算法可能是不同的,导致不同的性能(时间显示不是这种情况,但是这可能是可能的).

最后,

如果创建set对象比创建列表需要更多时间,那么潜在的原因是什么？

如您所知,一组不允许重复元素.CPython中的集合实现为哈希表(以确保平均O(1)插入和查找):构建和维护哈希表要比向列表中添加元素复杂得多.

具体来说,在构造集合时,您必须计算哈希值,构建哈希表,查找以避免插入重复事件等.相比之下,CPython中的列表实现为一个简单的指针数组,可根据需要进行malloc()编辑和realloc()编辑.

Answer 2

相关的行是http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640

640     static Py_ssize_t
641     set_len(PyObject *so)
642     {
643         return ((PySetObject *)so)->used;
644     }

和http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup#l431

431     static Py_ssize_t
432     list_length(PyListObject *a)
433     {
434         return Py_SIZE(a);
435     }

两者都只是静态查找.

那么你可能会有什么不同.您也可以测量对象的创建.创建集合比列表要花费更多时间.

Answer 3

使用带有-s标志的timeit 而不考虑第一个字符串:

~$ python -mtimeit -s "a=range(1000);" "len(a)"
10000000 loops, best of 3: 0.0424 usec per loop
                           ? 

~$ python -mtimeit -s "a={i for i in range(1000)};" "len(a)"
10000000 loops, best of 3: 0.0423 usec per loop
                           ? 

现在它只考虑len函数,结果几乎相同,因为我们没有考虑集合/列表的创建时间.

Answer 4

是的,你是对的,这更多是因为python 创建set和list对象所需的时间不同.作为更公平的基准,您可以使用timeit模块并使用setup参数传递对象:

from timeit import timeit

print '1st: ' ,timeit(stmt="len(a)", number=1000000,setup="a=set([1,2,3]*1000)")
print '2nd : ',timeit(stmt="len(a)", number=1000000,setup="a=[1,2,3]*1000")

结果:

1st:  0.04927110672
2nd :  0.0530669689178

如果你想知道为什么会这样,让我们​​来看看python世界.实际上set对象使用哈希表,哈希表使用哈希函数来创建项的哈希值并将它们映射到值,并在此交易中调用函数并计算哈希值,另外一些额外的任务将花费很多时间.在创建列表python时,只需创建一系列对象,您可以使用索引访问它们.

您可以set_lookkey从Cpython源代码中查看有关函数的更多详细信息.

另请注意,如果两个算法具有相同的复杂度,则并不意味着两个算法具有完全相同的运行时间或执行速度.¹

_{因为big O符号描述了函数的限制行为,并没有显示精确的复杂性方程.例如,下面的方程的复杂性f(x)=100000x+1和f(x)=4x+20是O(1),这意味着这两者都是线性方程BUR,你可以看到第一功能有一个相当大很多斜率,并且对于相同的输入他们会给出不同的结果.}