Сравните два списка в Python со сложностью o (n)

Question

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

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

Answer 1

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

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 и проверив пробелы, вместо создания списка в памяти.

Answer 2

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

Создать пустой словарь, 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]
 }

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

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

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

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

Answer 3

вместо того, чтобы

если 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)

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

Answer 4

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

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

Выход:

name
school
address

Answer 5

Вам нужно это https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_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]