PEP 372 -- Adding an ordered directory to collections
ptmcg at austin.rr.com
Tue Jun 17 05:23:13 CEST 2008
On Jun 16, 5:24 pm, "Martin v. Löwis" <mar... at v.loewis.de> wrote:
> > ``odict.byindex(index)``
> > Index-based lookup is supported by ``byindex()`` which returns
> > the key/value pair for an index, that is, the "position" of a
> > key in the ordered dict. 0 is the first key/value pair, -1
> > the last.
> > >>> d.byindex(2)
> > ('foo', 'bar')
> For this API, I think it's important to make some performance
> guarantees. It seems fairly difficult to make byindex O(1), and
> simultaneously also make insertion/deletion better than O(n).
> IOW, the PEP should somehow specify which operations are efficient,
> and which ones aren't.
My guess is that the two main memory allocate/deallocate cases are 1)
appending a new item to the end, and 2) GC'ing the entire data
structure. I would optimize these 2 at the expense of all others.
More information about the Python-list