How is the __len__ method implemented in various container types in Python? [duplicate]

Question

Until now, when I used the len function with various container types (let's say the list type for now), I assumed that each container type has a field member which stores the length of that particular object.. Coming from Java, this made a lot of sense. But when I come to think about it, I don't think this is true, this made me confused.

Whenever I'm using the len function on an object which implement __length__, does it calculates the length by iterating on the object's elements, or just returning the length somehow immediately?

The question came to me actually from using the dict built-in type. I added some elements (a lot of them) to the dictionary and eventually I needed to get the amount of elements in the dictionary, so because I'm not sure what is the time complexity of the len function, I decided to count the elements as I insert them... but I'm not sure this is the right solution to my problem.

This is an example code for my question:

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)

Second solution looks nicer (and shorter) to me... and I know that theoretically the time complexity is the same whether the len function is instant or not, in the second solution I'm afraid it iterates twice to 10 ** 6 (first for the dictionary comprehension, and second for the length calculation).

Enlighten me please.

Answer 1

You are very definitely over-thinking this. Python is not really the language that you should be using if you're worried about optimising at this level.

That said, on the whole Python's containers do know their own lengths, without having to iterate. The built-in types are implemented in C (in the CPython implementation), and I'd have to dig into the actual code to find out exactly where it's implemented, but len is always a constant-time call.