根据任意字段查找字典列表的交集

Question

假设我有一个字典列表 l1 和 l2。每个都包含相同格式的词典。我想根据字典的某些字段找到 l1 和 l2 的交集。

例如，设

l1 = [{"key":1, "key2":2}, {"key":1, "key2":0}],
l2 = [{"key":0, "key2":2}].

我想根据 "key2" 将它们相交。所以，l1.intersect(l2) = 2.

如果我没记错的话，我可以按如下方式执行此操作，其复杂度为 O(len(l1) + len(l2))。

d = defaultdict(bool)
for e in l2:
    d[e['key2']] = True
intersection=set()
for e in l1:
    if d[e['key2']]:
        intersection.add(e['key2])

我想知道是否有更好的解决方案，或者我的解决方案是否已经是最优的。

Answer 1

您可以使用集合推导来使这个紧凑。例如，

l1 = [{"key":1, "key2":2}, {"key":3, "key2":4}, {"key":5, "key2":6}, {"key":7, "key2":8}]
l2 = [{"key":0, "key2":2}, {"key":1, "key2":3}, {"key":2, "key2":4}]

key = "key2"
values = {d[key] for d in l1} & {d[key] for d in l2}
print(values)

输出

{2, 4}

您可以通过在函数中进行集合推导来使代码更具可读性，尽管函数调用会使代码在微观上变慢。

def key_set(seq, key):
    return {d[key] for d in seq}

values = key_set(l1, key) & key_set(l2, key)

这种技术可以推广到处理任意数量的列表。

all_lists = (l1, l2)
key = "key2"
values = set.intersection(*({d[key] for d in seq} for seq in all_lists))

根据任意字段查找字典列表的交集

Finding the intersection of a list of dictionaries based on an arbitrary field

python

dictionary

intersection

list