python : 목록에서 일치하는 튜플 찾기

Question

2 튜플의 다른 목록에서 일치하는 2 튜플을 찾는 가장 빠른 방법은 무엇입니까?

다음 코드는 매우 비효율적입니다. loc1과 loc2는 (x, y) 좌표의 튜플 목록입니다.

loc3=[] 
for loc in loc1: 
    if loc in loc2: 
     loc3.append(loc) 

해시는 키이지만 파이썬에서 어떻게 수행해야할지 모르 십니다. 우아한 코드를 가르쳐주세요. 감사합니다. .

Answer 1

당신은 세트와 intersection를 사용할 수 있습니다

loc3 = set(loc1).intersection(loc2) 

이 당신에게 순서가 있고 중복 포함되지 않습니다 set를 제공 (및 항목이 해쉬 것을 적용). 그게 문제 인 경우 Phil Frost의 다른 답변을 참조하십시오. 그러나 이것은 주문과 중복이 불필요한 경우 훨씬 더 효율적이어야합니다. 파이썬

sloc2 = set(loc2) 
loc3 = [ item for item in loc1 if item in sloc2 ] #still O(m) 

set 단순히 해시 테이블이며, 다음과 같이

중복을 포함하지만, (loc2에서) 항목 hashability을 필요로 할 수 용액을 보존 질서이다. 항목의 위치가 해싱을 통해 발견되기 때문에 항목이 해당 세트에 포함되어 있는지 확인하려면 (대략) O (1) 작업입니다.