an indexed list - how to do it in python

[Alex Martelli]

"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).


Alex