an indexed list - how to do it in python

[Brian Dam Pedersen]

"Alex Martelli" <alex at magenta.com> wrote in message
news:8n8j86030po at news2.newsguy.com...
> "Brian Dam Pedersen" <brian.pedersen at mail.danbbs.dk> wrote in message
> news:2hOl5.176$rG7.2928778257 at news.euroconnect.net...
> > "Aahz Maruch" <aahz at netcom.com> wrote in message
> > news:8n4fu8$dav$1 at slb3.atl.mindspring.net...
> > > In article <8n3tm2$jug$1 at nnrp1.deja.com>,  <dmost at magna.com.au> wrote:
> > > >
> > > >I want to create, in Python, an object that mixes the behavior of a
> > > >sequence and a mapping. The primary behavior should be that of a
> > > >mutable sequence, or list, but the objects in the list should also be
> > > >accessible by a key value.
> > >
> > > How many items?  What performance do you need?  One option would be to
> > > write a wrapper class that maintains the info as *both* a dict and a
> > > list.  Then the only tricky part is inserting new items by order into
> > > the list (which will be O(N)).
> >
> > Or O(log N) if you do a binary search for the insertion point (since
this
> is
> > an ordered list)
>
> Nope, still O(N), since Python's "lists" are implemented as compact blocks
> of memory: you may find the insertion-point as fast as you want, but once
> you HAVE found it (on average, smack in the middle of the existing
> sequence), then to insert the item you have to move up (on average)
> N/2 other items.  So, the overall work is O(N).

Right, I forgot about the last part.

--
Brian Dam Pedersen
Software Engineer