python - python 字典中值之间的交集(更快的方式)

Question

我正在尝试使用两个字典的交集生成一个 txt 文件。我正在搜索，我知道最好的方法是使用键的交集，但是我的字典无法做到这一点。

我的词典示例:

dA = {'1':'aaa','2':'aaa','3':'bbb'}
dB = {'10':'aaa','11':'aaa','12':'bbb'}

这是我在 txt 文件中需要的输出:

1 10
1 11
2 10
2 11
3 12

注意:我的字典每个都有 ~100.000.000 个条目

这是我的代码:

>>> for key, value in da.items():
...     for bkey, bvalue in db.items():
...             if bvalue == value:
...                     print(key, bkey)

Answer 1

一种更快的方法，它产生未排序 输出。

from itertools import product
from collections import defaultdict

da = {'1':'aaa','2':'aaa','3':'bbb'}
db = {'10':'aaa','11':'aaa','12':'bbb'}

def gen_matches():
  map_a = defaultdict(list)
  map_b = defaultdict(list)

  for key, value in da.items():
    map_a[value].append(key)
  for key, value in db.items():
    map_b[value].append(key)

  for key in map_a:
    if key in map_b:
      for x in product(map_a[key], map_b[key]):
        yield x

for match in gen_matches():
  print(match)

输出

('2', '11')
('2', '10')
('1', '11')
('1', '10')
('3', '12')

这是 O(n+m)，这意味着它只需要查看每个字典中的每个元素一次。我们称字典 A 的大小为“n”，字典 B 的大小为“m”。

原来的方法，是O(n*m)。每次查看 A 的一个元素时，您都会查看 B 中的所有其他元素。

因此，您可以通过代入数字来了解这两种方法需要多长时间。如果字典 A 和 B 都包含 1000 个元素，则此版本将花费大约 2000 个时间单位，而原始版本将花费 1,000,000!

Big-O notation是一种估计算法复杂度的方法。我已将您链接到一个很好的初学者指南；不幸的是，维基百科的文章很难读。