在两个大型词典中查找匹配键并快速完成

Question

我试图在两个不同的词典中找到相应的键.每个都有大约600k条目.

比如说:

    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中实现这样做？我用Google搜索,但似乎没有任何效果.

谢谢.

Answer 1

你可以这样做:

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

你的第一次尝试是缓慢的,因为你是比较每一个与myRDP键每个在myNames关键.在算法术语中,如果myRDP有n个元素而myNames有m个元素,那么该算法将采用O(n × m)运算.每个600k元素,这是360,000,000,000比较!

但是测试特定元素是否是字典的关键字很快 - 实际上,这是字典的定义特征之一.在算法术语中,key in dict测试是O(1)或恒定时间.所以我的算法将花费O(n)时间,这是600,000的时间.

Answer 2

使用集合,因为它们有一个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

Answer 3

在python 3中你可以做到

myNames.keys() & myRDP.keys()

Answer 4

for key in myRDP:
    name = myNames.get(key, None)
    if name:
        print key, name

dict.getNone如果密钥不存在,则返回您为其提供的默认值(在本例中为).

Answer 5

您可以从找到公共密钥然后迭代它们开始.设置操作应该很快,因为它们是用C实现的,至少在现代版本的Python中是这样.

common_keys = set(myRDP).intersection(myNames)
for key in common_keys:
    print key, myNames[key]