Подтвердить что ты не робот

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

Учитывая эти 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
4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

    return False

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

Ответ 2

Вы ищете

any( k in s for k in keywords )

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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, если не найден - это может быть полезно, если вам нужно знать, какое ключевое слово соответствует)

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

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

               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 solution и аналогичный подход перед применением регулярных выражений. Я также добавил 2 новых теста:

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

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

Ответ 5

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