сравнение списка списков с самим собой

Question

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

Как я могу избежать повторных сравнений, сравнивая уже сопоставленные списки?

Ex: big_list [0] был сопоставлен с big_list [20], поэтому нет причин сравнивать big_list [20] с big_list [0] позже в цикле.

 big_list= [[0.12, 0.939, -0.321, 6.342], [0.12, 0.939, -0.321,6.342], [0.0, 1.0, -0.0, -5.166], [0.0, 1.0, 0.0, -5.166], [0.0, 1.0, -0.0, -5.166], [-0.0, 1.0, 0.0, -5.166], [0.0, 1.0, 0.0, -5.166], [0.0, 1.0, 0.0, -5.166], [0.0,1.0, -0.0, -5.166], [0.0, 1.0, 0.0, -5.166], [-0.0, 1.0, -0.0, -5.166], [-0.0, 1.0, 0.0, -5.166], [-0.12, 0.939, 0.321, 0.282], [-0.12, 0.939, 0.321, 0.282], [0.12, 0.939, 0.321, -17.782], [0.12, 0.939, 0.321, -17.782], [-0.0, 1.0, 0.0, 0.834], [0.0, 1.0, 0.0, 0.834], [0.0, 1.0, 0.0, 0.834], [0.0, 1.0, 0.0, 0.834], [-0.12, 0.939, -0.321, 24.406], [-0.12, 0.939, -0.321, 24.406], [0.0, 0.874, -0.486, 21.883], [0.0, 0.874, -0.486, 21.883], [0.0, 0.874, 0.486, -14.598], [0.0, 0.874, 0.486, -14.598]] 

     for j in range(len(big_list)): 
      for k in range(len(big_list)): 
       if j!=k: 

        result=math.sqrt(sum([(a-b)**2 for a,b in zip(big_list[j],big_list[k])]))) 

Ранее, я решил этот вопрос, установив определенную терпимость и добавление каждого результата в новый список, но я пытаюсь придумать более эффективный способ сделать это. В конце концов, big_list, вероятно, будет 1 миллион + списки

if result<=rel_tol and big_list[k] not in new_list: 
    new_list.append(big_list[k]) 

Answer 1

Вместо сравнения списков друг с другом с двумя циклами for вы можете преобразовать их в кортежи и использовать Counter, чтобы узнать, сколько экземпляров есть. Затем вы можете перебирать список и выбирать первое вхождение каждого подсписок, имеющего несколько экземпляров.

from collections import Counter 

c = Counter(tuple(l) for l in big_list) 
new_list = [] 
for l in big_list: 
    t = tuple(l) 
    if c[t] > 1: 
     new_list.append(l) 
     c[t] = 0 

Это O (п) временной сложность и это приведет к тому же самому порядку, как исходный код.

Answer 2

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

for j in range(len(big_list)): 
     for k in range(len(big_list)): 

сделать это (обратите внимание на j+1):

for j in range(len(big_list)): 
     for k in range(j+1, len(big_list)): 

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

Answer 3

То, что @Justin ответил, также было моей первой мыслью, но после отражения я не считаю, что это самый эффективный для реального big_lists. Вместо этого я хотел бы использовать set() х tuples:

tupled_set = set([tuple(i) for i in big_list]) 
new_list_of_tuples = list(tupled_set) 

короче и быстрее с только встроенных итераций. Теперь, конечно, если вам нужно, чтобы вернуться к спискам (по какой-то причине нужно изменяемых подсписков), то прирост производительности может быть потерян (не уверен ТБХ, должны были бы эталоном), но читаемость не является:

list_of_lists = [list(i) for i in new_list_of_tuples] 

Cheers