an indexed list - how to do it in python

[dmost at magna.com.au]

Right. I am trying to reproduce something like the VB Collection class.

Hmm, engaging brain shows me that you are right. My mental trap was
thining that python list insertion is an O(1) operation.

Other posts about keeping an ordered tree or list of keys point to an
alternative.

That way I can have O(logn) insertion and deletion, O(logn) access by
key, and O(1) access by index.

Further thoughts: Python lists have O(n) insertion and deletion anyway,
and have O(1) access by index. All I need to do is figure out an O(1)
access by key, and try not to disturb the O(n) insertion and deletion
too much with renumberings or updates.

In article <Xufl5.145132$Gh.2157843 at news20.bellglobal.com>,
  "Olivier Dagenais" <olivierS.dagenaisP at canadaA.comM> wrote:
> It looks to me like you're trying to reproduce the behaviour of VB's
> collection class.  When I reproduced it, I was using a linked list
(for O(1)
> insertion, but O(n) integer index retrieval) as well as a hash table,
where
> the data of a pair was a reference to a linked list node.
>
> You could use an array for O(n) insertion but O(1) integer index
retrieval,
> but there isn't (as far as I know) a data structure that permits O(1)
> _ordered_ insertion and retrieval.  The closest you get is O(log(n)),
and
> that's using a balanced tree, like AVL...
>
> --
> ----------------------------------------------------------------------
> Olivier A. Dagenais - Carleton University - Computer Science III
>
> <dmost at magna.com.au> wrote in message news:8n3tm2
$jug$1 at nnrp1.deja.com...
> > 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.
> >
> > In my mind, this object would be defined something like this:
> >
> > Class IndexedSequence:
> >     def __init__(self):
> >         self.data = []
> >         self.keys = []
> >         self.index = {}
> >
> >
> > At some point in time, this data structure might look like this:
> > self.data = ["nurk", "bazar"]
> > self.keys = ["fred", "jill"]
> > seld.index = {"fred":0, "jill":1}
> >
> > Operations that append to this data structure operate just fine.
> > The problem is that there is no way to eliminate the renumbering
> > required by insertion or deletion.
> >
> > I could rebuild the index on the next index access operation after
> > insertion or deletion, but this seems overly stupid to me.
> >
> > Given an object and a list to which it belongs, how can I find its
> > position in a list in O(1) operations.
> >
> >
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
>
>


Sent via Deja.com http://www.deja.com/
Before you buy.