Dict.setdefault insert sorted into a list

Question

I'm wondering if there is a way of using a lambda like style to append to a dictionarie's list field sorted.

Example:

a = {}
a.setdefault("foo", []).append(2)
a.setdefault("foo", []).append(1)
{'foo': [2, 1]}

Is there a way of doing an insert in sorted order as using a["foo"].bisect.insort(a, -1), so that I don't need to call sort afterwards?

Answer 1

All you need is in Pythons standard library:

import bisect
from collections import defaultdict


def add(dd, key, value):
    bisect.insort_left(dd[key], value)


a = defaultdict(list)
add(a, "foo", 3)
add(a, "foo", 2)
add(a, "foo", 1)
add(a, "foo", 3)
add(a, "foo", 2)
add(a, "foo", 1)

assert a["foo"] == sorted(a["foo"])
print(a)

if you want a lambda:

add = lambda dd, key, value: bisect.insort_left(dd[key], value)

In terms of performance using sort afterwards runtime should be faster than using bisect.insort_left. In both cases runtime complexity is O(n log n) but function call overhead should result in different absolute run times.

Answer 2

You could use collections.defaultdict instead, with some SortedList implementation (downloaded with pip install sortedcontainers, but there are others):

import collections
from sortedcontainers import SortedList

a = collections.defaultdict(SortedList)
a["foo"].add(2)
a["foo"].add(1)
print(a)

result:

defaultdict(<class 'sortedcontainers.sortedlist.SortedList'>, {'foo': SortedList([1, 2])})

you could override add by append if you have a lot of code to refactor.

note that it also works with setdefault, but more cumbersome:

a = {}
a.setdefault("foo", SortedList()).add(2)
a.setdefault("foo", SortedList()).add(1)

(and doing that on a lot of elements has the disadvantage of creating a SortedList() object just in case the key doesn't exist)