Thursday, October 25, 2012

OrderedDict in python

The dict type in python is not ordered, and it's been a pain, especially when you want to keep the sorted order inside a dictionary. From python 2.7, OrderedDict is supported. Screen Shot 2012 10 25 at 10 57 47 AM This quick example will show you what are the differences.
from collections import *

print 'Regular dictionary:'
d = {}
d['a'] = 'A'
d['b'] = 'B'
d['c'] = 'C'
d['d'] = 'D'
d['e'] = 'E'

for k, v in d.items():
    print k, v

print '\nOrderedDict:'
d = collections.OrderedDict()
d['a'] = 'A'
d['b'] = 'B'
d['c'] = 'C'
d['d'] = 'D'
d['e'] = 'E'

for k, v in d.items():
    print k, v
OrderedItem() keeps the input order, with this you can sort
Regular dictionary:
a A
c C
b B
e E
d D

OrderedDict:
a A
b B
c C
d D
e E
  • OrderedDict() requires import collections.
  • When printing the object, OrderedDict() doesn't show it with '{' and '}'.
You can build OrderedDict() using list (iteration), and you can keep the order now.
d = OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])
for k, v in d.items():
    print k, v
apple 4
banana 3
orange 2
pear 1
Using this, you can get the sorted dictionary. Remembering dict.items() return list, you can sort regular dictionary.
# dictionary sorted by value
d = {'banana': 3, 'apple':4, 'pear': 1, 'orange': 2}
d = OrderedDict(sorted(d.items(), key=lambda t: t[0]))
for k, v in d.items():
    print k, v
d = OrderedDict(sorted(d.items(), key=lambda t: t[1]))
for k, v in d.items():
    print k, v
apple 4
banana 3
orange 2
pear 1

pear 1
orange 2
banana 3
apple 4
sort() method gets a list as an input and returns sorted list, it doesn't modify the original list.
a = [1,2,3,4,-3]
b = sorted(a)
print b
print a
[-3, 1, 2, 3, 4]
[1, 2, 3, 4, -3]
Even you can sort by the length of the index.
d = {'banana': 3, 'apple':4, 'pear': 1, 'orange': 2}
# dictionary sorted by length of the key string
d = OrderedDict(sorted(d.items(), key=lambda t: len(t[0])))
for k, v in d.items():
    print k, v
pear 1
apple 4
orange 2
banana 3
You can get the dict from OrderedDict() as the latter is iterable.
o = OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)])
d = dict(o)
for k, v in d.items():
    print k, v
orange 2
pear 1
apple 4
banana 3

References

1 comment:

  1. If you want to keep a dictionary sorted by key, you should check out the SortedDict type as part of the SortedContainers module. It maintains sorted order automatically and is much faster than rebuilding the dictionary after edits. It's available on PyPI: https://pypi.python.org/pypi/sortedcontainers and is pure-Python but fast-as-C implementations (there's a performance comparison). The project is fully documented with 100% coverage and hours of stress testing. Learn more at http://www.grantjenks.com/docs/sortedcontainers/

    ReplyDelete