字典列表,如何获取:基于一个值的交集和基于另一个值的对称差

2024-03-28 22:15:01 发布

您现在位置:Python中文网/ 问答频道 /正文

假设我有:

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的列表,在这里我们有基于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秒。你知道吗


Tags: inid列表for条目差分解决方案dict
2条回答

试试这个:

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中有多个匹配项,那么这将生成重复的结果。如果你不想保留所有的副本,你可以用集合理解代替。你知道吗

相关问题 更多 >