问len()在集合和列表方面的复杂性

EN

--首先， --您没有测量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)是一个非常快速的语句。测量速度的过程可能会受到“噪音”的影响。考虑到按时间执行(并测量)的代码相当于以下内容：

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()ed和realloc()ed。

相关的行是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     }

两者都只是静态查找。

那么你可能会问的区别是什么呢？您也可以测量对象的创建。创建一个集合比创建一个列表要花费更多时间。

在不考虑第一个字符串的情况下，将此与-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函数，结果几乎是一样的，因为我们没有考虑到set/list的创建时间。