Временная сложность для сопоставления и подсчета между двумя списками

Question

n_dicwords = [np.sum([c.lower().count(w.decode('utf-8')) for w in dictionary]) 
               for c in documents] 

Здесь я пытаюсь определить свою функцию времени инженерные вычисления:

Используя эту строку кода, которая проходит через каждый документ и проверяет, является ли или нет, и если да, то сколько его слов также появляется в этом словаре, который у меня есть, он генерирует функцию, называемую n_dicwords. Извините, что я такой noob для теории сложности, я думаю, что сложность времени для создания этой функции O (n * m * w), где n - количество документов, m - количество слов в каждом документе, w - номер слов в словаре. Я прав? И если есть ли способ улучшить это?

Большое вам спасибо! Я очень благодарен за вашу помощь!

Answer 1

Я немного удивлен тем, что конструкция «x in s» в python - это O (n), где n - количество элементов n списка. Итак, ваша оценка правильная. Немного более правильный способ взглянуть на это: поскольку ваш документ или счет в нем не изменяются вообще, важными числами являются общее количество слов, которые необходимо проверить, и длину словаря, против которого они находятся проверено. Очевидно, это вовсе не изменяет количество вычислений, оно просто приводит нас к быстро узнаваемой форме O (m * n).

Возможно, вы можете хранить словарь в бинарном дереве, что уменьшит его до O (log (n)).

Поиск «бинарного дерева python» в Google, мне было интересно, как пакет, называемый «bintrees».

Однако Эрик Вестерас указывает, что структура данных «набор» на основе python является хешированной базой данных и имеет сложность O (1) в среднем случае, а O (n) - в худшем и очень редком дело.

См https://docs.python.org/2/library/stdtypes.html#set

Answer 2

Если код под код не делает любой умный материал ваш анализ сложности должен быть правильным.

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

Для начала ознакомьтесь с Aho-Corasick, который является наиболее часто используемым и работает в линейном времени. В Googling «Aho-Corasick python» появилось несколько различных реализаций, поэтому, хотя я не использовал их лично, я бы подумал, что вам не придется реализовывать сам алгоритм, чтобы использовать его.

Если вам просто нужен ваш код для запуска немного быстрее, и вам не нужно получать лучшую производительность, вы могли бы просто использовать набор для словаря. В python нормальный набор является хэш-множеством, поэтому он имеет постоянный поиск по времени. Тогда вы можете просто проверить каждое слово, если оно находится в словаре.