• 14

A PHP Error was encountered

Severity: Notice

Message: Undefined index: userid

Filename: views/question.php

Line Number: 191


File: /home/prodcxja/public_html/questions/application/views/question.php
Line: 191
Function: _error_handler

File: /home/prodcxja/public_html/questions/application/controllers/Questions.php
Line: 433
Function: view

File: /home/prodcxja/public_html/questions/index.php
Line: 315
Function: require_once

name Punditsdkoslkdosdkoskdo

Key-ordered dict in Python

I am looking for a solid implementation of an ordered associative array, that is, an ordered dictionary. I want the ordering in terms of keys, not of insertion order.

More precisely, I am looking for a space-efficent implementation of a int-to-float (or string-to-float for another use case) mapping structure for which:

  • Ordered iteration is O(n)
  • Random access is O(1)

The best I came up with was gluing a dict and a list of keys, keeping the last one ordered with bisect and insert.

Any better ideas?

      • 1
    • And you can't just do the conversion as required? You need to cache the results for later? And the performance requirements are needed because this has been found to be a bottleneck?
    • Well, I did not gave the context, sorry. I have something like 10 000 structures like that in memory. Each of them contain between 10 and 5 000 key/value pairs. Depending on the pattern, either I look for one precise key for each of the mappings, or I apply some function on it, which is dependant on the order. I cannot precalculate the results, as they depend on user input. Profiling showed that sorting the dict was really a bottleneck.
      • 1
    • I have to change the contents based on user input. Approx 70% of the times it is just a matter of appending a key (the last in order), but it happens sometimes that I have to insert / delete a medium one.

"Random access O(1)" is an extremely exacting requirement which basically imposes an underlying hash table -- and I hope you do mean random READS only, because I think it can be mathematically proven than it's impossible in the general case to have O(1) writes as well as O(N) ordered iteration.

I don't think you will find a pre-packaged container suited to your needs because they are so extreme -- O(log N) access would of course make all the difference in the world. To get the big-O behavior you want for reads and iterations you'll need to glue two data structures, essentially a dict and a heap (or sorted list or tree), and keep them in sync. Although you don't specify, I think you'll only get amortized behavior of the kind you want - unless you're truly willing to pay any performance hits for inserts and deletes, which is the literal implication of the specs you express but does seem a pretty unlikely real-life requirement.

For O(1) read and amortized O(N) ordered iteration, just keep a list of all keys on the side of a dict. E.g.:

class Crazy(object):
  def __init__(self):
    self.d = {}
    self.L = []
    self.sorted = True
  def __getitem__(self, k):
    return self.d[k]
  def __setitem__(self, k, v):
    if k not in self.d:
      self.sorted = False
    self.d[k] = v
  def __delitem__(self, k):
    del self.d[k]
  def __iter__(self):
    if not self.sorted:
      self.sorted = True
    return iter(self.L)

If you don't like the "amortized O(N) order" you can remove self.sorted and just repeat self.L.sort() in __setitem__ itself. That makes writes O(N log N), of course (while I still had writes at O(1)). Either approach is viable and it's hard to think of one as intrinsically superior to the other. If you tend to do a bunch of writes then a bunch of iterations then the approach in the code above is best; if it's typically one write, one iteration, another write, another iteration, then it's just about a wash.

BTW, this takes shameless advantage of the unusual (and wonderful;-) performance characteristics of Python's sort (aka "timsort"): among them, sorting a list that's mostly sorted but with a few extra items tacked on at the end is basically O(N) (if the tacked on items are few enough compared to the sorted prefix part). I hear Java's gaining this sort soon, as Josh Block was so impressed by a tech talk on Python's sort that he started coding it for the JVM on his laptop then and there. Most sytems (including I believe Jython as of today and IronPython too) basically have sorting as an O(N log N) operation, not taking advantage of "mostly ordered" inputs; "natural mergesort", which Tim Peters fashioned into Python's timsort of today, is a wonder in this respect.

  • 29
Reply Report
      • 2
    • I have almost exactly the same thing, but with __setitem__(self, k, v): if not k in self.d: idx = bisect.bisect(self.l, k) # log(n) self.l.insert(idx, k) # keeps the list sorted self.d[k] = v That prevents the "dirty" flag thing. Is there a paper describing in detail python sort precisely (if not, I will read source code). But my question was really about a trick to prevent the duplication of the key list (for example, if hash are short, it may be preferable to duplicate only the hashs instead of longs). Thanks for the insight on python sort, though.
    • How about if (1) eliminate self.sorted (2) self.L == None if not sorted (3) self.L is generated from keys in iter__() (4) __setitem invalidates self.L, setting it to None?
      • 1
    • Nice idea! If I have a probability p of doing an insertion between two iterations, that would reduce the constant before the iteration (which will still be O (n log n)) by the same factor. As an added benefit, if I can prove that my updates are sufficently uniformly distributed amongst my series (and given the garbage collector collects often enough, the average additional memeroy load will only be (1-p) * load of one serie (but I fear a bit the garbage collection cost). Need to study it the patterns more closely. Thanks !
      • 2
    • There's a .txt file in the python sources that's a very nice essay by Tim Peters about his sorting algorithm; sorry, can't find the URL right now as I'm on my phone, no wifi. Key point here is that appending one item to a sorted list and sorting again is o(n), like bisect then insert, and asymptotically better if m much less than n items are appended between sorts, which I hope explains why the code I propose shd be better than the alternatives mentioned in the comments.

The sortedcontainers module provides a SortedDict type that meets your requirements. It basically glues a SortedList and dict type together. The dict provides O(1) lookup and the SortedList provides O(N) iteration (it's extremely fast). The whole module is pure-Python and has benchmark graphs to backup the performance claims (fast-as-C implementations). SortedDict is also fully tested with 100% coverage and hours of stress. It's compatible with Python 2.6 through 3.4.

  • 9
Reply Report

Here is my own implementation:

import bisect
class KeyOrderedDict(object):
   __slots__ = ['d', 'l']
   def __init__(self, *args, **kwargs):
      self.l = sorted(kwargs)
      self.d = kwargs

   def __setitem__(self, k, v):
      if not k in self.d:
         idx = bisect.bisect(self.l, k)
         self.l.insert(idx, k)
       self.d[k] = v

   def __getitem__(self, k):
      return self.d[k]

   def __delitem__(self, k):
      idx = bisect.bisect_left(self.l, k)
      del self.l[idx]
      del self.d[k]

   def __iter__(self):
      return iter(self.l)

   def __contains__(self, k):
      return k in self.d

The use of bisect keeps self.l ordered, and insertion is O(n) (because of the insert, but not a killer in my case, because I append far more often than truly insert, so the usual case is amortized O(1)). Access is O(1), and iteration O(n). But maybe someone had invented (in C) something with a more clever structure ?

  • 5
Reply Report

An ordered tree is usually better for this cases, but random access is going to be log(n). You should keep into account also insertion and removal costs...

  • 4
Reply Report

You could build a dict that allows traversal by storing a pair (value, next_key) in each position.

Random access:

my_dict[k][0]   # for a key k


k = start_key   # stored somewhere
while k is not None:     # next_key is None at the end of the list
    v, k = my_dict[k]
    yield v

Keep a pointer to start and end and you'll have efficient update for those cases where you just need to add onto the end of the list.

Inserting in the middle is obviously O(n). Possibly you could build a skip list on top of it if you need more speed.

  • 1
Reply Report
      • 2
    • Obviously, you can store a pointer to the previous element also, which would make insertion/deletion from the middle easier, especially if you do layer a skip list on top.

I'm not sure which python version are you working in, but in case you like to experiment, Python 3.1 includes and official implementation of Ordered dictionaries: http://www.python.org/dev/peps/pep-0372/ http://docs.python.org/3.1/whatsnew/3.1.html#pep-372-ordered-dictionaries

  • 1
Reply Report
      • 2
    • Ordered dictionaries are ordered with respect to key insertion, not key sort order, so I don't think the LeMiz will be able to use this solution.

The ordereddict package ( http://anthon.home.xs4all.nl/Python/ordereddict/ ) that I implemented back in 2007 includes sorteddict. sorteddict is a KSO ( Key Sorted Order) dictionary. It is implemented in C and very space efficient and several times faster than a pure Python implementation. Downside is that only works with CPython.

>>> from _ordereddict import sorteddict
>>> x = sorteddict()
>>> x[1] = 1.0
>>> x[3] = 3.3
>>> x[2] = 2.2
>>> print x
sorteddict([(1, 1.0), (2, 2.2), (3, 3.3)])
>>> for i in x:
...    print i, x[i]
1 1.0
2 2.2
3 3.3

Sorry for the late reply, maybe this answer can help others find that library.

  • 1
Reply Report

here's a pastie: I Had a need for something similar. Note however that this specific implementation is immutable, there are no inserts, once the instance is created: The exact performance doesn't quite match what you're asking for, however. Lookup is O(log n) and full scan is O(n). This works using the bisect module upon a tuple of key/value (tuple) pairs. Even if you can't use this precisely, you might have some success adapting it to your needs.

import bisect

class dictuple(object):
        >>> h0 = dictuple()
        >>> h1 = dictuple({"apples": 1, "bananas":2})
        >>> h2 = dictuple({"bananas": 3, "mangoes": 5})
        >>> h1+h2
        ('apples':1, 'bananas':3, 'mangoes':5)
        >>> h1 > h2
        >>> h1 > 6
        >>> 'apples' in h1
        >>> 'apples' in h2
        >>> d1 = {}
        >>> d1[h1] = "salad"
        >>> d1[h1]
        >>> d1[h2]
        Traceback (most recent call last):
        KeyError: ('bananas':3, 'mangoes':5)

    def __new__(cls, *args, **kwargs):
        initial = {}
        args = [] if args is None else args
        for arg in args:

        instance = object.__new__(cls)
        instance.__items = tuple(sorted(initial.items(),key=lambda i:i[0]))
        return instance

    def __init__(self,*args, **kwargs):

    def __find(self,key):
        return bisect.bisect(self.__items, (key,))

    def __getitem__(self, key):
        ind = self.__find(key)
        if self.__items[ind][0] == key:
            return self.__items[ind][1]
        raise KeyError(key)
    def __repr__(self):
        return "({0})".format(", ".join(
                          for item in self.__items))
    def __contains__(self,key):
        ind = self.__find(key)
        return self.__items[ind][0] == key
    def __cmp__(self,other):

        return cmp(self.__class__.__name__, other.__class__.__name__
                  ) or cmp(self.__items, other.__items)
    def __eq__(self,other):
        return self.__items == other.__items
    def __format__(self,key):
    #def __ge__(self,key):
    #    pass
    #def __getattribute__(self,key):
    #    pass
    #def __gt__(self,key):
    #    pass
    __seed = hash("dictuple")
    def __hash__(self):
        return dictuple.__seed^hash(self.__items)
    def __iter__(self):
        return self.iterkeys()
    def __len__(self):
        return len(self.__items)
    #def __reduce__(self,key):
    #    pass
    #def __reduce_ex__(self,key):
    #    pass
    #def __sizeof__(self,key):
    #    pass

    def fromkeys(cls,key,v=None):

    def get(self,key, default):
        ind = self.__find(key)
        return self.__items[ind][1] if self.__items[ind][0] == key else default

    def has_key(self,key):
        ind = self.__find(key)
        return self.__items[ind][0] == key

    def items(self):
        return list(self.iteritems())

    def iteritems(self):
        return iter(self.__items)

    def iterkeys(self):
        return (i[0] for i in self.__items)

    def itervalues(self):
        return (i[1] for i in self.__items)

    def keys(self):
        return list(self.iterkeys())

    def values(self):
        return list(self.itervalues())
    def __add__(self, other):
        _sum = dict(self.__items)
        return self.__class__(_sum)

if __name__ == "__main__":
    import doctest
  • 0
Reply Report

For "string to float" problem you can use a Trie - it provides O(1) access time and O(n) sorted iteration. By "sorted" I mean "sorted alphabetically by key" - it seems that the question implies the same.

Some implementations (each with its own strong and weak points):

  • 0
Reply Report

Here's one option that has not been mentioned in other answers, I think:

  • Use a binary search tree (Treap/AVL/RB) to keep the mapping.
  • Also use a hashmap (aka dictionary) to keep the same mapping (again).

This will provide O(n) ordered traversal (via the tree), O(1) random access (via the hashmap) and O(log n) insertion/deletion (because you need to update both the tree and the hash).

The drawback is the need to keep all the data twice, however the alternatives which suggest keeping a list of keys alongside a hashmap are not much better in this sense.

  • 0
Reply Report

Trending Tags