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

Question

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

Answer 1

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

Answer 2

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!

Answer 3

Write your program so that it's clear 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 if it's significant in your code.

Answer 4

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

Answer 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.

Answer 6

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

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

Answer 7

len is an O(1) operation.