python - How to merge a list of multiple dictionaries into a dictionary of lists?

Question

I have the following list of dictionaries in Python3.x:

list_of_dictionaries = [{0:3523, 1:3524, 2:3540, 4:3541, 5:3542}, 
                        {0:7245, 1:7246, 2:7247, 3:7248, 5:7249, 6:7250},
                        {1:20898, 2:20899, 3:20900, 4:20901, 5:20902}]

In this case, it's a single list with three dictionaries.

I would like to efficiently merge this into a single dictionary with lists as values; here is the correct answer:

correct = {0:[3523, 7245], 1:[3524, 7246, 20898], 2:[3540, 7247, 20899], 
               3:[7248, 20900], 4:[3541, 20901], 5:[3542, 7249, 20902], 6:[7250]}

My first thought was a list comprehension like this:

dict(pair for dictionary in list_of_dictionaries for pair in dictionary.items())

But this is wrong, as it doesn't include lists of values:

{0: 7245, 1: 20898, 2: 20899, 4: 20901, 5: 20902, 3: 20900, 6: 7250}

I'm also worried about how to efficiently as possible create value lists. It may not scale to large lists/large dictionaries either.

How could I accomplish this?

Answer 1

defaultdict

You can use collections.defaultdict. Your dictionary comprehension will never work as you are not defining any lists. This is likely to be more efficient than using a dictionary comprehension, which would involve iterating each dictionary for each unique key.

from collections import defaultdict

dd = defaultdict(list)

for d in list_of_dictionaries:
    for k, v in d.items():
        dd[k].append(v)

Result:

print(dd)

defaultdict(list,
            {0: [3523, 7245],
             1: [3524, 7246, 20898],
             2: [3540, 7247, 20899],
             4: [3541, 20901],
             5: [3542, 7249, 20902],
             3: [7248, 20900],
             6: [7250]})

Dictionary comprehension

A dictionary comprehension is possible but this requires calculating the union of keys and iterating the list of dictionaries for each of these keys:

allkeys = set().union(*list_of_dictionaries)

res = {k: [d[k] for d in list_of_dictionaries if k in d] for k in allkeys}

{0: [3523, 7245],
 1: [3524, 7246, 20898],
 2: [3540, 7247, 20899],
 3: [7248, 20900],
 4: [3541, 20901],
 5: [3542, 7249, 20902],
 6: [7250]}

Time complexity

Consider these terms:

n = sum(map(len, list_of_dictionaries))
m = len(set().union(*list_of_dictionaries))
k = len(list_of_dictionaries)

In this context, the defaultdict solution will have complexity O(n), while the dictionary comprehension will have complexity O(mk), where mk >= n.