Производительность - Самый быстрый способ сравнить 2 больших списка строк в Python

Question

У меня есть списки Python, один из которых содержит около 13000 запрещенных фраз, а другой содержит около 10000 предложений.

phrases = [
    "phrase1",
    "phrase2",
    "phrase with spaces",
    # ...
]

sentences = [
    "sentence",
    "some sentences are longer",
    "some sentences can be really really ... really long, about 1000 characters.",
    # ...
]

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

Это то, что я имею до сих пор:

import re
for sentence in sentences:
    for phrase in phrases:
        if phrase in sentence.lower():
            iphrase = re.compile(re.escape(phrase), re.IGNORECASE)
            newsentence = iphrase.sub("**"+phrase+"**", sentence)
            newlist.append(newsentence)

Пока этот подход занимает около 60 секунд.

Я пытался использовать многопроцессорность (каждое предложение для цикла было отображено отдельно), однако это дало еще более медленные результаты.Принимая во внимание, что каждый процесс работал примерно на 6% загрузки ЦП, кажется, что накладные расходы делают сопоставление такой небольшой задачи нескольким ядрам не стоящим.Я думал о том, чтобы разделить список предложений на более мелкие куски и отобразить их в отдельные процессы, но не совсем понял, как это реализовать.

Я также рассмотрел использование алгоритма двоичного поиска но не смог выяснить, как использовать это со строками.

Итак, по сути, какой самый быстрый способ выполнить эту проверку?

Answer 1

Создайте свое регулярное выражение один раз, отсортировав по самой длинной фразе, чтобы вы охватили ** вокруг самых длинных совпадающих фраз, а не самых коротких, произведите подстановку и отфильтруйте те, которые не были сделаны, например:

phrases = [
    "phrase1",
    "phrase2",
    "phrase with spaces",
    'can be really really',
    'characters',
    'some sentences'
    # ...
]

sentences = [
    "sentence",
    "some sentences are longer",
    "some sentences can be really really ... really long, about 1000 characters.",
    # ...
]

# Build the regex string required
rx = '({})'.format('|'.join(re.escape(el) for el in sorted(phrases, key=len, reverse=True)))
# Generator to yield replaced sentences
it = (re.sub(rx, r'**\1**', sentence) for sentence in sentences)
# Build list of paired new sentences and old to filter out where not the same
results = [new_sentence for old_sentence, new_sentence in zip(sentences, it) if old_sentence != new_sentence]

Дает вам results из:

['**some sentences** are longer',
 '**some sentences** **can be really really** ... really long, about 1000 **characters**.']

Answer 2

А как насчет набора понимания?

found = {'**' + p + '**' for s in sentences for p in phrases if p in s}

Вы можете попробовать обновить (уменьшив) список phrases, если не возражаете изменить его:

found = []
p = phrases[:] # shallow copy for modification
for s in sentences:
    for i in range(len(phrases)):
        phrase = phrases[i]
        if phrase in s:
            p.remove(phrase)
            found.append('**'+ phrase + '**')
    phrases = p[:]

Обычно каждая итерация уменьшает контейнер phrases.Мы перебираем последний контейнер, пока не найдем фразу, которая в хотя бы в одном предложении .

Мы удаляем его из скопированного списка, затем, как только мы проверим последние фразы, мы обновляем контейнер с сокращенным подмножеством фраз (тех, которые еще не видели).Мы делаем это, поскольку нам нужно видеть фразу хотя бы один раз , поэтому повторная проверка (хотя она может существовать в другом предложении) не нужна.