Оптимизация вложенного цикла цикла с двумя списками

Question

У меня есть программа, которая выполняет поиск по двум отдельным спискам, позволяет называть их list1 и list2.

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

Если они совпадают, я хочу, чтобы полные списки (включая несоответствующие элементы) добавлялись к двум соответствующим спискам.

Я написал код следовать:

for item in list1: 
    for item2 in list2: 
     if (item[0] and item[2:4])==(item[0] and item2[2:4]): 
      newlist1.append(item) 
      newlist2.append(item2) 
      break 

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

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

Answer 1

Ваше состояние (item[0] and item[2:4])==(item[0] and item2[2:4]) неправильно.

Кроме того, что второй item[0] должен вероятно быть item2[0], чем (item[0] and item[2:4]) делает следующее (аналогично для (item2[0] and item2[2:4])):

• если item[0] является 0, она возвращает item[0] себя, т.е. 0
• если item[0] является не 0, он возвращает все, что item[2:4] является

И это затем сравнивается с результатом второго слагаемого. Таким образом, [0,1,1,1] будет «равно» [0,2,2,2], а [1,1,1,1] будет «равно» [2,1,1,1].

Попробуйте использовать tuples вместо:

if (item[0], item[2:4]) == (item2[0], item2[2:4]): 

Или использовать operator.itemgetter как предложено в другой ответ.

---

Чтобы ускорить парное сопоставление элементов из обоего списков, помещают элементы из первого списка в словарь, используя те кортежи, как ключ, а затем итерация над другим списком и поиск совпадающих элементов в словарь. Сложность будет O (N + M) вместо О (Н * м) (п и м быть длиной списков).

key = operator.itemgetter(0, 2, 3) 

list1_dict = {} 
for item in list1: 
    list1_dict.setdefault(key(item), []).append(item) 

for item2 in list2: 
    for item in list1_dict.get(key(item2), []): 
     newlist1.append(item) 
     newlist2.append(item2) 

Answer 2

from operator import itemgetter 

getter = itemgetter(0, 2, 3) 
for item,item2 in zip(list1, list2): 
    if getter(item) == getter(item2): 
     newlist1.append(item) 
     newlist2.append(item2) 
     break 

Это может уменьшить немного времени сложности, хотя ...