Блог

Вот мой подход к поиску подстрок в списке, содержащем «фразы», путем поиска по списку, содержащему «слова», и возвращению совпадающих подстрок, которые были найдены в каждом элементе списка, содержащего фразы.

 import re

def is_phrase_in(phrase, text):
    return re.search(r"b{}b".format(phrase), text, re.IGNORECASE) is not None

list_to_search = ['my', 'name', 'is', 'you', 'your']
list_to_be_searched = ['hello my', 'name is', 'john doe doe is last name', 'how are you', 'what is your name', 'my name is jane doe']

to_be_appended = []
for phrase in list_to_be_searched:
    searched = []
    for word in list_to_search:
        if is_phrase_in(word,phrase) is True:
            searched.append(word)
    to_be_appended.append(searched)
print(to_be_appended)

# (desired and actual) output
[['my'],
 ['name', 'is'],
 ['name', 'is'],
 ['you'],
 ['name', 'is', 'your'],
 ['my', 'name', 'is']]
  

Поскольку список ‘words’ (или list_to_search) содержит ~ 1700 слов, а список ‘phrases’ (или list_to_be_searched) — ~ 26561, для завершения кода требуется более 30 минут. Я не думаю, что мой приведенный выше код был реализован с учетом Pythonic способа кодирования и эффективной структуры данных. 🙁

Кто-нибудь может дать несколько советов по оптимизации или сделать это быстрее?

Спасибо!

На самом деле, я написал неправильный пример выше. Что, если ‘list_to_search’ содержит элементы, содержащие более 2 слов?

 import re

def is_phrase_in(phrase, text):
    return re.search(r"b{}b".format(phrase), text, re.IGNORECASE) is not None

list_to_search = ['hello my', 'name', 'is', 'is your name', 'your']
list_to_be_searched = ['hello my', 'name is', 'john doe doe is last name', 'how are you', 'what is your name', 'my name is jane doe']

to_be_appended = []
for phrase in list_to_be_searched:
    searched = []
    for word in list_to_search:
        if is_phrase_in(word,phrase) is True:
            searched.append(word)
    to_be_appended.append(searched)
print(to_be_appended)
# (desired and actual) output
[['hello my'],
 ['name', 'is'],
 ['name', 'is'],
 [],
 ['name', 'is', 'is your name', 'your'],
 ['name', 'is']]
  

Время
1-й способ:

 %%timeit
def is_phrase_in(phrase, text):
    return re.search(r"b{}b".format(phrase), text, re.IGNORECASE) is not None

    list_to_search = ['hello my', 'name', 'is', 'is your name', 'your']
    list_to_be_searched = ['hello my', 'name is', 'john doe doe is last name', 'how are you', 'what is your name', 'my name is jane doe']
to_be_appended = []
for phrase in list_to_be_searched:
    searched = []
    for word in list_to_search:
        if is_phrase_in(word,phrase) is True:
            searched.append(word)
    to_be_appended.append(searched)
#43.2 µs ± 346 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  

2-й метод (понимание вложенного списка и повторный поиск)

 %%timeit
[[j for j in list_to_search if j in re.findall(r"b{}b".format(j), i)] for i in list_to_be_searched]
#40.3 µs ± 454 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  

Время определенно улучшилось, но есть ли более быстрый способ? Или задача генетически медленная, учитывая, что она делает?

Вы можете использовать понимание вложенного списка:

 list_to_search = ['my', 'name', 'is', 'you', 'your']
list_to_be_searched = ['hello my', 'name is', 'john doe doe is last name',
                       'how are you', 'what is your name', 'my name is jane doe']

[[j for j in list_to_search if j in i.split()] for i in list_to_be_searched]

[['my'],
 ['name', 'is'],
 ['name', 'is'],
 ['you'],
 ['name', 'is', 'your'],
 ['my', 'name', 'is']]
  

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

Использование регулярного выражения для каждого элемента в list_to_be_searched , похоже, не привело к увеличению производительности. Но объединение list_to_be_searched в большой блок текста и сопоставление его с шаблоном регулярных выражений, построенным на основе list_to_search , привело к небольшому увеличению производительности:

 In [1]: import re
   ...:
   ...: list_to_search = ['my', 'name', 'is', 'you', 'your']
   ...: list_to_be_searched = ['hello my', 'name is', 'john doe doe is last name', 'how are you', 'what is your name', 'my name is jane doe']
   ...:
   ...: def simple_method(to_search, to_be_searched):
   ...:   return [[j for j in to_search if j in i.split()] for i in to_be_searched]
   ...:
   ...: def regex_method(to_search, to_be_searched):
   ...:   word = re.compile(r'(b(?:'   r'|'.join(to_search)   r')b(?:n)?)')
   ...:   blob = 'n'.join(to_be_searched)
   ...:   phrases = word.findall(blob)
   ...:   return [phrase.split(' ') for phrase in ' '.join(phrases).split('n ')]
   ...:
   ...: def alternate_regex_method(to_search, to_be_searched):
   ...:   word = re.compile(r'(b(?:'   r'|'.join(to_search)   r')b(?:n)?)')
   ...:   phrases = []
   ...:   for item in to_be_searched:
   ...:     phrases.append(word.findall(item))
   ...:   return phrases
   ...:

In [2]: %timeit -n 100 simple_method(list_to_search, list_to_be_searched)
100 loops, best of 3: 23.1 µs per loop

In [3]: %timeit -n 100 regex_method(list_to_search, list_to_be_searched)
100 loops, best of 3: 18.6 µs per loop

In [4]: %timeit -n 100 alternate_regex_method(list_to_search, list_to_be_searched)
100 loops, best of 3: 23.4 µs per loop
  

Чтобы увидеть, как это выполняется при больших входных данных, я использовал 1000 наиболее часто встречающихся слов в английском¹, взятых по одному слову за раз, как list_to_search , и весь текст Дэвида Копперфильда из Project Gutenberg², взятый по одной строке за раз, как list_to_be_searched :

 In [5]: book = open('/tmp/copperfield.txt', 'r ')

In [6]: list_to_be_searched = [line for line in book]

In [7]: len(list_to_be_searched)
Out[7]: 38589

In [8]: words = open('/tmp/words.txt', 'r ')

In [9]: list_to_search = [word for word in words]

In [10]: len(list_to_search)
Out[10]: 1000
  

Вот результаты:

 In [15]: %timeit -n 10 simple_method(list_to_search, list_to_be_searched)
10 loops, best of 3: 31.9 s per loop

In [16]: %timeit -n 10 regex_method(list_to_search, list_to_be_searched)
10 loops, best of 3: 4.28 s per loop

In [17]: %timeit -n 10 alternate_regex_method(list_to_search, list_to_be_searched)
10 loops, best of 3: 4.43 s per loop
  

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