Поиск списка строк для любой подстроки из другого списка

Учитывая эти 3 списка данных и список ключевых слов:

good_data1 = ['hello, world', 'hey, world'] good_data2 = ['hey, man', 'whats up'] bad_data = ['hi, earth', 'sup, planet'] keywords = ['world', 'he'] 

Я пытаюсь написать простую функцию, чтобы проверить, существует ли какое-либо из ключевых слов в качестве подстроки любого слова в списках данных. Он должен возвращать True для списков good_data и False для bad_data .

Я знаю, как это сделать в том, что кажется неэффективным:

 def checkData(data): for s in data: for k in keywords: if k in s: return True return False 

5 Solutions collect form web for “Поиск списка строк для любой подстроки из другого списка”

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

Поскольку вам не важно, какой элемент в списке содержит ключевое слово, вы можете сканировать весь список один раз (как одну строку) вместо одного элемента в то время. Для этого вам нужен символ объединения, который, как вы знаете, не будет встречаться в ключевом слове, чтобы избежать ложных срабатываний. В этом примере я использую новую строку.

 def check_data(data): s = "\n".join(data); for k in keywords: if k in s: return True return False 

В моем полностью ненаучном тесте моя версия проверила список из 5000 предметов 100000 раз за 30 секунд. Я остановил вашу версию через 3 минуты – устал ждать сообщения =)

Вы ищете

 any( k in s for k in keywords ) 

Это более компактно, но может быть менее эффективным.

Если у вас много ключевых слов, вы можете попробовать суффикс-дерево [1]. Вставьте все слова из трех списков данных, сохраняя список, из которого каждое слово приходит в его завершающем узле. Затем вы можете выполнять запросы по дереву для каждого ключевого слова действительно, очень быстро.

Предупреждение: деревья суффикса очень сложны для реализации!

[1] http://ru.wikipedia.org/wiki/Suffix_tree

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

Это может позволить им тестироваться параллельно, но будет сильно зависеть от того, какие ключевые слова (например, некоторые работы могут быть повторно использованы для тестирования «привет» и «ад», а не для поиска каждой фразы с самого начала для каждого слова.

Вы можете сделать это, выполнив:

 import re keyword_re = re.compile("|".join(map(re.escape, keywords))) 

Затем:

 >>> bool(keyword_re.search('hello, world')) True >>> bool(keyword_re.search('hi, earth')) False 

(Он фактически вернет найденный объект соответствия и None, если не найден – это может быть полезно, если вам нужно знать, какое ключевое слово соответствует)

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

[Изменить] Для справки, вот как подходят подходы к вашему примеру:

  good1 good2 good3 bad1 bad2 original : 0.206 0.233 0.229 0.390 63.879 gnud (join) : 0.257 0.347 4.600 0.281 6.706 regex : 0.766 1.018 0.397 0.764 124.351 regex (join) : 0.345 0.337 3.305 0.481 48.666 

Очевидно, что для этого случая ваш подход работает намного лучше, чем регулярное выражение. Независимо от того, будет ли это всегда так, многое зависит от количества и сложности ключевых слов и от входных данных, которые будут проверяться. Для большого количества ключевых слов и длинных списков или редко совпадающих фраз регулярные выражения могут работать лучше, но получать информацию о времени и, возможно, сначала попытаться упростить оптимизацию (например, переместить наиболее распространенные слова в начало списка ключевых слов). Иногда самый простой подход действительно лучший.

[Edit2] Обновлена ​​таблица с помощью решения gnud и аналогичный подход перед применением регулярных выражений. Я также добавил 2 новых теста:

 good_data3 = good_data2 * 500 # 1000 items, the first of which matches. bad_data2 = bad_data * 500 # 1000 items, none of which matches. 

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

Я думаю, что это довольно эффективно и понятно, хотя вы можете использовать map (), чтобы избежать множества гнезд. Я согласен с ross на идее словаря для более крупных списков.

  • Сбор трипсина (расщепление) не работает с использованием регулярного выражения
  • Как работает декоратор @timeout (timelimit)?
  • Как операторы сравнения Python <и> работают с именем функции в качестве операнда?
  • Как изменить порядок списка?
  • Как извлечь определенные строки данных из огромного листа Excel с помощью Python?
  • нахождение max в python в соответствии с определенным пользовательским критерием
  • «Наконец» эквивалент для операторов If / Elif в Python
  • Как определить повторный ввод в моей игре палача (Python)!
  • Python - лучший язык программирования в мире.