목록이 다른 목록에 있는지 확인하는 방법 python

Question

두 개의 목록 (listA, listB)이 있는데, 각각 두 개의 튜플 목록으로 구성됩니다.

예. 이 listB에없는 경우

listA = [ [(0,1), (1,2) ... ] , [(5,6), (6,10)] , ... ] # can have 5000 lists, each with 100+ tuples 
listB = [...] # about the same structure 

내가 중고 장비 구매에 각 목록 전체를 반복하고 싶지, 내가 listB에 추가합니다.

은 그래서이 같은 것입니다 :

for lst in listA: 
    if lst not in listB: # membership checking 
     listB.append(lst) 

나는 수백 수행하는 등의 작업의 수천을하고 중고 장비 구매 및 listB가 커질 때 정말 느린 것 같다. 회원 확인이 병목 현상 인 것 같습니다. 나는 정수의 튜플 대신에 '0-1'이라는 문자열을 사용하려고 시도했지만 더 빠르게 진행되지는 않습니다. 누구든지 코드를 최적화하는 방법을 알고 있습니까? 목록 회원 확인이 정말로 느 립니 까?

도움을 주시면 대단히 감사하겠습니다. 감사!

------------- 편집 :이 내가

-------------이, 사람을 주셔서 감사합니다 사용하게하는 것이다. 중첩 목록을 튜플로 변환하고 집합 작업 사용 그러나 listA를 반복 할 때 각 중첩 된 목록을 튜플로 변환해야하므로 조심해야합니다 (단, 멤버쉽을 확인하기 위해!). listB에 목록으로 중첩 목록을 추가해야합니다. 즉 : 내가 틀리지 않는 경우 두 목록을 가정

# first convert listB to a set of tuples 
listB_as_set = set([tuple(x) for x in listB]) # O(N) 

for lst in listA: 
    # convert the nested list to tuple 
    lst_tuple = tuple(lst) 
    # membership checking 
    if lst_tuple in listB_as_set: # now O(1), originally O(N) 
     listB.append(lst) # still appending as a list to listB 

길이 N이 있고, lst_tuple하는 LST를 변환하는 시간을 무시하고 listB에 LST를 추가, 우리는 O(N)에 O(N2)에서 개선을 얻었다.

Answer 1

저장소 값을 확인하려면 세트이 훨씬 빠릅니다. 그래서 이것을 시도한 다음 for 루프를 사용하면 목록보다 빠릅니다. set becaus이다

listA，listB = set(listA),set(listB) 

버킷에 매핑하는 해시 함수를 사용한다. 파이썬 구현은 해시 테이블의 크기를 자동으로 조정하기 때문에 속도는 O(1) 일 수 있습니다. 이 객체 전 세트로, BU 에보다 느린 lists 온다 그 내용을 통해를 반복 여부를 결정에 관해서

Sets 상당히 빠릅니다. 중첩 된 목록을 사용하는 경우

---

, 당신은

listA = [[(0, 1), (1, 2)], [(5, 6), (6, 10)]] 
listA = { tuple(i) for i in listA} 

또는

listA = {frozenset(i) for i in listA} 

frozenset 유형은 불변 해쉬 그래서

frozenset([(0, 1), (1, 2)]) = frozenset([(1,2),(0,1)]) 

희망이 시도 할 수 있습니다 도움이됩니다.

Answer 2

지금하고있는 방식대로 목록의 성격 때문에 O (N^2) 작업입니다.당신이 세트를 사용하는 경우, 그것은 대략 O (N + m) 때문에 자세한 내용은 여기를 참조하십시오

https://wiki.python.org/moin/TimeComplexity 그래서 접근이

a = set(lista) 
b = set(listb) 

b.union(lista) 

단 세 줄의 코드와 훨씬 더 빨리 너무. AChampion이 uhashable 목록에 대해 제기 한 좋은 점. 이 경우

a = set([ tuple(x) for x in listA ]) 

이 적용됩니다.