Algorithmic complexity of len (list)?

[Roy Smith]

Is the length of a list stored in the object, or does len() have to
count the elements each time you call it? In other words, is len (list)
O(1) or O(n)?

[Sam Holden]

On Fri, 02 Jul 2004 19:18:20 -0400, Roy Smith <ro*@panix.com> wrote:

Is the length of a list stored in the object, or does len() have to
count the elements each time you call it? In other words, is len (list)
O(1) or O(n)?

I'd assume O(1), and the following seems to verify it:

import time
lists = []
for len_power in range(1,8):
lists.append(range(1,10**len_power))
for l in lists:
start = time.time()
length = len(l)
end = time.time()
print "%d\t%f" % (length, end-start)

I'm sure there's a python library that does a much better
job of determining average runtimes, but for this case if
it was O(n) is should show up pretty quick in the output
generated.

The existance of negative indexing strongly implies O(1) as
well, as does the existance of bounds checking when
accessing (rather than random core dumps).

--
Sam Holden

[Tim Peters]

[Roy Smith]

Is the length of a list stored in the object, or does len() have to
count the elements each time you call it? In other words, is len (list)
O(1) or O(n)?

O(1). Ditto len(tuple), len(dict), len(str), len(unicode), and
len(array.array).

[george young]

On Fri, 02 Jul 2004 19:18:20 -0400
Roy Smith <ro*@panix.com> threw this fish to the penguins:

Is the length of a list stored in the object, or does len() have to
count the elements each time you call it? In other words, is len (list)
O(1) or O(n)?

[Python 2.3.3]
timeit.py -s 'l=range(5000)' 'len(l)'
1000000 loops, best of 3: 0.975 usec per loop
timeit.py -s 'l=range(10000)' 'len(l)'
1000000 loops, best of 3: 0.975 usec per loop
timeit.py -s 'l=range(50000)' 'len(l)'
1000000 loops, best of 3: 0.975 usec per loop
timeit.py -s 'l=range(100000)' 'len(l)'
1000000 loops, best of 3: 0.975 usec per loop

Sure looks like O(0) to me.

seems to be the same for strings and tuples.

-- George Young

--
"Are the gods not just?" "Oh no, child.
What would become of us if they were?" (CSL)

[Aahz]

In article <ro***********************@reader2.panix.com>,
Roy Smith <ro*@panix.com> wrote:

Is the length of a list stored in the object, or does len() have to
count the elements each time you call it? In other words, is len (list)
O(1) or O(n)?

Consider that if it weren't, operations such as l.pop() and l[-3:] would
also be O(N)...

(I couldn't resist making a comment because I'm currently using your
..sig. ;-)
--
Aahz (aa**@pythoncraft.com) <*> http://www.pythoncraft.com/

"Typing is cheap. Thinking is expensive." --Roy Smith, c.l.py

[Roy Smith]

In article <cc**********@panix3.panix.com>, aa**@pythoncraft.com (Aahz)
wrote:

In article <ro***********************@reader2.panix.com>,
Roy Smith <ro*@panix.com> wrote:

Is the length of a list stored in the object, or does len() have to
count the elements each time you call it? In other words, is len (list)
O(1) or O(n)?

Consider that if it weren't, operations such as l.pop() and l[-3:] would
also be O(N)...

(I couldn't resist making a comment because I'm currently using your
.sig. ;-)

Well, I take that as meaning, "you really should have been able to
figure that out yourself if you just took the time to think about it".
I disagree. I can guess, I can even make intelligent informed guesses,
but it would still just be a guess.

One could think of implementations where l.pop() and l[-3:] are O(1),
but len(l) is O(n). I could, for example, keep a pointer to the tail of
the list, but not keep track of the number of elements.

Why would somebody want to implement it that way? I don't know, but
it's possible. Maybe they felt that accessing the ends of lists was
something that needed to be done fast, but computing their length
wasn't, and saving the extra bit of memory for each list was important.

Iterators sort of look like lists, but I can't get their length quickly
(or even idempotently, it would appear). If they didn't think getting
the length of an iterator was important, then maybe they didn't think
getting the length of a list was important either.

I can make measurements, or download the source and look at it, but I
shouldn't have to. Likewise, I shouldn't have to engage in a deep
analytic guessing game of what the designer had in mind when designing
the container. I want a tool, not a hobby. One of the (few) things I
like about the C++ STL is that it documents these types of things. Is
there any reason Python couldn't?

[A. Lloyd Flanagan]

Roy Smith <ro*@panix.com> wrote in message news:<ro***********************@reader2.panix.com> ...

analytic guessing game of what the designer had in mind when designing
the container. I want a tool, not a hobby. One of the (few) things I
like about the C++ STL is that it documents these types of things. Is
there any reason Python couldn't?

I believe this has been mentioned before, and the main reason it
hasn't been done may be that no one has done it (yet). As a first
step, somebody should summarize this discussion and add it to the
language reference.

[Peter Otten]

Roy Smith wrote:

(or even idempotently, it would appear). If they didn't think getting
the length of an iterator was important, then maybe they didn't think
getting the length of a list was important either.

They might think *not* getting the length of an iterator is important.

Peter

[Leif K-Brooks]

Roy Smith wrote:

Iterators sort of look like lists, but I can't get their length quickly
(or even idempotently, it would appear).

You can if that particular iterator happens to have an __len__ method. I
would assume that the iterator protocol doesn't require one because that
would make infinite iterators impossible.