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:
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?
Alternatively, is there a more applicable data structure for this type of process?
Edit: Timing for small data set added
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}))
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())
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.