Python - 목록의 각 항목을 해당 목록의 다른 모든 항목과 비교하십시오.

Question

매우 긴 목록 (12471 항목)의 모든 항목을 같은 목록의 다른 항목과 비교해야합니다. 다음은 내 목록은 다음과 같습니다

[array([3, 4, 5]) 
array([ 6, 8, 10]) 
array([ 9, 12, 15]) 
array([12, 16, 20]) 
array([15, 20, 25]) 
...]     #12471 items long 

나는 그들이 동일한있어 있는지 확인하기 위해 다른 모든 배열의 첫 번째 항목으로 각 배열의 두 번째 항목을 비교해야합니다. 그리고 매우 바람직하게는, 매우 효율적인 방법으로. 파이썬 2.x에서 이것을 할 수있는 간단하고 효율적인 방법이 있습니까?

---

나는 여기에 매우 원유 방법을 근무하지만, 정말 느리다 :

ls=len(myList)  #12471 
l=ls 
k=0 
for i in myList: 
     k+=1 
     while l>=0: 
      l-=1 
      if i[1]==myList[l][0]: 
       #Do stuff 
     l=ls 

Answer 1

이 여전히 이론적 N^2 시간 (최악의 경우), 그것은 조금 더 나은 일을해야하지만 : 내 간단하고 짧은 사건의

import collections 

inval = [[3, 4, 5], 
[ 6, 8, 10], 
[ 9, 12, 15], 
[ 12, 14, 15], 
[12, 16, 20], 
[ 6, 6, 10], 
[ 8, 8, 10], 
[15, 20, 25]] 

by_first = collections.defaultdict(list) 
by_second = collections.defaultdict(list) 

for item in inval: 
    by_first[item[0]].append(item) 
    by_second[item[1]].append(item) 

for k, vals in by_first.items(): 
    if k in by_second: 
     print "by first:", vals, "by second:", by_second[k] 

출력 :

by first: [[6, 8, 10], [6, 6, 10]] by second: [[6, 6, 10]] 
by first: [[8, 8, 10]] by second: [[6, 8, 10], [8, 8, 10]] 
by first: [[12, 14, 15], [12, 16, 20]] by second: [[9, 12, 15]] 

중복 된 내용은 처리하지 않지만

Answer 2

우리는 python dict가 삽입 및 검색에 O (1) 시간이 걸린다는 가정하에 O (N)에서이를 수행 할 수 있습니다. 첫번째 스캔에서 맵의 각 행의 두 번째 요소를 포함하는 경우 제 스캔

1. , 우리는 제 2 주사에서, 전체 목록을
2. 를 스캔하여 최초의 번호 및 행 인덱스를 저장하는 맵을 만들고, 우리는 발견. map이 포함하면 map의 값은 필요한 기준과 일치하는 행 인덱스 목록을 제공합니다.

 
    myList = [[3, 4, 5], [ 6, 8, 10], [ 9, 12, 15], [12, 16, 20], [15, 20, 25]] 

    first_column = dict() 
    for idx, list in enumerate(myList): 
     if list[0] in first_column: 
      first_column[list[0]].append(idx) 
     else: 
      first_column[list[0]] = [idx] 

    for idx, list in enumerate(myList): 
     if list[1] in first_column: 
      print ('rows matching for element {} from row {} are {}'.format(list[1], idx, first_column[list[1]]))