Collapse a list of (dictionary of list) to a single (dictionary of list)

Dems_53341 0
Viewed 290

I have data arriving as dictionaries of lists. In fact, I read in a list of them...

data = [
    {
        'key1': [101, 102, 103],
        'key2': [201, 202, 203],
        'key3': [301, 302, 303],
    },
    {
        'key2': [204],
        'key3': [304, 305],
        'key4': [404, 405, 406],
    },
    {
        'key1': [107, 108],
        'key4': [407],
    },
]

Each dictionary can have different keys.

Each key associates to a list, of variable length.

What I'd like to do is to make a single dictionary, by concatenating the lists that share a key...

desired_result = {
    'key1': [101, 102, 103, 107, 108],
    'key2': [201, 202, 203, 204],
    'key3': [301, 302, 303, 304, 305],
    'key4': [404, 405, 406, 407],
}

Notes:

  • Order does not matter
  • There are hundreds of dictionaries
  • There are dozens of keys per dictionary
  • Totalling hundreds of keys in the result set
  • Each source list contains dozens of items

I can do this, with comprehensions, but it feels very clunky, and it's actually very slow (looping through all the possible keys for every possible dictionary yield more 'misses' than 'hits')...

{
  key: [
    item
      for d in data
        if key in d
      for item in d[key]
  ]
    for key in set(
      key
        for d in data
        for key in d.keys()
    )
}

# TimeIt gives 3.2, for this small data set

A shorter, easier to read/maintain option is just to loop through everything. But performance still sucks (possibly due to the large number of calls to extend(), forcing frequent reallocation of memory as the over-provisioned lists fill-up?)...

from collections import defaultdict
result = defaultdict(list)
for d in data:
  for key, val in d.items():
    result[key].extend(val)

# TimeIt gives 1.7, for this small data set

Is there a better way?

  • more 'pythonic'?
  • more concise?
  • more performant?

Alternatively, is there a more applicable data structure for this type of process?

  • I'm sort of making a hash map
  • Where each entry is guaranteed to have multiple collisions and so always be a list

Edit: Timing for small data set added

  • No timings for real world data, as I don't have access to it from here (err, ooops/sorry...)
dictionary python
4 Answers
res = {}
for d in data:
    for k, v in d.items():
        # Adds `key1` to `res` with empty list, if `key1` is not there yet.
        # Extends list under `key1` with new portion of data contained in `v`.
        res.setdefault(k, []).extend(v)

Result:

{'key1': [101, 102, 103, 107, 108],
 'key2': [201, 202, 203, 204],
 'key3': [301, 302, 303, 304, 305],
 'key4': [404, 405, 406, 407]}

UPDATE: I would like to avoid comparison the performance of setdefault and defaultdict, but there was a dissusion in comments and I did some tests for that particular data, using python 3.10.

TL;DR: Setdefault faster defaultdict about 13% for that particular case.

The testing result:

defaultldict [1.633565943, 1.590108738, 1.6549000220000005, 1.622328843, 1.6121867709999993]
setdefault [1.4336988549999994, 1.4056579070000002, 1.4107502079999996, 1.408643755, 1.433823878]

The code of the test:

import timeit
from collections import defaultdict

data = [
    {
        'key1': [101, 102, 103],
        'key2': [201, 202, 203],
        'key3': [301, 302, 303],
    },
    {
        'key2': [204],
        'key3': [304, 305],
        'key4': [404, 405, 406],
    },
    {
        'key1': [107, 108],
        'key4': [407],
    },
]

def setdefault():
    res = {}
    for d in data:
         for k, v in d.items():
            res.setdefault(k, []).extend(v)

def default():
    res = defaultdict(list)
    for d in data:
        for k, v in d.items():
            res[k].extend(v)

if __name__ == '__main__':
    print('defaultldict', timeit.repeat(stmt=default, repeat=5, number=1000000, globals={'data': data}))
    print('setdefault', timeit.repeat(stmt=setdefault, repeat=5, number=1000000, globals={'data': data}))
user_19813840

Perhaps you could use list comprehension and pandas.

No idea if this is a valid answer, or how it performs but it works, for the small set of example data anyway.

import pandas as pd

data = [
    {
        "key1": [101, 102, 103],
        "key2": [201, 202, 203],
        "key3": [301, 302, 303],
    },
    {
        "key2": [204],
        "key3": [304, 305],
        "key4": [404, 405, 406],
    },
    {
        "key1": [107, 108],
        "key4": [407],
    },
]

dics = [pd.DataFrame.from_dict(el, orient="index") for el in data]

dics_concat = pd.concat(dics).fillna("Empty")
dics_concat["key"] = dics_concat.index
dics_concat = dics_concat.groupby("key").agg(list)

combined = dics_concat.apply(
    lambda row: sorted(
        [item for sublist in row for item in sublist if item != "Empty"]
    ),
    axis=1,
)

print(combined.to_dict())

{'key1': [101, 102.0, 103.0, 107, 108.0], 
 'key2': [201, 202.0, 203.0, 204], 
 'key3': [301, 302.0, 303.0, 304, 305.0], 
 'key4': [404, 405.0, 406.0, 407]}

Without pd.concat.

df = pd.DataFrame(data).fillna("")

combined = df.apply(
    lambda row: sorted(
        [item for sublist in row for item in sublist if item != "Empty"]
    ),
    axis=0,
)

print(combined.to_dict())
user_28500260

I have a solution that seems to achieve good results when the lists in your dictionaries are long. Although it is not the case in your situation I still mention it.

The idea as mentioned in my comments is to use append instead of extend in a first loop and then concatenate all lists in the resulting dictionary using itertools.chain. This is the function chain defined below. I also added @mrvol's code in my answer for comparison.

Here is the code:

import timeit
import itertools
from collections import defaultdict

REPEAT = 5    #  parameter repeat of timeit
NUMBER = 100  #  parameter number of timeit
DICTS = 100   #  number of dictionaries in our data
KEYS = 12     #  size of the dictionaries in our data
LEN = 1_000   #  size of the lists in our dictionaries

data = [
    {
        f'key{x}': [x * 100 + y for y in range(LEN)]
        for x in range(KEYS)
    }
    for _ in range(DICTS)
]


def setdefault():
    res = {}
    for d in data:
         for k, v in d.items():
            res.setdefault(k, []).extend(v)
    return res


def default():
    res = defaultdict(list)
    for d in data:
        for k, v in d.items():
            res[k].extend(v)
    return res


def chain():
    res = dict()
    for d in data:
         for k, v in d.items():
            res.setdefault(k, []).append(v)
    for key in res:
        res[key] = list(itertools.chain.from_iterable(res[key]))
    return res


#  check that all produce the same result
assert chain() == default()
assert setdefault() == default()


if __name__ == '__main__':
    for name, fun in [
            ('default', default),
            ('setdefault', setdefault),
            ('chain', chain)
    ]:
        print(name, timeit.repeat(
            stmt=fun, repeat=REPEAT, number=NUMBER,
            globals={'data': data}
        ))

All tests below have been made with python 3.10.

Here are the results:

default [3.0608591459999843, 2.9533347530000356, 3.204700414999934, 2.934139603999938, 2.854463246000023]
setdefault [2.7814459759999863, 2.801596405000055, 2.796927817000096, 2.797430740999971, 2.795393482999998]
chain [2.336767712999972, 2.33148793700002, 2.3378432869999415, 2.3322470529999464, 2.3312841169999956]

If we increase LEN to 10_000 the difference is more impressive:

default [33.63351462200012, 33.598145768999984, 33.83524595699987, 33.732721158000004, 33.785992579999856]
setdefault [33.658237180000015, 33.51113319399997, 33.25321677000011, 33.23780467200004, 33.467723277999994]
chain [23.47564513400016, 23.542697918999693, 23.520614959999875, 23.498439506000068, 23.582990831999723]

But with LEN=100, the chain function is sligthly slower:

default [0.20926385200004916, 0.23037391399998342, 0.21281876400007604, 0.21195233899993582, 0.21580142600009822]
setdefault [0.22843905199988512, 0.2232434430000012, 0.2187928880000527, 0.22453147500004889, 0.21708852799997658]
chain [0.24585279899997659, 0.23280389700016713, 0.2262972040000477, 0.24113659099998586, 0.2370573980001609]

So, once again, chain should not fit your needs as your lists tend to be small with dozens of items, but I mention this solution for the sake of completeness.

user_20748310

Try using list comprehension with setdefault and extend method

res={}
[[res.setdefault(key,[]).extend(entry[key]) for key in entry] for entry in data]
print(res)

pretty-print

import json
print(json.dumps(res,sort_keys=True, indent=4))

Result:

{
    "key1": [
        101,
        102,
        103,
        107,
        108
    ],
    "key2": [
        201,
        202,
        203,
        204
    ],
    "key3": [
        301,
        302,
        303,
        304,
        305
    ],
    "key4": [
        404,
        405,
        406,
        407
    ]
}
user_172234020
Related