Снизить стоимость сравнения двух списков

Question

Я хочу свести к минимуму стоимость сравнения двух списков, содержащих несколько слов. В приведенном ниже коде A имеет 4 слова, тогда как B имеет 2 слова и стоит O(n^2), что очень плохо. Хотя за 100 слов это может занять много времени. Могу ли я как-то свести к минимуму?

A= ["helry", "john" , "kat" , "david"] 
d="Helry David" 
B = d.lower().split() 

for x in range(len(A)): 
      for i in range(len(B)): 
       if A[x] == B[i]: 
        print("Match = " + A[x]) 
       else: 
        print("No") 

Answer 1

1. Сортировка массива для O (NlogN) в первую очередь.
2. Сравните это в O (n), потому что вы можете смело предположить, что связь между определенными элементами одинакова после сортировки.

Answer 2

1. O(nlogn) для сортировки A.
2. используйте двоичный поиск для каждого элемент B в A Iit'll возьмите O(log n). Для m элементов в B, это будет O(m*logn).

(или), если вы используете хэш, вы можете сделать в O(m) для m элементов B.

Answer 3

Используйте наборы вместо списков (кстати, они не называются массивами в Python). То, что вам нужно, - это пересечение двух множеств, которое (в среднем) O(min(len(A), len(B)) (https://wiki.python.org/moin/TimeComplexity). И поскольку этот алгоритм встроен и реализован в C, он намного быстрее, чем все, что вы могли бы написать в коде Python.

Пример (A и B считаются определены как раньше):

>>> set(A) & set(B) 
{'david', 'helry'} 

Это дает вам набор всех значений, которые содержатся в А и В.

Answer 4

Вы можете сделать это в о (п) времени с наборами и тестированием для членства с in, вам все равно придется перебрать все имена в A но проверке, если каждое имя в setof зовут O(1):

A = ["helry", "john" , "kat" , "david"] 
d = "Helry David" 
st = set(d.lower().split()) 

for name in A: 
    if name in st: 
     print("Match = {}".format(name)) 
    else: 
     print("No match")