PEP 372 -- Adding an ordered directory to collections

[Armin Ronacher]

Martin v. Löwis <martin <at> v.loewis.de> writes:

> 
> > I think I have lost the thread here, sorry. So I explain again what I
> > mean. I think for this data structure it's important to keep all the
> > normal dict operations at the same speed. If you use a C
> > implementation vaguely similar to my pure python recipe you can
> > perform the del in O(1) too, because pairs are joined in (double)
> > linked list. But such data structure is O(n) to find the n-th item
> > inserted into the sequence.
> 
> Right. So byindex(n) would be O(n) then, right? If so, what's the
> purpose of having that method in the first place?
What's the purpose of having list.insert?

> The PEP doesn't give a rationale, but just proposes that the method
> be there. My guess is that it includes it for performance reasons.
> However, I think the PEP (author) is misguided in assuming that
> making byindex() a method of odict, you get better performance than
> directly doing .items()[n] - which, as you say, you won't.
Without byindex the only way to cherry pick an item is either doing
something like

    i = od.iteritems()
    for idx in xrange(offset):
        value = idx.next()
    return value

Or

    return od.items()[offset]

One creates tons of unnecessary method calls, the other creates a full
blown list object just to throw it away later.  Both less than optimal
solutions that can be implemented in a more efficient way on the C
layer where one only has to iterate over the linked list offset times
and return the item.  And iteration for that linked list is most likely
something like "for (n = 0; n != offset; ++n) iter = iter->next".

Regards,
Armin