469,600 Members | 2,393 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,600 developers. It's quick & easy.

Algorithmic complexity of len (list)?

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)?
Jul 18 '05 #1
8 4364
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
Jul 18 '05 #2
[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).

Jul 18 '05 #3
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)
Jul 18 '05 #4
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
Jul 18 '05 #5
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?
Jul 18 '05 #6
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.
Jul 18 '05 #7
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

Jul 18 '05 #8
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.
Jul 18 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by Roy Smith | last post: by
12 posts views Thread by Brett L. Moore | last post: by
4 posts views Thread by Generic Usenet Account | last post: by
4 posts views Thread by Xah Lee | last post: by
25 posts views Thread by Markus Svilans | last post: by
10 posts views Thread by pamelafluente | last post: by
26 posts views Thread by Lionel B | last post: by
reply views Thread by suresh191 | last post: by
4 posts views Thread by guiromero | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.