时间戳

首页 > 解决方案 > 减少python中嵌套循环的时间复杂度

python - 减少python中嵌套循环的时间复杂度

问题描述

这是我的代码。需要 17 小时才能完成。您能否建议任何替代代码来减少计算时间？

# test algorithm1 - fuzzy
matched_pair = []
for x in dataset1['full_name_eng']:
    for y in dataset2['name']:
        if (fuzz.token_sort_ratio(x,y) > 85):
            matched_pair.append((x,y))
            print((x,y))

我尝试了不同的但没有工作（（。

dataset1 - 10krows，dataset2 - 1M 行，fuzz.token_sort_ratio(x,y) - 是一个接受 2 个参数（2 个字符串）并输出整数的函数 - 这 2 个字符串的相似度

标签： pythontime-complexity

解决方案

由于此处并未真正使用数据框，因此我将简单地使用以下两个列表：

import string
import random

random.seed(18)
dataset1 = [''.join(random.choice(string.ascii_lowercase + ' ') for _ in range(random.randint(13, 20))) for s in range(1000)]
dataset2 = [''.join(random.choice(string.ascii_lowercase + ' ') for _ in range(random.randint(13, 20))) for s in range(1000)]

将这两个列表与您使用fuzzywuzzy 提供的代码一起使用。作为第一个更改，您可以使用RapidFuzz（我是作者），它与 FuzzyWuzzy 基本相同，但速度要快得多。当使用我的测试列表时，这大约是您的代码的 7 倍。另一个问题是，当使用 fuzz.token_sort_ratio 时，字符串总是小写，例如标点符号被删除。虽然这对字符串匹配有意义，但您对列表中的每个字符串都执行多次，这在处理更大的列表时会累加。在这些列表中，仅使用一次 RapidFuzz 和预处理大约是 14 倍。

from rapidfuzz import fuzz, utils

dataset2_processed = [utils.default_process(x) for x in dataset2]
dataset1_processed = [utils.default_process(x) for x in dataset1]

matched_pair = []
for word1, word1_processed in zip(dataset1, dataset1_processed):
    for word2, word2_processed in zip(dataset2, dataset2_processed):
        if fuzz.token_sort_ratio(word1_processed, word2_processed, processor=None, score_cutoff=85):
            matched_pair.append((word1, word2))

推荐阅读