-1

我有两个字典（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 的第一个元素具有相同的值元组，因此，我们只选择一个

4

3 回答 3

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)
于 2013-03-03T21:27:14.113 回答
1

我可能会做这样的事情：

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)行；现在它建立了一个不需要的中间结构，但我不完全确定在碰撞情况下正确的选择逻辑应该是什么。

于 2013-03-03T21:28:53.370 回答
1

对我有用的是

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

..这是紧凑的代码，可能只和 .. 一样昂贵O(n*log(n))，因为所做的一切都是在字典中插入。

于 2013-03-03T21:36:46.390 回答