уменьшить временную сложность вложенного l oop in python - PullRequest
Новая
       19

уменьшить временную сложность вложенного l oop in python

1 голос
/ 29 апреля 2020

вот мой код. для завершения требуется 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))

Я пробовал разные, но не работал ((.

набор данных1 - 10krows , dataset2 - 1M строк, fuzz.token_sort_ratio (x, y) - это функция, которая принимает 2 параметра (2 строки) и выводит целое число - сходство этих 2 строк

1 Ответ

1 голос
/ 29 апреля 2020

Поскольку в данном случае датафрейм на самом деле не используется, я просто буду работать со следующими двумя списками: 

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))
...