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

Учитывая эти 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 на идее словаря для более крупных списков.

  • Как проверить, содержит ли файл простой текст?
  • получить mimetype файла python
  • Как убедить объекты потока python возвращать true из isatty ()?
  • Есть ли обратная функция для time.gmtime (), которая анализирует UTC-кортеж в секундах с момента эпохи?
  • Google Appengine NDB предка против ключевого запроса
  • Создание копии всего пространства имен?
  • Лучшая обработка KeyboardInterrupt в интерпретаторе командной строки cmd.Cmd
  • «Пихарм» неожиданно показывает «Неразрешенную ссылку»
  •  
    Interesting Posts for Van-Lav

    получение класса или пространства имен класса в python, даже если оно вложенное

    Pyserial не играет хорошо с виртуальным портом

    Извлечение текста из тега скрипта с помощью BeautifulSoup в Python

    python и sys.argv

    Как я могу извлечь все значения из словаря в Python?

    Какую версию Visual Studio и / или MinGW мне нужно для создания модулей расширения для данной версии Python?

    Ткань env.roledefs действует не так, как ожидалось

    Как зависит от системной команды с python / distutils?

    Какова наилучшая практика использования файла настроек в Python?

    iTunes API для скриптов python

    Создание матрицы замешательства из нескольких CSV-файлов

    В чем преимущество использования многострочных и однострочных строковых литералов в python?

    Javascript эквивалент Zip-функции Python

    Отменить уже выполняющуюся задачу с помощью Celery?

    Python list_of_tuples: суммировать второй val каждого кортежа, только если первый val tuple == something

    Python - лучший язык программирования в мире.