[nylug-talk] Python programming question

[Michael Bacarella]

On Wed, Feb 28, 2007 at 09:49:25PM -0500, Eric Moore wrote:
> > Thought I'd pick the list-brain a bit.
> >
> > Given:
> >
> > v = {}
> > for i  in xrange(0,20000000):
> >     v[i] = 1
> >
> > Is calling keys() on v an expensive O(n) kind of operation, or more like 
> > a cheap O(1) operation?
> 
> It pretty much has to be O(n) since the list returned is a copy of the
> list of keys, and copying a list or array is generally an O(n)
> operation.  Well, I suppose you could use copy-on-write for it, in
> which case modifying the list would be the O(n) operation (or
> something similar).  I'm not a python expert, but I'd be very
> surprised if it weren't O(n).

You're right.

I was expecting keys() to behave more like iterkeys().  

-- 
Michael Bacarella <mbac at netgraft.com>

1-646-641-8662 (cell)

545 Eighth Avenue * Suite 401
New York, NY 10018

http://michael.bacarella.com/
http://netgraft.com/