Python: Do Python Lists keep a count for len() or does it count for each call?

Python Programming

Question or problem about Python programming:

If I keep calling len() on a very long list, am I wasting time, or does it keep an int count in the background?

How to solve the problem:

Solution 1:

Don’t worry: Of course it saves the count and thus len() on lists is a pretty cheap operation. Same is true for strings, dictionaries and sets, by the way!

Solution 2:

And one more way to find out how it’s done is to look it up on Google Code Search look at the source on GitHub, if you don’t want to download the source yourself.

static Py_ssize_t list_length(PyListObject *a)
{
    return a->ob_size;
}

Solution 3:

len is an O(1) operation.

Solution 4:

Write your program so that it’s optimised for clarity and easily maintainable. Is your program clearer with a call to len(foo)? Then do that.

Are you worried about the time taken? Use the timeit module in the standard library to measure the time taken, and see whether it is significant in your code.

You will, like most people, very likely be wrong in your guesses about which parts of your program are slowest. Avoid the temptation to guess, and instead measure it to find out.

Remember that premature optimisation is the root of all evil, in the words of Donald Knuth. Only focus on the speed of code that you have measured the speed of, to know whether the benefit would be worth the cost of changing how it works.

Solution 5:

The question has been answered (len is O(1)), but here’s how you can check for yourself:

$ python -m timeit -s "l = range(10)" "len(l)"
10000000 loops, best of 3: 0.119 usec per loop
$ python -m timeit -s "l = range(1000000)" "len(l)"
10000000 loops, best of 3: 0.131 usec per loop

Yep, not really slower.

Solution 6:

A Python “list” is really a resizeable array, not a linked list, so it stores the size somewhere.

Solution 7:

It has to store the length somewhere, so you aren’t counting the number of items every time.

Hope this helps!