len（）关于集合和列表的复杂性
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
它是否与特定的基准相关，比如，构build集比构build列表需要更多的时间，并且基准也考虑到了这一点？
如果创build一个集合对象比创build一个列表需要更多的时间，那么根本原因是什么？
首先，你还没有测量len()的速度，你已经测量了创build一个list / set的速度和len()的速度。
使用timeit的--setup参数：
$ 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) len(a); len(a); ...; len(a) 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()在列表和集合上有相同的performance，但是现在你确定结果是正确的。）
第三， “复杂性”和“速度”是相关的，但我相信你是在混淆。 len()对列表和集合具有O（1）复杂性这一事实并不意味着它必须以列表和集合上的相同速度运行。
这意味着，无论列表a有多长， len(a)平均执行相同的渐进步数。 而且，无论集合b有多长， len(b)执行相同的渐进步数。 但是，计算列表和集合的大小的algorithm可能会不同，导致不同的性能（时间表明情况并非如此，但这可能是一种可能性）。
最后，
如果创build一个集合对象比创build一个列表需要更多的时间，那么潜在的原因是什么？
一套，如你所知，不允许重复的元素。 CPython中的集合被实现为哈希表（以确保平均的O（1）插入和查找）：构build和维护哈希表比将元素添加到列表要复杂得多。
具体来说，在构build一个集合时，必须计算哈希值，构build哈希表，查找以避免插入重复的事件等等。 相比之下，CPython中的列表是作为一个简单的指针数组实现的，这些指针根据需要是malloc() ed和realloc() 。
相关的行是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 }
两者都只是一个静态的查找。
那么你可能会问什么？ 您也可以测量对象的创build。 创build一个集合比列表更费时。
使用这个和-s标志来计时， 而不考虑第一个string：
~$ 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函数，结果几乎相同，因为我们没有考虑set / list的创build时间。
是的，你是对的，更多的是因为python创buildset和list对象所需的时间不同。 作为一个更公平的基准，您可以使用timeit模块并使用setupparameter passing对象：
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的世界。 实际上，设置对象使用散列表，而散列表使用散列函数来创build项目的散列值，并将它们映射到值，并在此交易中调用函数并计算散列值，而另外一些额外的任务将花费很多时间。 虽然创build一个列表python只是创build一个对象序列，您可以通过索引访问它们。
您可以从Cpython源代码中查看set_lookkey函数的更多详细信息。
还要注意，如果两个algorithm具有相同的复杂度，那么并不意味着这两个algorithm具有完全相同的运行时间或执行速度。 1
因为big O符号描述了函数的限制行为，并没有显示确切的复杂性等式。 例如，下面的方程f(x)=100000x+1和f(x)=4x+20的复杂性是O（1），这意味着两者都是线性方程bur，你可以看到第一个函数有一个非常大的斜率，并为相同的input，他们会给出不同的结果。
让我在这里O(1)出色的答案： O(1)只会告诉你关于投入规模的增长顺序 。
O(1)尤其仅意味着关于input大小的 恒定时间 。 一个方法可能总是花费0.1s，任何input，另一个可能需要1000年的任何input，他们都是O(1)
在这种情况下，虽然文档有一定程度的模糊性 ，但这意味着该方法需要大致相同的时间处理大小为1的列表，以处理大小为1000列表 ; 同样，处理大小为1的字典需要相同的时间来处理大小为1000的字典。
不能保证不同的数据types 。
这并不令人惊讶，因为在调用堆栈的某个点执行len()会根据数据types的不同而有所不同。
顺便说一句， 这种歧义在静态types的语言中被消除，其中ClassA.size()和ClassB.size()适用于所有的意图，而purpouse则是两种不同的方法。
删除len(a)语句。 结果几乎相同。 一个集合需要散列，只保留不同的项目，因此速度较慢。
许多人已经注意到O（1）不是关于不同数据types的性能，而是关于性能作为不同input大小的函数。
如果你想testingO（1）性，你会找更多的东西
~$python -m timeit --setup "a=list(range(1000000))" "len(a)" 10000000 loops, best of 3: 0.198 usec per loop ~$python -m timeit --setup "a=list(range(1))" "len(a)" 10000000 loops, best of 3: 0.156 usec per loop
大数据或小数据，所花费的时间非常相似。 每隔一段时间，这就将testing时间与安装时间分开了，但是并没有减less镜像时间和循环时间的噪声。
