根据值合并字典的Python方法

Question

我有两个字典（在Python中），我想根据值来合并它们（而不是根据键）。不过，我现在的方法效率很低，基本上是O(n^2)。有没有更好的办法呢？

在这个例子中，字典的键是整数，值是一个包含5个整数的元组。

谢谢！

举个例子：

字典A: {25: (1, 5, 1, 5), 34: (5, 24, 5, 24)}

字典B: {46: (1, 5, 1, 5), 29: (5, 23, 1, 5)}。

合并后的字典是: {25: (1, 5, 1, 5), 34: (5, 24, 5, 24), 29: (5, 23, 1, 5)}。注意，字典A的第一个元素和字典B的第一个元素的值元组是相同的，所以我们只选择一个。

Answer 1

可能像这样吧？

a = {25: (1, 5, 1, 5), 34: (5, 24, 5, 24)}
b = {46: (1, 5, 1, 5), 29: (5, 23, 1, 5)}

for k, v in b.items ():
    if v not in a.values (): a [k] = v

print (a)

不过我想这还是O(n**2)的复杂度。

补充一下：
对于大型字典，这个方法应该会更快：

c = {}
for k, v in a.items (): c [v] = k
for k, v in b.items (): c [v] = k

c = dict ( (b, a) for a, b in c.items () )
print (c)

Answer 2

对我来说，以下方法有效：

C={v:k for k,v in {v:k for k, v in B.items()+A.items()}.iteritems()}

..这段代码很简洁，可能只需要花费 O(n*log(n)) 的时间，因为它的主要操作就是在字典里插入数据。

Answer 3

我可能会这样做：

from collections import defaultdict

A = {25: (1, 5, 1, 5), 34: (5, 24, 5, 24)}
B = {46: (1, 5, 1, 5), 29: (5, 23, 1, 5)}

vk = defaultdict(list)
sources = A, B
for source in sources:
    for k,v in source.iteritems():
        vk[v].append(k)

out = {v[0]:k for k,v in vk.iteritems()}

这个方法总是会选择sources中最早的键，并生成

>>> out
{25: (1, 5, 1, 5), 34: (5, 24, 5, 24), 29: (5, 23, 1, 5)}

如果你担心内存使用问题，可以修改vk[v].append(k)这一行；现在这个方法会创建一个不必要的中间结构，但我不太确定在发生冲突时应该用什么样的选择逻辑。