改进 fuzzywuzzy - 匹配 2 个列表中的名称

Question

我的要求是找到 2 个列表的匹配名称。第一个列表有 400 个名字，第二个列表有 90000 个名字。我得到了想要的结果，但过程需要超过 35 分钟。很明显，有 2 个 for 循环，因此需要 O(N*N) 次操作，这是瓶颈。我已经删除了两个列表中的重复项。可以帮忙改进一下吗。我检查了许多其他问题，但不知何故无法实现。如果您认为我只是错过了阅读一些已经存在的帖子，请指出这一点。我会尽力理解并复制这一点。

下面是我的代码

from fuzzywuzzy import fuzz
infile=open('names.txt','r')
name=infile.readline()
name_list=[]
while name:
    name_list.append(name.strip())
    name=infile.readline()

print (name_list)

infile2=open('names2.txt','r')
name2=infile2.readline()
name_list2=[]
while name2:
    name_list2.append(name2.strip())
    name2=infile2.readline()

print (name_list2)

response = {}
for name_to_find in name_list:
    for name_master in name_list2:
        if fuzz.ratio(name_to_find,name_master) > 90:
            response[name_to_find] = name_master
            break

for key, value in response.items():
    print ("Key is ->" + key + "  Value is -> " + value)

Answer 1

最明显的方法是使用哈希表。伪代码：

1. 识别较小的列表

2. 基于较小的列表创建哈希表：

   hash1 ={name: 1 for name in name_list}

3. 遍历第二个列表并检查第一个列表中是否存在名称键：

   l = [name for name in name_list2 if name in hash1]

就是这样。您将获得两个列表中都存在的名称列表