Python data structure for sorted key-value pairs

Question

I have a (fixed) set of keys for which I store a value. I often look up the value for a key and increment or decrement it. A typical dict usage.

x = {'a': 1, 'b': 4, 'c': 3}
x['a'] += 1

Additionally however, just as often as incrementing or decrementing values, I also need to know the key for the i-th largest (or smallest) value. Of course I can do the sorting:

s = sorted(x, key=lambda k:(x[k],k))
s[1] == 'c'

The problem is sorting every time seems rather expensive. Especially because I only increment one item in between sorts. I feel that I could use another data structure better suited for this. A tree perhaps?

Answer 1

You could use blist's sorteddict to keep the values in order. Here's a quick implementation of a dictionary which, when iterated over, returns its keys in order of its values (not really tested intensively):

import collections
from blist import sorteddict

class ValueSortedDict(collections.MutableMapping):
    def __init__(self, data):
        self._dict = {}
        self._sorted = sorteddict()
        self.update(data)

    def __getitem__(self, key):
        return self._dict[key]

    def __setitem__(self, key, value):
        # remove old value from sorted dictionary
        if key in self._dict:
            self.__delitem__(key)
        # update structure with new value
        self._dict[key] = value
        try:
            keys = self._sorted[value]
        except KeyError:
            self._sorted[value] = set([key])
        else:
            keys.add(key)            

    def __delitem__(self, key):
        value = self._dict.pop(key)
        keys = self._sorted[value]
        keys.remove(key)
        if not keys:
            del self._sorted[value]

    def __iter__(self):
        for value, keys in self._sorted.items():
            for key in keys:
                yield key

    def __len__(self):
        return len(self._dict)

x = ValueSortedDict(dict(a=1, b=4, c=3))
x['a'] += 1
print list(x.items())
x['a'] += 10
print list(x.items())
x['d'] = 4
print list(x.items())

This gives:

[('a', 2), ('c', 3), ('b', 4)]
[('c', 3), ('b', 4), ('a', 12)]
[('c', 3), ('b', 4), ('d', 4), ('a', 12)]

Answer 2

You can use OrderDict from collections. Though it is unavailable in old python versions.

from collections import OrderedDict

If you have django installed you can use django.utils.datastructures.SortedDict

Answer 3

Use Operator:

import operator

max(x.iteritems(), key=operator.itemgetter(1))[0]

From Docs:

operator.itemgetter(*items)

Return a callable object that fetches item from its operand using the operand’s getitem() method. If multiple items are specified, returns a tuple of lookup values. For example:

I don't knw if it's the best solution but it works.

Answer 4

why not use a Counter from collections? Then you can use Counter.most_common() to get the sorted list.

>>> from collections import Counter
>>> x = Counter({'a': 1, 'b': 4, 'c': 3})
>>> x['a'] += 1
>>> x.most_common()
[('b', 4), ('c', 3), ('a', 2)]

Answer 5

I think most of the python structures are going to do something similar to what you have done in your example. The only thing I can think of to make it a little more efficient is to keep a sorted list of your keys. That way you only have to sort each time you insert. In your method you have to sort each time you want to access a value by index. Here is an example:

x = {'a': 1, 'b': 4, 'c': 3}
x['a'] += 1

keyList = sorted(x.keys())

print x[keyList[1]]
4

x['e'] = 7
x['j'] = 11
x['d'] = 6
x['h'] = 8

keyList = sorted(x.keys())

print x[keyList[3]]
6
print x[keyList[4]]
7

Hope that helps.