[Python-Dev] PEP 372 -- Adding an ordered directory to collections ready for pronouncement
Lie Ryan
lie.1296 at gmail.com
Thu Mar 5 05:32:58 CET 2009
Terry Reedy wrote:
> Lie Ryan wrote:
>
>> Isn't ordered dictionary essentially also an "always sorted"
>> container? It is always sorted depending on the order of insertion? I
>> can't see any technical reason why the data structure can't
>> accommodate them both. Can you point me to a discussion on this?
>
> Appending an item at the end of a sequence is O(1), no search required.
> Inserting an item at a random 'sorted' point requires at best an
> O(logN) search. Insertion itself is O(1) to O(N) depending on the
> structure.
Yeah, but with a proper algorithm[1] it is possible to get a O(1) append
(which is the characteristic we want for insertion order dictionary,
while falling back to O(log n) if we explicitly give comparer function
(or comparison key extractor).
[1] The insertion algorithm will test for where to insert from the end
of the list. This way, insertion-order dict will still be O(1) (with an
increased constant), else if custom order is specified insertion it will
be O(n)
#UNTESTED BECAUSE I DON'T HAVE PYTHON CURRENTLY
# Note that it derives from OrderDict
class MyOrderDict(OrderDict):
def __init__(*args, **kwds):
if len(args) > 2:
raise TypeError('expected at most 2 arguments')
if len(args) == 2:
self._cmp, args = args[0], args[1:]
else:
self._cmp = lambda a, b: True
if not hasattr(self, '_keys'):
self._keys = []
self.update(*args, **kwds)
def __setitem__(self, key, value):
if key not in self:
self._key.append(None)
for i, k in enumerate(reversed(self._key)):
i = -i - 1
if self._cmp((k, self[k]), (key, value)):
self._key[i], self._key[i - 1] = k, key
else:
self._key[i] = k
dict.__setitem__(self, key, value)
More information about the Python-Dev
mailing list