Home Original page

an indexed list - how to do it in python

Alex Martelli alex at magenta.com
Mon Aug 14 11:55:14 EDT 2000 
"Brian Dam Pedersen" <brian.pedersen at mail.danbbs.dk> wrote in message
news:kTRl5.186$NO4.3016248332 at news.euroconnect.net...
    [snip]
> > > > >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.
    [snip]
> > > > 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.

One could, I guess, use a different arrangement.  If data tend to come in
a burst of write-accesses, followed by a burst of read-accesses, then the
new data could just be added at the end, as an 'unsorted' flag is set --
at the first following __getitem__, the sort is performed, the flag reset.

Whether that's an optimization will depend on exact patterns of usage...
a more suitable data structure (which I believe has already been suggested)
might in any case be preferable.


Alex
More information about the Python-list mailing list