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 -- http://mail.python.org/mailman/listinfo/python-list