список словарей, как получить: пересечение на основе одного значения и симметричной разности, основанной на другом значении

Допустим, у меня есть:

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

а также

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

Как получить список идентификаторов, где у нас есть пересечение их на основе «id», но симметричная разница на основе b?

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

в настоящее время это мое решение:

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

Я спрашиваю, потому что в настоящее время это самая большая потеря времени в моей программе, я бы хотел, чтобы был какой-то способ сделать это быстрее. Результат ( same_a_different_b ) обычно равен 0 или очень мал, один список имеет около 900 записей, а другой около 1400. В настоящее время он занимает 9 секунд.

Попробуй это:

 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 

Вот один из способов использования списка и 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 . Если вы не хотите хранить все дубликаты, вместо этого вы можете использовать понимание набора.