Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Difference between dictionary and OrderedDict

I am trying to get a sorted dictionary. But the order of the items between mydict and orddict doesn't seem to change.

from collections import OrderedDict

mydict = {'a': 1, 'b': 2, 'c': 3, 'd': 4}

orddict = OrderedDict(mydict)

print(mydict, orddict)

# print items in mydict:
print('mydict')
for k, v in mydict.items():
    print(k, v)

print('ordereddict')
# print items in ordered dictionary
for k, v in orddict.items():
    print(k, v)


# print the dictionary keys
# for key in mydict.keys():
#     print(key)


#  print the dictionary values
# for value in mydict.values():
#     print(value)
like image 600
liv2hak Avatar asked Dec 16 '15 06:12

liv2hak


People also ask

What is an OrderedDict?

An OrderedDict is a dictionary subclass that remembers the order that keys were first inserted. The only difference between dict() and OrderedDict() is that: OrderedDict preserves the order in which the keys are inserted.

When should I use OrderedDict?

Intent signaling: If you use OrderedDict over dict , then your code makes it clear that the order of items in the dictionary is important. You're clearly communicating that your code needs or relies on the order of items in the underlying dictionary.

What is the difference between dict and {}?

As we can see, dict() is obviously slower than {}. Especially, if the dictionary is initialized with many elements, it has a huge impact if your code needs 0.04ms or almost 0.08ms to create your dictionary. Even when you initialize an empty dictionary, it is slower.

Is OrderedDict obsolete?

No it won't become redundant in Python 3.7 because OrderedDict is not just a dict that retains insertion order, it also offers an order dependent method, OrderedDict. move_to_end() , and supports reversed() iteration*.


4 Answers

As of Python 3.7, a new improvement to the dict built-in is:

the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec.

This means there is no real need for OrderedDict anymore 🎉. They are almost the same.


Some minor details to consider...

Here are some comparisons between Python 3.7+ dict and OrderedDict:

from collections import OrderedDict

d = {'b': 1, 'a': 2}
od = OrderedDict([('b', 1), ('a', 2)])

# they are equal with content and order
assert d == od
assert list(d.items()) == list(od.items())
assert repr(dict(od)) == repr(d)

Obviously, there is a difference between the string representation of the two object, with the dict object in more natural and compact form.

str(d)  # {'b': 1, 'a': 2}
str(od) # OrderedDict([('b', 1), ('a', 2)])

As for different methods between the two, this question can be answered with set theory:

d_set = set(dir(d))
od_set = set(dir(od))
od_set.difference(d_set)
# {'__dict__', '__reversed__', 'move_to_end'}  for Python 3.7
# {'__dict__', 'move_to_end'}  for Python 3.8+

This means OrderedDict has at most two features that dict does not have built-in, but work-arounds are shown here:

Workaround for __reversed__ / reversed()

No workaround is really needed for Python 3.8+, which fixed this issue. OrderedDict can be "reversed", which simply reverses the keys (not the whole dictionary):

reversed(od)        # <odict_iterator at 0x7fc03f119888>
list(reversed(od))  # ['a', 'b']

# with Python 3.7:
reversed(d)                    # TypeError: 'dict' object is not reversible
list(reversed(list(d.keys()))) # ['a', 'b']

# with Python 3.8+:
reversed(d)        # <dict_reversekeyiterator at 0x16caf9d2a90>
list(reversed(d))  # ['a', 'b']

To properly reverse a whole dictionary using Python 3.7+:

dict(reversed(list(d.items())))  # {'a': 2, 'b': 1}

Workaround for move_to_end

OrderedDict has a move_to_end method, which is simple to implement:

od.move_to_end('b')  # now it is: OrderedDict([('a', 2), ('b', 1)])

d['b'] = d.pop('b')  # now it is: {'a': 2, 'b': 1}
like image 62
Mike T Avatar answered Sep 22 '22 09:09

Mike T


An OrderedDict preserves the order elements were inserted:

>>> od = OrderedDict()
>>> od['c'] = 1
>>> od['b'] = 2
>>> od['a'] = 3
>>> od.items()
[('c', 1), ('b', 2), ('a', 3)]
>>> d = {}
>>> d['c'] = 1
>>> d['b'] = 2
>>> d['a'] = 3
>>> d.items()
[('a', 3), ('c', 1), ('b', 2)]

So an OrderedDict does not order the elements for you, it preserves the order you give it.

If you want to "sort" a dictionary, you probably want

>>> sorted(d.items())
[('a', 1), ('b', 2), ('c', 3)]
like image 28
Brian Malehorn Avatar answered Sep 22 '22 09:09

Brian Malehorn


Starting with CPython 3.6 and all other Python implementations starting with Python 3.7, the built-in dict is ordered - you get the items out in the order you inserted them. Which makes dict and OrderedDict effectively the same.

The documentation for OrderedDict lists the remaining differences. The most important one is that

  • The equality operation for OrderedDict checks for matching order.

Then there's a few minor practical differences:

  • dict.popitem() takes no arguments, whereas OrderedDict.popitem(last=True) accepts an optional last= argument that lets you pop the first item instead of the last item.
  • OrderedDict has a move_to_end(key, last=True) method to efficiently reposition an element to the end or the beginning. With dicts you can move a key to the end by re-inserting it: mydict['key'] = mydict.pop('key')
  • Until Python 3.8, you could do reversed(OrderedDict()) but reversed({}) would raise a TypeError: 'dict' object is not reversible error because they forgot to add a __reversed__ dunder method to dict when they made it ordered. This is now fixed.

And there are a few under-the-hood differences that might mean that you could get better performance for some specific usecase with OrderedDict:

  • The regular dict was designed to be very good at mapping operations. Tracking insertion order was secondary.
  • The OrderedDict was designed to be good at reordering operations. Space efficiency, iteration speed, and the performance of update operations were secondary.
  • Algorithmically, OrderedDict can handle frequent reordering operations better than dict. This makes it suitable for tracking recent accesses (for example in an LRU cache).

See this great talk from 2016 by Raymond Hettinger for details on how Python dictionaries are implemented.

like image 8
Boris Avatar answered Sep 26 '22 09:09

Boris


Adding on to the answer by Brian, OrderedDict is really great. Here's why:

  • You can use it as simple dict object because it supports equality testing with other Mapping objects like collections.counter.

  • OrderedDict preserves the insertion order as explained by Brian. In addition to that it has a method popitem which returns (key,value) pairs in LIFO order. So, you can also use it as a mapped 'stack'.

You not only get the full features of a dict but also, some cool tricks.

like image 3
xssChauhan Avatar answered Sep 24 '22 09:09

xssChauhan