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)
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
