Python 中针对 50K 项列表的嵌套循环优化

Question

我有一个 csv 文件，其中包含大约 50K 行搜索引擎查询。一些搜索查询是相同的，只是词序不同，例如“查询 A 这是”和“这是查询 A”。

我已经测试过使用 fuzzywuzzy 的 token_sort_ratio 函数来查找匹配的词序查询，效果很好，但是我正在努力解决嵌套循环的运行时问题，并寻找优化技巧。

目前，嵌套 for 循环在我的机器上运行大约需要 60 小时。有谁知道我如何加快速度？

代码如下：

from fuzzywuzzy import fuzz
from fuzzywuzzy import process
import pandas as pd
from tqdm import tqdm

filePath = '/content/queries.csv'

df = pd.read_csv(filePath)

table1 = df['keyword'].to_list()
table2 = df['keyword'].to_list()

data = []

for kw_t1 in tqdm(table1):
  for kw_t2 in table2:
     score = fuzz.token_sort_ratio(kw_t1,kw_t2)
     if score == 100 and kw_t1 != kw_t2:
       data +=[[kw_t1, kw_t2, score]]

data_df = pd.DataFrame(data, columns=['query', 'queryComparison', 'score'])

任何意见，将不胜感激。

谢谢！

Answer 1

由于您要查找的是由相同单词组成的字符串（只是不一定按相同顺序），因此根本不需要使用模糊匹配。您可以改为collections.Counter为每个字符串创建一个频率字典，使用它可以将字符串映射到由其频率字典键控的列表字典下。然后你可以输出长度大于1的字典中的子列表。

由于字典不可散列，因此您可以通过首先将它们转换为键值对元组的冻结集来将它们设为字典的键。

这将代码的时间复杂度从O(n ^ 2)提高到O(n)，同时还避免了执行模糊匹配的开销。

from collections import Counter

matches = {}
for query in df['keyword']:
    matches.setdefault(frozenset(Counter(query.split()).items()), []).append(query)

data = [match for match in matches.values() if len(match) > 1]

演示： https: //replit.com/@blhsing/WiseAfraidBrackets