Сравнение двух списков строк

Question

Я знаком со сравнением 2 списков целых чисел и строки; однако при сравнении двух списков строк с дополнительными символами это может быть немного сложным.

Предположим, что вывод содержит следующее, где я разбиваю его на список строк. Я назвал это diff в моем коде.

выход

164c164
< Apples = 
---
> Apples = 0
168c168
< Berries = 
---
> Berries = false
218c218
< Cherries = 
---
> Cherries = 20
223c223
< Bananas = 
---
> Bananas = 10
233,234c233,234
< Lemons = 2
< Strawberries = 4
---
> Lemons = 4
> Strawberries = 2
264c264
< Watermelons = 
---
> Watermelons = 524288

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

>>> ignore
['Apples', 'Lemons']

Мой код:

>>> def str_compare (ignore, output):
...     flag = 0
...     diff = output.strip ().split ('\n')
...     if ignore:
...         for line in diff:
...             for i in ignore:
...                 if i in line:
...                     flag = 1
...             if flag:
...                 flag = 0
...             else:
...                 print (line)
... 
>>>

Код работает с пропущенными Apple и Lemons.

>>> str_compare(ignore, output)
164c164
---
168c168
< Berries = 
---
> Berries = false
218c218
< Cherries = 
---
> Cherries = 20
223c223
< Bananas = 
---
> Bananas = 10
233,234c233,234
< Strawberries = 4
---
> Strawberries = 2
264c264
< Watermelons = 
---
> Watermelons = 524288
>>>

Должен быть лучший способ сравнить 2 строки, что это не O (n ^ 2). Если бы мой список различий не содержал лишних символов, таких как «Apples =», то сравнение двух списков можно было бы выполнить с помощью O (n). Любые предложения или идеи для сравнения без циклически изменяемой переменной ignore для каждого элемента diff?

Обновление № 1 Чтобы избежать путаницы и использования предложенного комментария, я обновил код.

>>> def str_compare (ignore, output):
...     diff = output.strip ().split ('\n')
...     if ignore:
...         for line in diff:
...             if not any ([i in line for i in ignore]):
...                 print (line)
...                 print ("---")
>>>

Несмотря на это, он по-прежнему циклически игнорируется дважды для каждого элемента сравнения.

Answer 1

для эффективности используйте игнорируемые наборы, а не список. Используйте split, чтобы получить ключевое слово fromline.

>>> def str_compare (ignore, output):
...     ignore = set (ignore)
...     diff = output.strip ().split ('\n')
...     for line in diff:
...         if line.startswith('<') or line.startswith('>'):
...             var = line.split () [1]
...             if var not in ignore:
...                 print (line)
...         else:
...             print (line)
... 

выход

>>> str_compare (ignore, output)
164c164
---
168c168
< Berries = 
---
> Berries = false
218c218
< Cherries = 
---
> Cherries = 20
223c223
< Bananas = 
---
> Bananas = 10
233,234c233,234
< Strawberries = 4
---
> Strawberries = 2
264c264
< Watermelons = 
---
> Watermelons = 524288

Вы можете устранить необходимость в флаге, разделив и присоединившись к "--- \ n" (немного более общее решение, чем флаги или ввод ----)

Обратите внимание, что включение строки s1 в худшем случае s2 должно быть примерно len (s1) * len (2), тогда как равенство примерно max (len (s1), len (s2). В то время как реализация на python довольно приличная (для среднего случая) ), кажется, что существуют линейные алгоритмы сложности http://monge.univ -mlv.fr / ~ mac / Articles-PDF / CP-1991-jacm.pdf См. Также Алгоритм поиска совпадений нескольких строк