python教程—len()在集合和列表方面的复杂性-Python实用宝典

python教程—len()在集合和列表方面的复杂性

len()对于集合和列表的复杂度是O(1)。为什么处理集合需要更多的时间?

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对象需要更多的时间,那么潜在的原因是什么?

回答

首先,你没有测量len()的速度,你测量了列表/集合创建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)是一个非常快的语句。测量其速度的过程可能会受到“噪音”的影响。假设

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

因为len(a)和itertools.repeat(…). _next__()都是快速操作,它们的速度可能相似,所以itertools.repeat(…). _next__()的速度可能会影响计时。

因此,最好测量len(a);len(一个);…;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)都执行相同的渐近步骤数。但是计算列表和集合大小的算法可能不同,从而导致不同的性能(time - it表明情况并非如此,但是这也有可能)。

<强>最后,< /强>

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

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

具体地说,在构造一个集合时,您必须计算哈希值、构建哈希表、查找哈希表以避免插入重复的事件等等。相反,CPython中的列表实现为一个简单的指针数组,根据需要使用malloc()ed和realloc()ed。

​Python实用宝典 (pythondict.com)
不只是一个宝典
欢迎关注公众号:Python实用宝典

本文由 Python实用宝典 作者:Python实用宝典 发表,其版权均为 Python实用宝典 所有,文章内容系作者个人观点,不代表 Python实用宝典 对观点赞同或支持。如需转载,请注明文章来源。
0

发表评论