List of dictionaries how to get: intersection based on one value and symmetric difference based on another value

Question

Let's say I have:

dict_listA = [
    {'id':0, 'b':1},
    {'id':1, 'b':2},
    {'id':2, 'b':3},
]

and

dict_listB = [
    {'id':1, 'b':1},
    {'id':2, 'b':3},
    {'id':3, 'b':2},
]

How do I get a list of identifiers where we intersect them based on "id" but a symmetric difference based on b?

same_a_different_b = [
    {'id':1, 'b':2},
]

This is currently my solution:

for d1 in list_dictA:
    same_a_different_b = filter(lambda d2: d2['id'] == d1['id'] and d2['b'] != d1['b'], list_dictB)

I ask, because this is currently the biggest loss of time in my program, I would like to have a way to do it faster. The result ( same_a_different_b) is usually 0 or very small, one list has about 900 entries and the other about 1400. Currently it takes 9 seconds.

Answer 1

:

hashed = {e['id']: e['b'] for e in dict_listB}
same_a_different_b2 = [e for e in dict_listA if e['id'] in hashed and hashed[e['id']] != e['b']]

, O (len (a) + len (b)). , O (len (a) * len (b)).

:

hashed = defaultdict(set)
for e in dict_listB:
    hashed[e['id']].add(e['b'])
same_a_different_b2 = [e for e in dict_listA if e['id'] in hashed and e['b'] not in hashed[e['id']]]

(len (a) == len (b) == 2000):

from collections import defaultdict

import time
from itertools import product

dict_listA = [
    {'id': 0, 'b': 1},
    {'id': 1, 'b': 2},
    {'id': 2, 'b': 3},
    *[{'id': i, 'b': 1} for i in range(10000, 10000 + 2000)]
]

dict_listB = [
    {'id': 1, 'b': 1},
    {'id': 2, 'b': 3},
    {'id': 3, 'b': 2},
    *[{'id': i, 'b': 1} for i in range(20000, 20000 + 2000)]
]

same_a_different_b = [
    {'id': 1, 'b': 2},
]
start_time = time.clock()


def previous_solution():
    new_same_a_different_b = []
    for d1 in dict_listA:
        new_same_a_different_b.extend(filter(lambda d2: d2['id'] == d1['id'] and d2['b'] != d1['b'], dict_listB))
    return new_same_a_different_b


def new_solution():
    hashed = {e['id']: e['b'] for e in dict_listB}
    return [e for e in dict_listA if e['id'] in hashed and hashed[e['id']] != e['b']]


def other_solution():
    return [d1 for d1, d2 in product(dict_listA, dict_listB) if d2['id'] == d1['id'] and d2['b'] != d1['b']]


for func, name in [
    (previous_solution, 'previous_solution'),
    (new_solution, 'new_solution'),
    (other_solution, 'other_solution')
]:
    start_time = time.clock()
    new_result = func()
    print('{:20}: {:.5f}'.format(name, time.clock() - start_time))
    assert new_result, same_a_different_b

:

previous_solution   : 1.06517
new_solution        : 0.00073
other_solution      : 0.60582

Answer 2

itertools.prodcut:

In [41]: from itertools import product
In [42]: [d1 for d1, d2 in product(dict_listA, dict_listB) if d2['id'] == d1['id'] and d2['b'] != d1['b']]
Out[42]: [{'id': 1, 'b': 2}]

, , dict_listB . , .