PEP 372 -- Adding an ordered directory to collections

[Paul McGuire]

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.
>
> Regards,
> Martin

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.

-- Paul