Python dictionary anthology

We are starting a series of articles on the topic of data structures in Python, where we'll be also introducing you to the different unique solutions of our users and how they are applying these data structures.

dict

marathon = { 
'sam': 71,
'dean': 95,
'cas': 53,
}

squares = {x: x * x for x in range(6)} 

>>> marathon['cas']
53

>>> squares
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

The dict data type is a builtin dictionary implementation that comprises a collection of items. Python also provides syntactic sugar which helps when you are working with your programs' dictionaries. In the example above you can see how easily new dictionary objects can be defined.

Python dictionary has keys (value pairs) which must be immutable and therefore of a hashable type. A hashable object has a hash value which never changes. Plus, it can be compared to other objects and the equal hashable objects must have the same hash value. Python dicts a highly optimizes so they can retrieve values under the conditions of the key being known.

Python standard dict implementation is great and you can absolutely take take advantage of it. But specialized third-party dictionary implementations are also worth considering, among them skip lists or B-tree based dictionaries.

collections.OrderedDict

>>> import collections 
>>> d = collections.OrderedDict(sam=1, dean=2, cas=3) 

>>> d 
OrderedDict([('sam', 1), ('dean', 2), ('cas', 3)]) 

>>> d['joe'] = 4 
>>> d 
OrderedDict([('sam', 1), ('dean', 2), ('cas', 3), ('joe', 4)]) 

>>> d.keys() 
odict_keys(['sam', 'dean', 'cas', 'joe']) 

collections.OrderedDict is a specialized dict subclass which, if your algorithm requires it to work, you need to import from the collections module, because it's not a builtin part of Python language. The great thing about collections.OrderedDict is that when the keys are added it remembers their insertion order.

And here I want to present two examples of how OrderDict is used in CheckiO Missions. So, one of them is Tommi's Solutions of "Roman Numerals", and another is a very well commented solution from tarjeii for the mission "ADFGVX Cipher".

collections.defaultdict

>>> from collections import defaultdict 
>>> dd = defaultdict(list) 

>>> dd['turtles'].append('Schumacher') 
>>> dd['turtles'].append('Hamilton') 
>>> dd['turtles'].append('Barrichello') 

>>> dd['turtles'] 
['Schumacher', 'Hamilton', 'Barrichello'] 

The defaultdict class returns default values for missing keys. It means that defaultdict gives the caller an opportunity to specify the default before the container is initialized. So, in a case that a requested key cannot be found then the new entry will be created and a KeyError won't be thrown. It's faster than using the get() methods or catching a KeyError exception.

defaultdict is very broadly used on CheckiO. I can dedicate the whole new article just to show you solutions that are using defaultdict. But let's just focus on the two of them for now. The first one is from Sim0000 and the mission "What is wrong with this family?", and the second is from mshuffett and the mission "The Most Wanted Letter".

collections.ChainMap

>>> from collections import ChainMap 
>>> dict1 = {'sam': 1, 'dean': 2} 
>>> dict2 = {'cas': 3, 'joe': 4} 
>>> chain = ChainMap(dict1, dict2) 

>>> chain 
ChainMap({'sam': 1, 'dean': 2}, {'cas': 3, 'joe': 4}) 

>>> chain['cas'] 
3 
>>> chain['sam'] 
1 
>>> chain['missing'] 
KeyError: 'missing' 

collections.ChainMap data structure manages a sequence of dictionaries. The underlying mappings are searched when the values associated with keys have to be found. The list of mappings stored by ChainMap is mutable which means that the new mappings can be added or changed in order. And values can also be set through the ChainMap directly. But only the first mapping of the chain will be affected by the updates, insertions, and deletions.

ChainMap is not used that often on CheckiO. We have only few solutions that have it and almost the half of those solutions are from user pohmelie. One is for the mission "Color Map", and another one is for "Wall Keeper".

types.MappingProxyType

>>> from types import MappingProxyType 
>>> writable = {'dean': 1, 'sam': 2} 
>>> read_only = MappingProxyType(writable) 


>>> read_only['dean'] 
1 
>>> read_only['dean'] = 18 
TypeError: "'mappingproxy' object does not support item assignment" 

>>> writable['dean'] = 35
>>> read_only 
mappingproxy({'dean': 35, 'sam': 2}) 

MappingProxyType is a wrapper for a standard Python dictionary which provides a proxy with a read-only access. It was added in Python 3.3.

So, if you want to, for example, pass a dictionary to another function and return it not changed, this might be very useful. By using MappingProxyType there will be no need to create a full copy of the dictionary to put restrictions.

Right now CheckiO has more than 300 000 solutions, but MappingProxyType hasn't been used. This means that you might be the first to do it. In this article you can read all about the benefits of sharing solutions of CheckiO.

Conclusion

All of these Python dictionary implementations are built into the Python standard library and available for using to make your code clearer and easier to maintain.

If you're choosing which mapping type to use I'd recommend you dict.But they all have their strong sides. The only thing is that it might be better to use only one of these data types in case you have some special requirements.

P.S.

Next time we'll be covering the topic of Array Data Structures. If this article was useful, you can also see the relative ones on itertools part 1 and part 2.