在python中找到两个列表之间匹配索引的最快方法？

Question

我有两张单子

listA = ['123', '345', '678']
listB = ['ABC123', 'CDE455', 'GHK678', 'CGH345']

我想找到与listA中每个元素匹配的listB的位置。例如，预期的输出是

0 3 2

其中123出现在listB的第一个元素中，所以result返回0，345出现在listB的第四个位置，所以它是3。注意，两个列表中的元素数量非常大（大约500K个元素），因此for loop太慢。你有什么更快的解决办法吗？这是我的解决方案

for i in range (len(listA)):
    for j in range (len(listB)):
        if listA[i] in listB[j]:
            print ('Postion ', j)

Answer 1

你可以这样试试。我们知道在字典中找到东西是最快的，所以解决方案应该使用字典来完成任务。你知道吗

In [1]: import re                                                                        

In [2]: listA = ['123', '345', '678']                                                    

In [3]: listB = ['ABC123', 'CDE455', 'GHK678', 'CGH345']                                 

In [4]: # Mapping b/w number in listB to related index                                   

In [5]: mapping = {re.sub(r'\D+', '', value).strip(): index for index, value in enumerate(listB)}                                                                         

In [6]: mapping # Print mapping dictionary                                               
Out[6]: {'123': 0, '455': 1, '678': 2, '345': 3}

In [7]: # Find the desired output                                                        

In [8]: output = [mapping.get(item) for item in listA]                                   

In [9]: output                                                                           
Out[9]: [0, 3, 2]

In [10]:   

Attached screenshot »

Answer 2

尝试将列表中的所有元素添加到set()并搜索它。它应该有一个更快的in测试。你知道吗

Answer 3

它本质上取决于您的数据集。如果你有一个足够大的数据集，你需要一个低复杂度的数据集，我建议你研究一下aho corasick algorithm。它的要点是您要预处理listA，这样它就变成了一个trie，其节点包含到trie中当前节点的最长后缀的失败链接。因此，您可以简单地遍历listB的每个单词中的每个字符，并遵循您通过预处理创建的trie。因此，您的复杂性增加了listA的处理时间，而不是成倍增加。你知道吗

作为旁注，这并没有降低动态listA的复杂性