Оптимизация подсчета вхождений списка слов в заданной строке (Python)
Я создаю функцию, которая подсчитывает вхождения searched_words в переданной строке. Результатом является словарь с совпадающими словами в качестве ключей и их вхождениями в качестве значений.
Я уже создал функцию, которая выполняет это, но она очень плохо оптимизирована.
def get_words(string, searched_words):
words = string.split()
# O(nm) where n is length of words and m is length of searched_words
found_words = [x for x in words if x in searched_words]
# O(n^2) where n is length of found_words
words_dict = {}
for word in found_words:
words_dict[word] = found_words.count(word)
return words_dict
print(get_words('pizza pizza is very cool cool cool', ['cool', 'pizza']))
# Results in {'pizza': 2, 'cool': 3}
Я попытался использовать функциональность Counter из модели Python collections, но не смог воспроизвести желаемый результат. Кажется, что использование типа данных set также может решить мою проблему оптимизации, но я не знаю, как подсчитывать вхождения слов при использовании наборов.
Ответы 2
Вы правы, думая, что есть хорошее решение с использованием Counter:
from collections import Counter
string = 'pizza pizza is very cool cool cool'
search_words = ['cool', 'pizza']
word_counts = Counter(string.split())
# If you want to get a dict only containing the counts of words in search_words:
search_word_counts = {wrd: word_counts[wrd] for wrd in search_words}
Я знал, что это должно быть что-то вроде этого. Я думаю, что моя проблема заключалась в основном в получении словарной формы из возврата Counter() или word_counts в вашем коде. Спасибо.
@TomBrinner Counter объекты - это словари. Обратите внимание, что это решение по-прежнему полиномиальное, O(M*N). Это можно сделать в O(max(M, N)), если сделать набор из search_words
В качестве альтернативы вы можете создать список значений счетчиков, а затем создать словарь из zip:
def get_words(string, searched_words):
wordlist = string.split()
wordfreq = [wordlist.count(p) for p in searched_words]
return dict(list(zip(searched_words, wordfreq)))
Это короче и убирает дополнительный цикл for и не требует дополнительного импорта, но требует применения dict to list к zip.
Что именно вы пробовали с
Counter? Что такоеsearched_words? В любом случае, используя вышеизложенное, вы могли бы сделатьreturn Counter(found_words). Это линейно, но в целом ваш алгоритм все равно будетO(M*N). Чтобы решить эту проблему, преобразуйтеsearch_wordsвset. Тогда все будет линейно