defaultdict with default value 1?

chancyWu picture chancyWu · May 20, 2015 · Viewed 46.4k times · Source

I am new to python, and i read some code snippet from some place. It's an implementation of counting sort.

The code is as below:

from collections import defaultdict
def sort_colors(A):
    ht = {}                        # a hash map
    ht = defaultdict(lambda:0, ht) # with default value 1
    for i in A:
         ht[i] += 1
    ret = []
    for k in [0, 1, 2]:
        ret.extend([k]*ht[k])
    return ret

As in the first two lines of the func, it's

ht = {}
ht = defaultdict(lambda:0, ht)

I am not quite clear about this initialization.Could you kindly help me figure it out? and also, Shall we just replace these two lines with following?

ht = defaultdict(int) # default value 0

Answer

rafaelc picture rafaelc · May 20, 2015

Short answer (as per Montaro's answer below)

defaultdict(lambda:1)

Long answer on how defaultdicts work

ht = {}
ht = defaultdict(lambda:0, ht)

defaultdicts are different from dict in that when you try to access a regular dict with a key that does not exists, it raises a KeyError.
defaultdict, however, doesn't raise an error: it creates the key for you instead. With which value? With the return of the callable you passed as an argument. In this case, every new keys will be created with value 0 (which is the return of the simple lambda function lambda:0), which also happens to be the same return of int() , so in this case, there would be no difference in changing the default function to int().

Breaking down this line in more detail: ht = defaultdict(lambda:0, ht)

The first argument is a function, which is a callable object. This is the function that will be called to create a new value for an inexistent key. The second argument, ht is optional and refers to the base dictionary that the new defaultdict will be built on. Therefore, if ht had some keys and values, the defaultdict would also have these keys with the corresponding values. If you tried to access these keys, you would get the old values. However, if you did not pass the base dictionary, a brand new defaultdict would be created, and thus, all new keys accessed would get the default value returned from the callable.
(In this case, as ht is initially an empty dict, there would be no difference at all in doing ht = defaultdict(lambda:0) , ht = defaultdict(int) or ht = defaultdict(lambda:0, ht) : they would all build the same defaultdict.