88

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
chancyWu
  • 14,073
  • 11
  • 62
  • 81
  • 4
    As long as you're importing from collections, may as well just use a `Counter`. – Kevin May 20 '15 at 17:51
  • 3
    The default value there is not 1, it's 0. – Matt Ball May 20 '15 at 17:51
  • 4
    Try `ht = defaultdict(lambda: 1) # with default value 1` and delete the preceding `ht = {}` which doesn't accomplish anything since you change the value of `ht` in the next line. – martineau May 20 '15 at 18:01

3 Answers3

136

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.

RoadRunner
  • 25,803
  • 6
  • 42
  • 75
rafaelc
  • 57,686
  • 15
  • 58
  • 82
  • (lambda:0, ht) is just to be callable with 0? – chancyWu May 20 '15 at 17:58
  • That is correct. I edited the post to break it down in more detail – rafaelc May 20 '15 at 18:03
  • Thanks for the answer. Do you know how to make the constant always different? I explain: `defaultdict(lambda: 'string', ht)` will not work as expected because all new keys will share the same instance of `'string'`. How can I provide a copy each time? Note that `defaultdict(lambda: copy.copy('string'), ht)` does not work because `copy` is evaluated only once. – Dr_Zaszuś Jun 23 '20 at 09:46
  • @Dr_Zaszuś I'm sorry, but I don't think I understand your example. Strings are immutable and some are interned, so even if you do `x = "some string"` and `b = copy.copy(x)`, you could still find that `x is b == True`. So it wouldn't really matter in this case to use `copy` or not. Could you explain a little further? – rafaelc Jun 23 '20 at 13:51
  • One challenge with this approach is that the resulting dictionary cannot be pickled. You can convert it to an ordinary dictionary (ht=dict(ht)) and then do it. – Dr Xorile Jun 22 '22 at 02:24
63

I think you can just pass a lambda function that returns 1

from collections import defaultdict

d = defaultdict(lambda: 1)
Asclepius
  • 57,944
  • 17
  • 167
  • 143
Montaro
  • 9,240
  • 6
  • 29
  • 30
6

Equivalent to @Montaro's answer:

def a():
    return 1

d = defaultdict(a)
ran632
  • 1,099
  • 1
  • 12
  • 14