#python #performance #time #long-integer #fuzzywuzzy
#python #Производительность #время #длинное целое число #fuzzywuzzy
Вопрос:
Мое требование — найти совпадающие имена для 2 списков. В одном списке 400 имен, а во втором списке 90000 имен. Я получил желаемый результат, но процесс занимает более 35 минут. Как очевидно, существует 2 цикла for, поэтому требуется O (N * N) операций, что является узким местом. Я удалил дубликаты в обоих списках. Можете ли вы помочь улучшить это. Я проверил много других вопросов, но почему-то не смог реализовать это. Если вы думаете, что я просто пропустил чтение какого-то уже существующего поста, пожалуйста, укажите на это. Я сделаю все возможное, чтобы понять и воспроизвести это.
Ниже приведен мой код
from fuzzywuzzy import fuzz
infile=open('names.txt','r')
name=infile.readline()
name_list=[]
while name:
name_list.append(name.strip())
name=infile.readline()
print (name_list)
infile2=open('names2.txt','r')
name2=infile2.readline()
name_list2=[]
while name2:
name_list2.append(name2.strip())
name2=infile2.readline()
print (name_list2)
response = {}
for name_to_find in name_list:
for name_master in name_list2:
if fuzz.ratio(name_to_find,name_master) > 90:
response[name_to_find] = name_master
break
for key, value in response.items():
print ("Key is ->" key " Value is -> " value)
Комментарии:
1. Проверьте, нет ли дубликатов в name_list и name_list2, и попробуйте удалить их перед циклом и посмотреть, работает ли это.
2. вы хотите, чтобы начальный символ имени совпадал с основным списком. если это так, вы можете ограничить количество циклов второго цикла на основе начального префикса char. создайте словарь на основе начального символа и просто выполните fuzz.ratio в этом ограниченном наборе.
3. @SukumarRdjf Спасибо за предложение. Я уже удалил дубликаты в обоих списках. Я добавлю это и в исходный вопрос.
4. @PariRajaram Не могли бы вы, пожалуйста, пояснить, что вы подразумеваете под «начальным символом». Просто пример. Именем в списке 1 может быть «Эш Джонс» . Вторым списком может быть «Эшли Джонс». Если оценка соответствия больше 90, то она должна вернуть это значение. Я все еще пытаюсь найти правильный результат, но, по сути, я хотел бы, чтобы это работало таким образом.
5. вы могли бы создать словарь (dict), используя один или два начальных символа full_name в качестве ключа и значение в качестве full_name. теперь для каждого слова вам нужно только повторить меньший набор имен в dict[полное имя[:2])] и выполнить fuzzywuzzy.
Ответ №1:
Не зная лежащего в основе алгоритма fuzz , я сомневаюсь, что мы можем многое сделать для сокращения асимптотического времени выполнения. Могут быть некоторые хитрости для удаления явно плохих пар, но, вероятно, не намного больше этого. Другой ответ предполагает, что вы выполняете точное совпадение — и не будет работать для сопоставления нечетких строк.
Что вы можете попробовать сделать, так это попытаться выполнить пакетные вызовы, и надеюсь, что fuzzywuzzy оптимизировал некоторую логику для пакетов в своем process . Что-то вроде
from fuzzywuzzy import process
for name in names400:
matches = filter(lambda x: x[1] > 90, process.extract(name, names90000, limit=90000))
for match_name, score in matches:
response[match_name] = name
Также обратите внимание, что на странице github для fuzzywuzzy упоминается, что использование python levenshtein может ускорить вычисления в 4-10 раз.
Комментарии:
1. @ashwin3086 да, после того, как я покопался в их кодовой базе, это все python, так что ускорения, как при использовании встроенных функций модуля (C code), нет.
2. Спасибо, что предложили Python Levenstein. Это действительно помогло в значительной степени. Теперь это заняло 4 минуты. Приведенный выше метод (с использованием Process) был не очень полезен по сравнению с тем, что я написал.
3. Вот статистика для ЦИКЛА FOR. Время начала — 1551756251.471381 Время окончания — 1551756415.6144588 — 164.1430778503418 секунды —
Ответ №2:
Наиболее очевидный подход — использовать хэш-таблицу. Псевдокод:
- Определить список меньшего размера
-
Создайте хэш-таблицу на основе меньшего списка:
hash1 ={name: 1 for name in name_list} -
Выполните итерацию по второму списку и проверьте, существуют ли ключи имен в первом списке:
l = [name for name in name_list2 if name in hash1]
вот и все. вы получаете список имен, которые существуют в обоих списках
Комментарии:
1. Спасибо за предложение. Позвольте мне попробовать это и обновить результаты. Кстати, я не ищу точное совпадение / проверку наличия в другом списке. Я думаю, я могу изменить условие if, чтобы использовать fuzzywuzzy_sort_ration token_sort_ration . Я попытаюсь изменить это для моего варианта использования.
2. Похоже, это не работает, Джарек, поскольку я не ищу прямого соответствия. Я должен выполнить нечеткое сопоставление, чтобы найти близость.
3. Извините, я думаю, что зациклился на стандартном решении для сопоставления двух списков. Да, это не сработало бы в вашем случае. На самом деле это сложная проблема: en.wikipedia.org/wiki/Approximate_string_matching . Но одной из возможных оптимизаций может быть какой-то этап предварительной компоновки, на котором вы могли бы использовать хеширование для разделения всех строк на группы, которые крайне непохожи друг на друга, и использовать для этого более простую процедуру, такую как группирование на основе диапазонов длин строк, чтобы 10 строк символов не нужно было сравнивать с 5 строками символов и т.д. Просто идея