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

它是否与特定的基准有关，例如，构建集合比构建列表需要更多的时间，而且基准也考虑到了这一点？在

如果创建一个集合对象比创建一个列表要花费更多的时间，那么潜在的原因是什么？在

Answer 1

首先，您没有测量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)是一个非常快速的语句。测量其速度的过程可能会受到“噪音”的影响。考虑the code executed (and measured) by timeit等效于以下内容：

^{pr2}$

由于len(a)和{}都是快速操作，并且它们的速度可能相似，itertools.repeat(...).__next__()的速度可能会影响计时。在

{或者说循环的次数要比循环的次数高出很多倍，所以对于循环次数来说：

$ 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)执行相同的渐进步数。但是计算列表和集合大小的算法可能不同，从而导致不同的性能（timeit显示情况并非如此，但这可能是一种可能性）。在

最后，

If the creation of a set object takes more time compared to creating a list, what would be the underlying reason?

如您所知，集合不允许重复的元素。CPython中的集合被实现为散列表（以确保平均O（1）插入和查找：构造和维护哈希表比向列表添加元素复杂得多。在

具体地说，在构造一个集合时，必须计算散列值、构建哈希表、查找它以避免插入重复的事件等等。相比之下，CPython中的列表被实现为一个简单的指针数组，根据需要，malloc()ed和{}ed。在

Answer 2

与-s标志一起使用，可以在不考虑第一个字符串的情况下对其进行计时：

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

---

^{pr2}$

现在它只考虑了len函数，由于没有考虑集合/列表的创建时间，结果几乎相同。在

Answer 3

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

^{pr2}$

两者都只是静态查找。在

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