在两个大字典中快速查找匹配键

Question

我正在尝试在两个不同的字典中找到对应的键。每个字典大约有60万个条目。

举个例子：

    myRDP = { 'Actinobacter': 'GATCGA...TCA', 'subtilus sp.': 'ATCGATT...ACT' }
    myNames = { 'Actinobacter': '8924342' }

我想打印出Actinobacter（8924342）的值，因为它与myRDP中的一个值匹配。

以下代码可以运行，但速度非常慢：

    for key in myRDP:
        for jey in myNames:
            if key == jey:
                print key, myNames[key]

我试过以下方法，但总是出现KeyError错误：

    for key in myRDP:
        print myNames[key]

有没有可能有一个用C语言实现的函数可以做到这一点？我在网上搜索过，但似乎没有找到有效的解决方案。

Answer 1

在Python 3中，你可以直接这样做：

myNames.keys() & myRDP.keys()

Answer 2

你可以这样做：

for key in myRDP:
    if key in myNames:
        print key, myNames[key]

你第一次尝试的速度很慢，因为你是在比较myRDP里的每一个键和myNames里的每一个键。用算法的术语来说，如果myRDP有n个元素，而myNames有m个元素，那么这个算法需要进行O(n×m)次操作。对于每个都有60万个元素的情况，这就意味着要进行360,000,000,000次比较！

不过，检查某个特定元素是否是字典的键是很快的——实际上，这就是字典的一个重要特点。从算法的角度来看，key in dict的测试是O(1)，也就是常数时间。所以我的算法只需要O(n)的时间，这样就只需要600,000分之一的时间。

Answer 3

使用集合，因为它们有一个内置的 intersection 方法，这个方法应该会很快：

myRDP = { 'Actinobacter': 'GATCGA...TCA', 'subtilus sp.': 'ATCGATT...ACT' }
myNames = { 'Actinobacter': '8924342' }

rdpSet = set(myRDP)
namesSet = set(myNames)

for name in rdpSet.intersection(namesSet):
    print name, myNames[name]

# Prints: Actinobacter 8924342