Применение пользовательских функций к большому списку занимает очень много времени - PullRequest
Новая
       28

Применение пользовательских функций к большому списку занимает очень много времени

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

Проблема:

У меня есть список слов длиной 48 000, и я пытаюсь сгруппировать возможные 4 слова (если они есть, но меньше), которые ближе всего друг к другу. Я получаю помощь от модуля difflib.

У меня было 2 способа сделать это в моей голове. Получите 4 ближайших совпадения, используя difflib.get_close_matches(), или составьте декартово произведение из списка слов и получите оценки по каждому кортежу из списка товаров.

У меня есть код, который работает для небольших списков, но когда длина списка увеличивается (в моем случае 48k), это занимает огромное количество времени. Я ищу масштабируемое решение для этой проблемы.

Код для воспроизведения такого списка: 

import random , string , itertools , difflib
from functools import partial
N = 10
random.seed(123)
words = [''.join(random.choice(string.ascii_lowercase) for i in range(5)) for j in range(10)]

Мои попытки:

1: Создана функция, которая будет возвращать счет после создания декартового произведения. После этого я могу сгруппировать по первому элементу и взять верхний n по своему желанию. 

def fun(x) : return difflib.SequenceMatcher(None,*x).ratio()
products = list(itertools.product(words,words))
scores = list(map(fun,products))

2: Функция, которая напрямую дает наилучшее n (4) совпадений 

f = partial(difflib.get_close_matches , possibilities = words , n=4 , cutoff = 0.4)
matches = list(map(f,words)) #this gives 4 possible matches if presentwords

Это также ожидаемый результат.

Оба работают для небольшого списка, но по мере увеличения размера списка это занимает очень много времени. Поэтому я попытался прибегнуть к многопроцессорной обработке:

Попытка многопроцессорной обработки 1:

Сохранить первую функцию (fun) при попытке 1 в файле py, а затем импортировать ее 

import multiprocessing
pool = multiprocessing.Pool(8)
import fun
if__name__ == '__main__':
    score_mlt_pr = pool.map(fun.fun, products ) #products is the cartesian product same as attempt 1
scores_mlt = list(score_mlt_pr)

попытка многопроцессорной обработки 2:

Использование того же f, что и попытка 2 ранее, но с пулом: 

close_matches = list(pool.map(f,words))

с многопроцессорной обработкой время, затрачиваемое на сокращение, но составляет около 1 часа для комбинации 1000 * 48000 слов.

Надеюсь, я мог бы привести наглядный пример своей проблемы. Пожалуйста, посоветуйте, как я могу ускорить мой код.

1 Ответ

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

Этот подход будет иметь лучшую производительность. 

words = <wordlist>
res = []
while len(words) > 4:
    # get a word from list
    word=words.pop()
    # Find three closest to it
    closest = difflib.get_close_matches(word, possibilities=words, n=3, cutoff=0.4)
    #remove found words from list
    for w in closest:
        words.remove(w)
    #add fourth word to list
    closest.append(word)
    res.append(closest)

Ваши методы возвращают столько групп из 4 слов, сколько слов в исходном списке, но, скорее всего, некоторые из них имеют те же четыре слова. В моем методе каждое слово только один раз во всех списках. Таким образом, с 1000 слов вы получаете 250 списков с четырьмя словами.

Я проверил ваш второй метод со списком 500 слов и списком из 1000 слов. Для 500 слов потребовалось 1.93796 секунд, а для 1000 слов - 7.75168 секунд. Так что время растет в геометрической прогрессии; двойной N вызвал почти в 4 раза более медленный прогон.

При моем подходе список из 500 слов занял 0,2435 секунды, а список из 1000 слов - 0,94891 секунды. Таким образом, двойное N потребовало всего 1,4 раза. Это было исключено, поскольку было меньше итераций (N / 4 против N) и get_closest_matches работает, вероятно, быстрее с меньшими возможностями.

---- EDIT ----

Если необходимо создать словарь, содержащий все слова в списке в качестве ключей. 

res = {}
while len(words) > 4:
    # get a word from list
    word=words.pop()
    # Find three closest to it
    closest = difflib.get_close_matches(word, possibilities=words, n=3, cutoff=0.4)
    #remove found words from list
    for w in closest:
        words.remove(w)
    #add fourth word to list
    closest.append(word)
    #add values to result
    for w in closest:
        res[w] = closest
#If there is some "leftover words", add them to result
for w in words:
    res[w] = words

Теперь в res есть столько элементов в словаре, сколько уникальных слов в списке. Единственная проблема - «качество данных». Поскольку список сокращается во время итераций, у метода get_closest_match появляется все меньше возможностей найти подходящие слова. Так что последние раунды не находят лучших совпадений для слова. С другой стороны, этот метод такой же быстрый, как и предыдущий.

Приемлемый ли результат зависит от того, где вы используете эти данные.

...