交叉两个字典

Question

我正在开发一个反向索引的搜索程序。索引本身是一个字典，其键是术语，值则是它们本身的字典，其中包含短文档，以ID号为键且文本内容为值。

要执行两个术语的“AND”搜索，因此我需要交集它们的倒排列表（字典）。有什么清晰的方法（不一定过于聪明）可以在Python中做到这一点吗？我最开始尝试了使用iter的冗长方式：

p1 = index[term1]  
p2 = index[term2]
i1 = iter(p1)
i2 = iter(p2)
while ...  # not sure of the 'iter != end 'syntax in this case
...

- norman

---

对于p1中的每一个i，如果i也在p2中，则返回{i:dict(p1[i],**p2[i])}。 - mtadd

我的上面的评论将会交集你的术语词典，但是会合并你的发布列表...如果你也想在文档ID号上交集你的发布列表，你可以使用{term:{doc_id:p1[term][doc_id] for doc_id in p1[term] if doc_id in p2[term]} for term in p1 if term in p2}。 - mtadd

你所期望的输出以及输入内容非常不清晰。根据你描述的问题，听起来你有一些嵌套的字典想要进行“交集”操作，但是你接受的答案并没有对嵌套字典进行交集操作，它只是对两个字典的键进行了交集操作。请澄清你的问题并提供一个最小可复现示例。 - Aran-Fey

可能是高效字典键交集的重复问题。 - Aran-Fey

Answer 1

一个鲜为人知的事实是，你不需要构造 set 就可以做到这一点：

Python 3

d1 = {'a': 1, 'b': 2}    
d2 = {'b': 2, 'c': 3}    
print(d1.keys() & d2.keys()) # {'b'}

Python 2

在Python 2中，我们将keys替换为viewkeys。对于values(viewvalues)和items(viewitems)也是如此。

In [78]: d1 = {'a': 1, 'b': 2}

In [79]: d2 = {'b': 2, 'c': 3}

In [80]: d1.viewkeys() & d2.viewkeys()
Out[80]: {'b'}

---

从viewitems的文档中：

In [113]: d1.viewitems??
Type:       builtin_function_or_method
String Form:<built-in method viewitems of dict object at 0x64a61b0>
Docstring:  D.viewitems() -> a set-like object providing a view on D's items

对于较大的 dict，这也比构建 set 然后进行交集操作略微更快：

In [122]: d1 = {i: rand() for i in range(10000)}

In [123]: d2 = {i: rand() for i in range(10000)}

In [124]: timeit d1.viewkeys() & d2.viewkeys()
1000 loops, best of 3: 714 µs per loop

In [125]: %%timeit
s1 = set(d1)
s2 = set(d2)
res = s1 & s2

1000 loops, best of 3: 805 µs per loop

For smaller `dict`s `set` construction is faster:

In [126]: d1 = {'a': 1, 'b': 2}

In [127]: d2 = {'b': 2, 'c': 3}

In [128]: timeit d1.viewkeys() & d2.viewkeys()
1000000 loops, best of 3: 591 ns per loop

In [129]: %%timeit
s1 = set(d1)
s2 = set(d2)
res = s1 & s2

1000000 loops, best of 3: 477 ns per loop

我们这里比较的是纳秒级别的时间，这可能对你有所作用也可能没有。无论如何，你会得到一个“set”，因此使用“viewkeys” /“keys” 可以消除一些混乱。

- Phillip Cloud

---

viewkeys() 函数是“自Python 2.7版本起添加”的。 - Dennis Williamson

不知何故，这种方法的计算速度比 set(d1.keys())＆set(d2.keys()) 稍微慢一点 (~12%)。但是，我不明白为什么会这样。 - Dan

@Dan：即使它（可能）更慢，对我来说它看起来更符合Python的风格。 - Azat Ibrakov

使用未来 (pip install future) 包，以下代码可在 Python 2 和 3 中运行：from future.utils import viewkeys; viewkeys(d1) & viewkeys(d2)。 - teichert

Answer 2

通常，在Python中构建字典的交集时，可以首先使用&运算符计算字典键的集合的交集（在Python 3中，字典键是类似于集合的对象）：

dict_a = {"a": 1, "b": 2}
dict_b = {"a": 2, "c": 3} 

intersection = dict_a.keys() & dict_b.keys()  # {'a'}

在Python 2中，你需要自己将字典的键转换为集合：

keys_a = set(dict_a.keys())
keys_b = set(dict_b.keys())
intersection = keys_a & keys_b

然后，鉴于键的交集，您可以按所需的任何方式构建值的交集。 在这里，您必须做出选择，因为集合交集的概念无法告诉您如果相关的值不同该怎么办。（这可能是为什么Python字典中直接未定义&交集运算符的原因）。

在这种情况下，听起来相同键的值将相等，因此您可以从其中一个字典中选择值：

dict_of_dicts_a = {"a": {"x":1}, "b": {"y":3}}
dict_of_dicts_b = {"a": {"x":1}, "c": {"z":4}} 

shared_keys = dict_of_dicts_a.keys() & dict_of_dicts_b.keys()

# values equal so choose values from a:
dict_intersection = {k: dict_of_dicts_a[k] for k in shared_keys }  # {"a":{"x":1}}

结合值的其他合理方法将取决于字典中值的类型以及它们所代表的内容。例如，您可能还希望对字典的字典共享键的值进行联合。由于字典的并集不取决于其值，因此它是明确定义的，在Python中，您可以使用|运算符来获取它：

# union of values for each key in the intersection:
dict_intersection_2 = { k: dict_of_dicts_a[k] | dict_of_dicts_b[k] for k in shared_keys }

在这种情况下，如果两个字典中键为"a"的值相同，则结果将相同。

- James

---

正如@Aran-Fey在问题下面的评论中指出的那样，这会找到两个字典键的交集，这可能并不等同于两个字典的交集，因为它完全忽略了与键相关联的值。 - martineau

@martineau 相交字典值的概念并不是非常明确 - 如果相交键的值不同，您可能会合理地希望对这些值执行不同的操作。我添加了一些解释这一点的示例。 - James

我认为您的更新是一种改进。顺便说一下，我见过的最直观（并且简洁）的确定交集，并将值考虑在内的方法之一是用户@schwobaseggl的答案，回答了类似的问题。 - martineau

Answer 3

In [1]: d1 = {'a':1, 'b':4, 'f':3}

In [2]: d2 = {'a':1, 'b':4, 'd':2}

In [3]: d = {x:d1[x] for x in d1 if x in d2}

In [4]: d
Out[4]: {'a': 1, 'b': 4}

- emnoor

---

这应该是答案，因为这是唯一一个简单地展示如何获取交集字典而不是键列表的方法。 - Rafe

Answer 4

在Python 3中，您可以使用

intersection = dict(dict1.items() & dict2.items())
union = dict(dict1.items() | dict2.items())
difference = dict(dict1.items() ^ dict2.items())

- dccsillag

---

对于 dict1 = {1: 1, 2:2} 和 dict2 = {2:4, 3:3}，它们的交集为 set()。很可能这不是 OP 所想要的。 - WloHu

@JCode 我不确定我理解了。intersection = dict(...) 将其转换回 dict。此外，我刚刚使用 dict1 = {1: 1, 2: 2} 和 dict2 = {2: 4, 3: 3}（上面的字典）进行了测试，intersection == set() 是 False。它是一个空字典。 - dccsillag

@DCPY 抱歉，我错过了 dict(...)。我的意思是，根据我的示例，结果为空。考虑到 OP 接受的内容和更常见的用例，.items() 的交集除非你要寻找字面上的重复，否则没有太多意义。 - WloHu

在这种情况下，可以安全地假设所有值都是唯一的。然后，使用{v：k for k，v in dict1.items（）}代替dict1，并使用{v：k for k，v in dict2.items（）}代替dict2。如果您想要键或字典的情况，则使用答案中给出的交集和此评论中给出的交集的并集。 - dccsillag

这对于 dict().values() 中的任何类型的值都不起作用。 - Kots

Answer 5

到目前为止，还没有解决交叉N个字典的一般情况的方案。

因此，如果您想处理任意N个字典的交集：

from functools import reduce

def dict_intersection(*dict_list):
    return reduce(lambda a,b: dict(a.items() & b.items()), dict_list)

a = {k:k for k in range(0,5)} # {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
b = {k:k for k in range(2,7)} # {2: 2, 3: 3, 4: 4, 5: 5, 6: 6}
c = {k:k for k in range(3,8)} # {3: 3, 4: 4, 5: 5, 6: 6, 7: 7}

dict_intersection(a,b,c)  # {3:3, 4:4}
# or if you have a list of dicts
dicts = [{k:k for k in range(0+n,5+n)} for n in (0,2,3)] # == [a,b,c]
dict_intersection(*dicts) # {3:3, 4:4}

使用functools.reduce可以在单次迭代列表字典的情况下完成操作，而不是像某些解决方案中需要多次循环。它也不执行任何其他条件语句。

权衡：

将dict_intersection_v1更改为dict_intersection_v2，我们可以看到它对于更大的字典和/或字典列表执行得更快（设计适当的实验来测试哪个因素更大超出了此解决方案的范围）。这种性能提升是由于减少了字典实例化的数量。

def dict_intersection_v1(*dict_list):
    return reduce(lambda a,b: dict(a.items() & b.items()),  dict_list)

def dict_intersection_v2(*dict_list):
    return dict(reduce(lambda a,b: a & b, (d.items() for d in dict_list)))

dict_lst1 = [{k:k for k in range(0+n,5+n)} for n in (0,2,3)] # = [a,b,c]
dict_lst2 = [{k:k for k in range(0,50,n)} for n in range(1,5)]]
dict_lst3 = [{k:k for k in range(0,500,n)} for n in range(40)]
dict_lst4 = [{k:k for k in range(0+n,500+n)} for n in range(400)]

字典列表	键值对数量	字典交集v1	字典交集v2	相对差异
1	15	每次循环808纳秒±4.31纳秒（平均值±7次运行的标准偏差，每次100万次循环）	每次循环821纳秒±0.785纳秒（平均值±7次运行的标准偏差，每次100万次循环）	+1.6%
2	105	每次循环3.14微秒±11.9纳秒（平均值±7次运行的标准偏差，每次10万次循环）	每次循环2.38微秒±5.76纳秒（平均值±7次运行的标准偏差，每次10万次循环）	-24.2%
3	2155	每次循环36.9微秒±61.9纳秒（平均值±7次运行的标准偏差，每次1万次循环）	每次循环25.1微秒±131纳秒（平均值±7次运行的标准偏差，每次1万次循环）	-32.0%
4	200_000	每次循环9.08毫秒±22微秒（平均值±7次运行的标准偏差，每次100次循环）	每次循环4.88毫秒±5.31微秒（平均值±7次运行的标准偏差，每次100次循环）	-46.3%

结果dict_lst1的回归主要是由于每次交集后创建字典和生成器内dict.items()调用的开销不同（以及Python通用函数调用的开销）。

注意：我测试了使用预先计算的dict.items()列表来代替v2实时构建生成器的情况。

我测试了在计时内外传递预先计算的列表，虽然这具有统计学意义，但它仍然小于30微秒和10微秒。如果您想获得更好的性能提升，可以考虑使用其他语言或Cython。

- plunker

Answer 6

好的，这里是Python3中上面代码的通用版本。它优化了使用推导式和类似集合的字典视图，这些方法足够快。

函数可以交叉多个字典，并返回一个包含共同键和每个共同键对应的共同值集合的字典：

def dict_intersect(*dicts):
    comm_keys = dicts[0].keys()
    for d in dicts[1:]:
        # intersect keys first
        comm_keys &= d.keys()
    # then build a result dict with nested comprehension
    result = {key:{d[key] for d in dicts} for key in comm_keys}
    return result

使用示例：

a = {1: 'ba', 2: 'boon', 3: 'spam', 4:'eggs'}
b = {1: 'ham', 2:'baboon', 3: 'sausages'}
c = {1: 'more eggs', 3: 'cabbage'}

res = dict_intersect(a, b, c)
# Here is res (the order of values may vary) :
# {1: {'ham', 'more eggs', 'ba'}, 3: {'spam', 'sausages', 'cabbage'}}

在这里，字典的值必须是可哈希的，如果它们不是，你可以简单地将集合括号 {} 改为列表 [ ]：

result = {key:[d[key] for d in dicts] for key in comm_keys}

- thodnev

---

我正在将一个字典列表传递给函数，但是它出现了错误。我该如何编辑上述函数，以便传递一个字典列表，并获得具有相同键和值的键值对？ - learnningprogramming

@learnningprogramming，希望你已经解决了问题，但对于其他好奇的人：*dicts作为函数参数意味着您需要传递许多参数，而不是它们的列表。如果您有lst = [dict1, dict2, dict3, ...]，则可以使用dict_intersect(dict1, dict2, dict3, ...)或展开列表dict_intersect(*lst)。 - thodnev

Answer 7

通过键和值查找完全交集

d1 = {'a':1}
d2 = {'b':2, 'a':1}
{x:d1[x] for x in d1 if x in d2 and d1[x] == d2[x]}

>> {'a':1}

- soldovskij

Answer 8

您的问题不够精确，无法得出单一答案。

1. 关键交叉点

如果您想从帖子中相交 IDs (感谢James)，请执行以下操作：

common_ids = p1.keys() & p2.keys()

然而，如果您想要迭代文档，您需要考虑哪篇文章具有优先权，我假设它是p1。对于common_ids的文档迭代，collections.ChainMap将非常有用：

from collections import ChainMap
intersection = {id: document
                for id, document in ChainMap(p1, p2)
                if id in common_ids}
for id, document in intersection:
    ...

如果您不想创建单独的intersection字典：

from collections import ChainMap
posts = ChainMap(p1, p2)
for id in common_ids:
    document = posts[id]

2. 项交集

如果您想要交集两篇文章的项，也就是匹配ID和文档，请使用以下代码（感谢DCPY）。但是，这仅在寻找术语中的重复项时才有用。

duplicates = dict(p1.items() & p2.items())
for id, document in duplicates:
    ...

3. 迭代 p1 和 p2。

如果你的意思是通过 "'AND' 搜索" 并使用 iter 来搜索两个帖子，那么再次使用 collections.ChainMap 是迭代多个帖子中 (几乎) 所有项目的最佳方法：

from collections import ChainMap
for id, document in ChainMap(p1, p2):
    ...

- WloHu

Answer 9

def two_keys(term_a, term_b, index):
    doc_ids = set(index[term_a].keys()) & set(index[term_b].keys())
    doc_store = index[term_a] # index[term_b] would work also
    return {doc_id: doc_store[doc_id] for doc_id in doc_ids}

def n_keys(terms, index):
    doc_ids = set.intersection(*[set(index[term].keys()) for term in terms])
    doc_store = index[term[0]]
    return {doc_id: doc_store[doc_id] for doc_id in doc_ids}

In [0]: index = {'a': {1: 'a b'}, 
                 'b': {1: 'a b'}}

In [1]: two_keys('a','b', index)
Out[1]: {1: 'a b'}

In [2]: n_keys(['a','b'], index)
Out[2]: {1: 'a b'}

我建议您将索引更改为

index = {term: {doc_id: doc}}

将两个索引返回，一个用于存储术语，另一个用于存储值。

term_index = {term: set([doc_id])}
doc_store = {doc_id: doc}

这样你就不会存储多个相同数据的副本了

- Aaron Goldman

Answer 10

只需使用一个简单的类将字典实例包装起来，以获取您想要的两个值

class DictionaryIntersection(object):
    def __init__(self,dictA,dictB):
        self.dictA = dictA
        self.dictB = dictB

    def __getitem__(self,attr):
        if attr not in self.dictA or attr not in self.dictB:
            raise KeyError('Not in both dictionaries,key: %s' % attr)

        return self.dictA[attr],self.dictB[attr]

x = {'foo' : 5, 'bar' :6}
y = {'bar' : 'meow' , 'qux' : 8}

z = DictionaryIntersection(x,y)

print z['bar']

- Eric Urban

---

我为什么要写那么多代码？如果我这样做了，我就不会用 Python 编程了，而会使用 Java！ :) - Robert Moskal