Блог

У меня есть два списка, и я хочу найти ключевые слова из инструкций, и если в инструкции есть это конкретное ключевое слово, то я должен вернуть это ключевое слово. Я делаю это в o(n^2) . Могу ли я сделать это в o(n) или в каком-либо другом, меньшей сложности?

 keywords = ['name', 'class', 'school', 'address']

statements = ['name is hello', 'name is not hello', 'school is hello', 'address is hello']

for key in keywords :
    for statement in statements :
            string = statement
            if string.find(key) != -1:
            print(key)
  

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

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

 words = {'name', 'class', ...}
  

Затем выполните итерацию по каждому слову в ваших утверждениях следующим образом:

 for statement in statements:
    for word in statement.split():
        if word in words:
            print(word)
  

O(n * m) , где m — длина самой длинной строки. Я не уверен, насколько это эффективно str.split() или как именно это работает, но вы могли бы уменьшить сложность с пробелами здесь, находя каждое слово вручную, просматривая statement и проверяя наличие пробелов, вместо создания списка в памяти.

Если все, что вы хотите, это найти, существует ли какой-либо ключ в keywords в каких str.join -либо операторах, попробуйте сначала использовать:

 joined_statements = ' '.join(statements)
for key in keywords:
    if key in joined_statements:
        print(key)
  

Вывод:

 name
school
address
  

вместо того, чтобы делать

если string.find(ключ) != -1:

вы можете просто сделать

если ключ в строке:

Но в любом случае отступ неверен, и этот возврат в любом случае не должен работать.

вместо этого вы могли бы сделать что-то вроде этого:

 keywords = ['name', 'class', 'school', 'address']
checkedkeywords = []

statements = ['name is hello', 'name is not hello', 'school is hello', 'address is hello']

for key in keywords :
    for statement in statements :
            string = statement
            if key in string:
              checkedkeywords.append(key)

print(checkedkeywords)  

Надеюсь, это поможет и удачи!

Итак, вам нужно использовать подход ОБРАТНОГО ИНДЕКСИРОВАНИЯ для решения этой проблемы.

Создайте пустой словарь, lookup_dict={}

Теперь выполните цикл по каждому слову в каждом операторе и сохраните STATEMENTS_INDEX, соответствующий этому слову, как описано ниже.

statements = ['name is hello', 'name is not hello', 'school is hello', 'address is hello']

 lookup_dict= {
          'name': [0,1], # Denoting 'name' keyword comes in index 0 and 1
          'is': [0,1,2,3],
          'hello':[0,1,2,3],
          'not':[1],
          'address':[3]
 }
  

Теперь, как только вы создадите свои индексы, что обычно является одноразовой операцией, если данных чертовски много.

Теперь, если вам нужно проверить, какое ключевое слово встречается во всех операторах, просто используйте словарь поиска.

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

Эта логика называется обратным индексированием и используется lucene, которая используется solr, elasticsearch внутренне.

Вам нужно это https://en.wikipedia.org/wiki/Aho–Corasick_algorithm Найдите строку в другой строке, это не бесплатно. Более простой способ

 keywords = ['name', 'class', 'school', 'address']

statements = ['name is hello', 'name is not hello', 'school is hello', 'address is hello']
from collection import defaultdict
word2statements = defaultdict(list)
for statement in statements :
    for word in set(statement.split()):
        word2statements[word].append(statement)

for keyword in keywords:
    word2statements[keyword]