Python Default Dict | Hacker News Reader

Python Default Dict

docs.python.org

36 pointsjohnjackjames58 comments

Great for expressivity of multi-level dicts (excuse the goofy example):

    state2name2visited = defaultdict(lambda: defaultdict(list))
     state2name2visited[“PA”][“Joe].append(“Pittsburgh”)

You can expand this a bit to make it n-level depth (until you blow the stack).

  def tree():
    return defaultdict(tree)

  >>> t = tree()
  >>> t['a']['b']['c'] = 10
  >>> t
  defaultdict(<function tree at 0x10c40df28>, {'a': 
  defaultdict(<function tree at 0x10c40df28>, {'b': 
  defaultdict(<function tree at 0x10c40df28>, {'c': 10})})})

Reminds me of perl's autovivification, where you can even mix and match dicts, arrays, and scalars:

    $M{hello}[4]{world}[0]++

gives you:

    {
        'hello' => [
            undef,
            undef,
            undef,
            undef,
            {
                'world' => [
                    1
                ]
            }
        ]
    }

This is really cool, I used it to implement a (very) basic trie:

    trie_struct: Callable = lambda: defaultdict(trie_struct)

    trie = trie_struct()

    for word in words:
        ref = trie
        for char in word:
            ref = ref[char]

It won't work with words that substring other words, but its interesting.

Nice! Very expressive way to do n-levels!

Python has too many ways to do it:

    >>> state2name2visited = {}
    >>> state2name2visited.setdefault("PA", {}).setdefault("Joe", []).append("Pittsburgh")
    >>> state2name2visited
    {'PA': {'Joe': ['Pittsburgh']}}

It’s really 2 ways to do it, and the defaultdict way (I believe) would have less allocations in a deeply nested loop (since this version has to create a {} and a [] every time).

Also setdefault causes confusion for less experienced users in a way that the defaultdict format does not.

I came across this once in Peter Norvig's Udacity CS 212 course - I think it was in the discussion forums for one of the lessons. My head promptly exploded.

And here I was thinking you could only pass a type.

oo nice. i haven't seen this before and was doing something similar in a much uglier fashion.

python-box does a pretty good job on this I find.

Here's a little "default dict puzzle" for you. A common use case for default dict is counting the number of occurrences of some string in an input file/stream by providing a default of zero and just incrementing the value for every key you see. But what if you want to use it to count the order in which we see keys, i.e. the first failed lookup initilizes to 1, the second to 2, etc? There are a number of solutions to this, I found 5 that are a few lines each, although a couple of these can be shoehorned into one-liners.

> The most common use case for default dict is counting the number of occurrences of some string

I don't see how you can declare what the most common use of a standard function is, so, uh, citation needed.

> But what if you want to use it to count the order in which we see keys

Don't bother. Since python 3.7 (really 3.6) you can just look at the key order after adding your strings to a normal dict comprehension because dicts are ordered now.

{s: 0 for s in strings}.keys() will give you the order. If you really want a number associated with each, you can wrap that in enumerate.

>I don't see how you can declare what the most common use of a standard function is, so, uh, citation needed.

In a casual discussion you don't formally "declare", you just state something based on your observations and the patterns you see in the wild, that might or might not be true in general.

Similarly, if it's a casual discussion, one can just read "the most common use case" as "a common use case", and just move on to the substance of the parent comment.

OK, a very common use case. As for your second part, yes, that would make my puzzle obsolete, although it's still an interesting exercise in the different ways you can keep state in Python.

Why wouldn't you use Counter for that? https://docs.python.org/3/library/collections.html#collectio...

> Why wouldn't you use Counter for that?

Counters are for counting, not for determining order of discovery.

> Changed in version 3.7: As a dict subclass, Counter Inherited the capability to remember insertion order. Math operations on Counter objects also preserve order. Results are ordered according to when an element is first encountered in the left operand and then by the order encountered in the right operand.

> Changed in version 3.7: As a dict subclass, Counter Inherited the capability to remember insertion order.

Yes but the question as framed ("first failed lookup initilizes to 1, the second to 2, etc") does not require counting the occurrences anymore, so using a counter does more work than necessary. If you want both counts _and_ order, then, yeah, counter is great.

I was replying to this:

> The most common use case for default dict is counting the number of occurrences of some string

I would assume very few people use defaultdict for this since Counter exists.

Despite attempts to depreciate Python 2, there's still a lot of code that hasn't been updated to use all of the new language features since Python 3.1, so it's anybody's guess, really. Depends on how much legacy code you interact with.

Oh, yeah, that's legit. Secretly (not secretly anymore, I guess!) I assume that the OP comment was a school homework assignment or something.

One horribly fragile solution to this depends on global name resolution:

  d = defaultdict(lambda: len(d))

However, it's probably better to avoid defaultdict altogether and implement __missing__ in a subclass of dict.

Most "straightforward" way I could think of:

```

import itertools, collections

cnt = itertools.count(1)

d = collections.defaultdict(lambda: next(cnt))

s = "abcad"

[d[c] for c in s]

```

Oh, this is nice. You can do it in one line (plus imports) with

  d = defaultdict(count().__next__)

Interesting... I wonder if this is vulnerable to getting garbaged collected at any point during execution.

No, the __next__ slot wrapper holds a reference to its associated count object.

  days = {}

  day = '2021-05-05'
  if day not in days:
    days[day] = []
  days[day].append(event)

vs. just

  days = defaultdict(list)

  day = '2021-05-05'
  days[day].append(event)

what a blessing! Thanks for posting this. I do this so often.

Now maybe add an `OrderedDefaultDict`.

  This is the TXR Lisp interactive listener of TXR 257.
  Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet.
  Caution: objects in heap are farther from reality than they appear.
  1> (defun pend (list item) (append list (list item)))
  pend
  2> (define-modify-macro pendto (item) pend)
  pendto
  3> (defvar x)
  x
  4> (pendto x 3)
  (3)
  5> (pendto x 4)
  (3 4)
  6> (defvar days (hash))
  days
  7> (pendto [days "2021-05-01"] 'event0)
  (event0)
  8> (pendto [days "2021-05-01"] 'event1)
  (event0 event1)
  9> (pendto [days "2021-05-01"] 'event2)
  (event0 event1 event2)
  10> days
  #H(() ("2021-05-01" (event0 event1 event2)))
  11> [days "2021-05-01"]
  (event0 event1 event2)

Dictionaries are ordered since, I think, 3.6. I believe this is an implementation detail of CPython, rather than it being “standard” (e.g., I don’t know if you can rely on, say, PyPy respecting that, although I suspect it does.)

In fact it looks like PyPy implemented it first [0], and it was an implementation detail in 3.6, but declared part of the standard in 3.7 [1].

[0]: https://docs.python.org/3.6/whatsnew/3.6.html#new-dict-imple...

[1]: https://docs.python.org/3.7/whatsnew/3.7.html

There's also the `setdefault` method you could use on ordinary dicts:

  -if day not in days:
  -  days[day] = []
  +days.setdefault(day, [])

Interestingly, in Common Lisp,

  (push event (gethash day days))

does this with zero extra effort, since the default value for fetching from a hashtable is NIL. The magic of reasonable defaults... I feel like it's underappreciated sometimes.

If you didn't know that yet, watch Raymond Hettinger's talk "Beautiful and idiomatic python". I consider it mandatory for any professional python programmer.

This post shows up in the same day I was looking exactly at it. Quite interesting.

Another way of avoiding KeyError is using

  dict.get(val, default_val)

I find it a bit cleaner, since you don't have to create a function or import collection.

[1] https://docs.python.org/3/library/stdtypes.html?highlight=di...

> Another way of avoiding KeyError is using dict.get(val, default_val)

Except that

   my_dict = {}
   my_dict[val] = my_dict.get(val, []).append('foo')

doesn't work because list.append() doesn't return anything, while

   my_dict = defaultdict(list)
   my_dict[val].append('foo')

does the right thing.

Defaultdict is sugar for dict.setdefault, not dict.get.

Shouldn't the walrus operator solve this, or did they limit that to conditionals only for some reason?

    (my_dict[val] := my_dict.get(val, [])).append('foo')

Haha, probably. But counterpoints:

1) the walrus operator is stupid

2) the walrus operator is dangerous

3) `(my_dict[val] := my_dict.get(val, [])).append` is the opposite of simpler compared to `my_dict.setdefault(val, []).append` or (cleanestly) just `my_default_dict.append`

That is a very good point! Thank you for raising that.

You may also be interested in `dict.setdefault`. It has the same behavior as above but also sets the value for the key if it was previously missing.

    dict.setdefault(val, default_val)

[1] https://docs.python.org/3/library/stdtypes.html#dict.setdefa...

But of course doing it the way you described is subtly unintuitive because it leads to either (1) duplication of the default value (or the need to pass it around as a constant to every access point) and (2) does not work anywhere the dict is accessed directly like:

    d['foo']

whereas defaultdict handles the default value for you correctly independently of the access method.

IMO defaultdict is ideal for this use case.

This is a simple class but has been a real time saver of not having to check if keys exist all the time.

I use it quite a bit for metadata structures with optional elements so reads will still give something back, even if an empty string or a default value.

You do know about `.get()`, right?

if `a = {'a': 1, 'b': 2}`, and I do `cval = a.get('c', 3)`, `cval` will contain 3.

If I do `cval = a['c']`, I get an exception

Yes, I think this is how default dict is implemented.

The issue here is that the clients have to know the particular default values for each parameter. For me, it was easier to return a defaultdict where the callers didn’t need to know what default value to pass into their gets.

This is one of those things that I always assume other Python developers know about, but often don't.

IMO defaultdicts are kind of dangerous, especially when passed as arguments to other calls that expect a normal dict. Silently returning a default value instead of a raising KeyError can lead to hard-to-find bugs.

I generally prefer to use .setdefault(key, default_value) with regular dicts, as it's much more explicit. If I do use a defaultdict for convenience, I will usually only use it within a limited scope, and if I'm returning it then I'll cast it back to a normal dict to avoid surprising the caller.

> IMO defaultdicts are kind of dangerous, especially when passed as arguments to other calls that expect a normal dict.

A defaultdict is a normal dict[0], its just a space-efficient way of expressing a large normal dict, most of whose keys won’t be accessed.

The default function itself should throw KeyError on values that are logically not in the dict (including, due to Python’s dynamically typed nature, those which are outside of the key domain because of type.) Though in some uses you can skip out on this because its used in a very lonited scope where you know its not going to be indexed improperly.

> I generally prefer to use .setdefault(key, default_value) with regular dicts, as it's much more explicit.

I’m not sure why one would prefer one of those over the other, as they have very different use cases; certainly defaultdict isn’t a great choice for places where .setdefault makes sense, but that’s true in reverse, too.

[0] well, except for the unfortunate .get() behavior; a ReallyDefaultDict where rdd.get(k, default) works more sensibly, returning rdd[k] unless that throws KeyError, and default otherwise, would be better.

> The default function itself should throw KeyError on values that are logically not in the dict (including, due to Python’s dynamically typed nature, those which are outside of the key domain because of type.)

That's not how `defaultdict` works - the key isn't passed to the default factory, so there's no opportunity for it to raise a `KeyError` if the key doesn't "logically belong" in the dict. It's possible to get that sort of behaviour by overriding `__missing__`, but I very rarely see this sort of thing in the wild.

A more typical use case is something like `defaultdict(list)` as a convenient way to build a dict of lists. This is fine within a limited scope where it's obvious to the reader that they are dealing with a defaultdict that has special `__getitem__` semantics, however it's a bad idea to return a defaultdict to a caller who might be expecting a normal dict, and would be surprised that missing keys don't result in KeyErrors.

With `.setdefault(key, default_value)` it's unambiguous what we're trying to achieve - the reader doesn't need to know whether they are dealing with a defaultdict.

> That's not how `defaultdict` works - the key isn't passed to the default factory, so there's no opportunity for it to raise a `KeyError` if the key doesn't "logically belong" in the dict. It's possible to get that sort of behaviour by overriding `__missing__`, but I very rarely see this sort of thing in the wild.

You're right. I was thinking of the how Ruby Hash-with-default works (I forget that you have to override __missing__ to get that with Python because .get() not working consistently with __getitem__ leads me to avoid defaultdict in practice.)

> With `.setdefault(key, default_value)` it's unambiguous what we're trying to achieve

Sure, but that’s only useful where you know the key that is going ro be accessed, which isn’t the use case for passing a “dictionary that can generate an appropriate default for keys that aren’t stored” either up or down a call chain. So while I agree that setdefault is ideal foe that use case, I don’t think it substitutes for a well-designed dictionary-with-default-generator. (Unfortunately, defaultdict doesn’t either, but its at least-usable-but-dangerous in that role, whereas setdefault() fundamentally can’t fill it since it involves situations where thr access is nonlocal to the code that wants the special handling.)

Personally think, ruby got it right where we can pass a lambda with the `key` parameter.

You can with Python, it accepts any callable

I think they're pointing out that the callable should be given the key value. So like, let's say a missing key should be assigned its own value by default. Below I try to do that but the callable doesn't seem to be passed the key.

``` In [22]: foo = defaultdict(lambda k: k)

In [23]: foo[1] --------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-23-5a39798fc62e> in <module> ----> 1 foo[1]

TypeError: <lambda>() missing 1 required positional argument: 'k' ```

I could envision this being useful for using a defaultdict as something like a local cache for something where requests are expensive. Below is how one might want to use it but it'll fail because the lambda is not given the key argument.

``` profiles = defaultdict(lambda p_id: get_profile_from_site(p_id)) ```

Used it all the time in my commercial python jobs. The other common one is namedtuple.

Shout out to the attrs library. If you find yourself using namedtuple a lot, it's worth considering despite it being an external dependency.

https://www.attrs.org/en/stable/

Data Classes, built into Python since 3.7, are like a somewhat simplified version of the attrs library. I use them in most situations where I would have previously used namedtuple.

https://www.python.org/dev/peps/pep-0557/

Learned it from the book “Elements of programming interviews” alongside with namedtuple and few other things

Unnecessary and awkward unless you really need a functional default. Use dict.setdefault for static defaults.

You've got that backwards. If you have a static default, that's what defaultdict is best at. If you need the default to depend on the key and you're the sole consumer of the dict, then you can use getdefault and setdefault -- but you incur the expense of computing that default whether or not you use it. If you need the default to depend on the key, and you can't control the scope that your dict will be used in, or you want to avoid computing the default when it's not needed, do that with a custom __missing__ method.

Reply on news.ycombinator.com