Устанавливает против Regex для поиска строк, который является более масштабируемым?

Question

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

Вариант I (регулярное выражение)

>>> import re 
>>> s = re.compile("|".join(big_list)) 
>>> len(s.find_all(sentence)) 

Вариант II (наборы)

>>> s = set(big_list) 
>>> len([word for word in sentence.split(" ") if word in s]) # O(1) avg lookup time 

Пример: если список [ "кошка", "собака", "колено"] и текст «собака прыгнула над котом, но собака сломала ему колено», конечный результат должен быть: 4

PS Любая другая опция приветствуется

Answer 1

Если ваши слова являются буквенно-цифровыми, я мог бы использовать что-то вроде:

s = set(big_list) 
sum(1 for x in re.finditer(r'\b\w+\b',sentence) if x.group() in s) 

Поскольку проверка принадлежности для набора в среднем O (1), этот алгоритм становится O (N + M), где N является количество слов в предложении и M - количество элементов в big_list. Не слишком потертый. Это также очень хорошо с точки зрения использования памяти.

Answer 2

Масштабируемый метод будет сортировать входной словарь и слова из текста, а затем выполнять сопоставление с использованием двух итераторов. Вы также можете использовать use a trie для лучшей производительности. Я не знаю внутреннего представления набора, однако использование большого регулярного выражения было бы полным избытком.