Merge and sum of two dictionaries
Additional notes based on the answers of georg, NPE, Scott and Havok.
I was trying to perform this action on collections of 2 or more dictionaries and was interested in seeing the time it took for each. Because I wanted to do this on any number of dictionaries, I had to change some of the answers a bit. If anyone has better suggestions for them, feel free to edit.
Here's my test method. I've updated it recently to include tests with MUCH larger dictionaries, and again to include Havok's and Scott's newer methods:
Firstly I used the following data:
import random
x = {'xy1': 1, 'xy2': 2, 'xyz': 3, 'only_x': 100}
y = {'xy1': 10, 'xy2': 20, 'xyz': 30, 'only_y': 200}
z = {'xyz': 300, 'only_z': 300}
small_tests = [x, y, z]
# 200,000 random 8 letter keys
keys = [''.join(random.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(8)) for _ in range(200000)]
a, b, c = {}, {}, {}
# 50/50 chance of a value being assigned to each dictionary, some keys will be missed but meh
for key in keys:
if random.getrandbits(1):
a[key] = random.randint(0, 1000)
if random.getrandbits(1):
b[key] = random.randint(0, 1000)
if random.getrandbits(1):
c[key] = random.randint(0, 1000)
large_tests = [a, b, c]
print("a:", len(a), "b:", len(b), "c:", len(c))
#: a: 100069 b: 100385 c: 99989
Now each of the methods:
from collections import defaultdict, Counter
from functools import reduce
def georg_method(tests):
return {k: sum(t.get(k, 0) for t in tests) for k in set.union(*[set(t) for t in tests])}
def georg_method_nosum(tests):
# If you know you will have exactly 3 dicts
return {k: tests[0].get(k, 0) + tests[1].get(k, 0) + tests[2].get(k, 0) for k in set.union(*[set(t) for t in tests])}
def npe_method(tests):
ret = defaultdict(int)
for d in tests:
for k, v in d.items():
ret[k] += v
return dict(ret)
# Note: There is a bug with scott's method. See below for details.
# Scott included a similar version using counters that is fixed
# See the scott_update_method below
def scott_method(tests):
return dict(sum((Counter(t) for t in tests), Counter()))
def scott_method_nosum(tests):
# If you know you will have exactly 3 dicts
return dict(Counter(tests[0]) + Counter(tests[1]) + Counter(tests[2]))
def scott_update_method(tests):
ret = Counter()
for test in tests:
ret.update(test)
return dict(ret)
def scott_update_method_static(tests):
# If you know you will have exactly 3 dicts
xx = Counter(tests[0])
yy = Counter(tests[1])
zz = Counter(tests[2])
xx.update(yy)
xx.update(zz)
return dict(xx)
def havok_method(tests):
def reducer(accumulator, element):
for key, value in element.items():
accumulator[key] = accumulator.get(key, 0) + value
return accumulator
return reduce(reducer, tests, {})
methods = {
"georg_method": georg_method, "georg_method_nosum": georg_method_nosum,
"npe_method": npe_method,
"scott_method": scott_method, "scott_method_nosum": scott_method_nosum,
"scott_update_method": scott_update_method, "scott_update_method_static": scott_update_method_static,
"havok_method": havok_method
}
I also wrote a quick function find whatever differences there were between the lists. Unfortunately, that's when I found the problem in Scott's method, namely, if you have dictionaries that total to 0, the dictionary won't be included at all because of how Counter() behaves when adding.
Test setup:
- MacBook Pro (15-inch, Late 2016), 2.9 GHz Intel Core i7, 16 GB 2133 MHz LPDDR3 RAM, running macOS Mojave Version 10.14.5
- Python 3.6.5 via IPython 6.1.0
Finally, the results:
Results: Small Tests
for name, method in methods.items():
print("Method:", name)
%timeit -n10000 method(small_tests)
#: Method: georg_method
#: 7.81 µs ± 321 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
#: Method: georg_method_nosum
#: 4.6 µs ± 48.8 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
#: Method: npe_method
#: 3.2 µs ± 24.7 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
#: Method: scott_method
#: 24.9 µs ± 326 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
#: Method: scott_method_nosum
#: 18.9 µs ± 64.8 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
#: Method: scott_update_method
#: 9.1 µs ± 90.7 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
#: Method: scott_update_method_static
#: 14.4 µs ± 122 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
#: Method: havok_method
#: 3.09 µs ± 47.9 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Results: Large Tests
Naturally, couldn't run anywhere near as many loops
for name, method in methods.items():
print("Method:", name)
%timeit -n10 method(large_tests)
#: Method: georg_method
#: 347 ms ± 20 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
#: Method: georg_method_nosum
#: 280 ms ± 4.97 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
#: Method: npe_method
#: 119 ms ± 11 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
#: Method: scott_method
#: 324 ms ± 16.8 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
#: Method: scott_method_nosum
#: 289 ms ± 14.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
#: Method: scott_update_method
#: 123 ms ± 1.94 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
#: Method: scott_update_method_static
#: 136 ms ± 3.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
#: Method: havok_method
#: 103 ms ± 1.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Conclusion
╔═══════════════════════════╦═══════╦═════════════════════════════╗
║ ║ ║ Best of Time Per Loop ║
║ Algorithm ║ By ╠══════════════╦══════════════╣
║ ║ ║ small_tests ║ large_tests ║
╠═══════════════════════════╬═══════╬══════════════╬══════════════╣
║ functools reduce ║ Havok ║ 3.1 µs ║ 103,000 µs ║
║ defaultdict sum ║ NPE ║ 3.2 µs ║ 119,000 µs ║
║ Counter().update loop ║ Scott ║ 9.1 µs ║ 123,000 µs ║
║ Counter().update static ║ Scott ║ 14.4 µs ║ 136,000 µs ║
║ set unions without sum() ║ georg ║ 4.6 µs ║ 280,000 µs ║
║ set unions with sum() ║ georg ║ 7.8 µs ║ 347,000 µs ║
║ Counter() without sum() ║ Scott ║ 18.9 µs ║ 289,000 µs ║
║ Counter() with sum() ║ Scott ║ 24.9 µs ║ 324,000 µs ║
╚═══════════════════════════╩═══════╩══════════════╩══════════════╝
Important. YMMV.
You can perform +, -, &, and | (intersection and union) with collections.Counter().
We can do the following (Note: only positive count values will remain in the dictionary):
from collections import Counter
x = {'both1':1, 'both2':2, 'only_x': 100 }
y = {'both1':10, 'both2': 20, 'only_y':200 }
z = dict(Counter(x)+Counter(y))
print(z)
[out]:
{'both2': 22, 'only_x': 100, 'both1': 11, 'only_y': 200}
To address adding values where the result may be zero or negative, use Counter.update() for addition, and Counter.subtract() for subtraction:
x = {'both1':0, 'both2':2, 'only_x': 100 }
y = {'both1':0, 'both2': -20, 'only_y':200 }
xx = Counter(x)
yy = Counter(y)
xx.update(yy)
dict(xx)
[out]:
{'both2': -18, 'only_x': 100, 'both1': 0, 'only_y': 200}
You didn't say how exactly you want to merge, so take your pick:
x = {'both1': 1, 'both2': 2, 'only_x': 100}
y = {'both1': 10, 'both2': 20, 'only_y': 200}
print {k: x.get(k, 0) + y.get(k, 0) for k in set(x)}
print {k: x.get(k, 0) + y.get(k, 0) for k in set(x) & set(y)}
print {k: x.get(k, 0) + y.get(k, 0) for k in set(x) | set(y)}
Results:
{'both2': 22, 'only_x': 100, 'both1': 11}
{'both2': 22, 'both1': 11}
{'only_y': 200, 'both2': 22, 'both1': 11, 'only_x': 100}