4

直到现在，当我将len函数用于各种容器类型（list现在说类型）时，我假设每个容器类型都有一个字段成员，用于存储该特定对象的长度。来自 Java，这使得很多感觉。但是当我想起来时，我不认为这是真的，这让我感到困惑。

每当我在len实现的对象上使用该函数时__length__，它是通过迭代对象的元素来计算长度，还是以某种方式立即返回长度？

这个问题实际上来自使用dict内置类型。我在字典中添加了一些元素（其中很多），最终我需要获取字典中元素的数量，所以因为我不确定len函数的时间复杂度是多少，所以我决定将元素计算为我插入它们......但我不确定这是解决我问题的正确方法。

这是我的问题的示例代码：

d = {}
count = 0
for i in range(10 ** 6):
    d[i] = True
    count += 1

VS

d = {i: True for i in range(10 ** 6)}
count = len(d)

第二个解决方案对我来说看起来更好（并且更短）......而且我知道理论上时间复杂度是相同的，无论len函数是否是即时的，在第二个解决方案中，我担心它会迭代两次到 10 ** 6 （第一个用于字典理解，第二用于长度计算）。

请启发我。

4

1 回答 1

7

你肯定是在想这个。如果您担心在此级别进行优化，那么 Python 并不是您真正应该使用的语言。

也就是说，总的来说，Python 的容器确实知道自己的长度，而无需迭代。内置类型是在 C 中实现的（在 CPython 实现中），我必须深入研究实际代码才能准确找出它的实现位置，但len始终是一个常量时间调用。

于 2013-10-17T11:51:20.203 回答