CODEWITHSUNDEEP
pythoninsertion-sort
user1767754
user1767754

Reputation: 25094

Dict.setdefault insert sorted into a list

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?

Upvotes: 3

Views: 351

Answers (3)

rocksportrocker
rocksportrocker

Reputation: 7419

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.

Upvotes: 2

Jean-François Fabre
Jean-François Fabre

Reputation: 140168

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)

Upvotes: 1

Alan haha
Alan haha

Reputation: 541

While you can do this, with a helper function:

def list_append(lst, item):
    lst.append(item)
    return lst

a = {}
list_append(a.setdefault("foo", []), 2).sort()
list_append(a.setdefault("foo", []), 1).sort()

But I will definitely recommend you try other data structure, like heapq.

Upvotes: 0

Related Questions