[list] 파이썬에서 목록이 항목을 공유하는지 테스트

짧은 대답 : use not set(a).isdisjoint(b), 일반적으로 가장 빠릅니다.

두 개의 목록 a을 b공유하고 항목을 공유 하는지 테스트하는 일반적인 네 가지 방법이 있습니다. 첫 번째 옵션은 다음과 같이 둘 다 세트로 변환하고 교차점을 확인하는 것입니다.

bool(set(a) & set(b))

세트는 파이썬에서 해시 테이블을 사용하여 저장O(1) 되기 때문에 세트를 검색합니다 ( 파이썬 연산자의 복잡성에 대한 자세한 내용 은 여기 참조 ). 이론적으로,이은 O(n+m)에 대한 평균 n및 m목록에 객체 a와 b. 그러나 1) 먼저 목록에서 집합을 만들어야하며 무시할 수없는 시간이 걸릴 수 있으며 2) 해시 충돌이 데이터 사이에 드문 것으로 가정합니다.

두 번째 방법은 다음과 같이 목록에서 반복을 수행하는 생성기 표현식을 사용하는 것입니다.

any(i in a for i in b)

이를 통해 내부 검색이 가능하므로 중간 변수에 새 메모리가 할당되지 않습니다. 그것은 또한 첫 번째 발견에서 구제됩니다. 그러나 in연산자는 항상 O(n)목록에 있습니다 ( 여기 참조 ).

제안 된 또 다른 옵션은 목록 중 하나를 반복하고 세트의 다른 하나를 변환하고이 세트의 멤버십을 테스트하는 하이브리드입니다.

a = set(a); any(i in a for i in b)

네 번째 방법은 isdisjoint()(냉동 된) 세트 의 방법을 활용하는 것입니다 ( 여기 참조 ).

not set(a).isdisjoint(b)

검색하는 요소가 배열의 시작 부분 근처에있는 경우 (예 : 정렬 된 경우), 집합 교차 방법이 중개 변수에 새 메모리를 할당해야하므로 생성기 표현식이 선호됩니다.

from timeit import timeit
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=list(range(1000))", number=100000)
26.077727576019242
>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=list(range(1000))", number=100000)
0.16220548999262974

리스트 크기에 따른이 예제의 실행 시간 그래프는 다음과 같습니다.

두 축은 ​​모두 로그입니다. 이것은 생성기 표현식에 가장 적합한 경우를 나타냅니다. 보다시피,이 isdisjoint()방법은 매우 작은 목록 크기에 대해 더 나은 반면 생성기 표현식은 큰 목록 크기에 더 좋습니다.

반면에 검색이 하이브리드 및 생성기 표현식의 시작으로 시작함에 따라 공유 요소가 배열의 끝에 체계적으로 있거나 두 목록이 값을 공유하지 않는 경우 분리 및 설정 교차 접근 방식은 생성기 표현과 하이브리드 방식보다 훨씬 빠릅니다.

>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
13.739536046981812
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
0.08102107048034668

리스트 크기가 클수록 생성기 표현식이 더 느리다는 점에 주목하는 것이 흥미 롭습니다. 이것은 이전 그림의 100000이 아니라 1000 회 반복입니다. 이 설정은 공유 된 요소가 없을 때에도 근사치이며, 분리 및 교차로 접근에 가장 적합한 경우입니다.

다음은 임의의 숫자를 사용한 두 가지 분석입니다 (하나의 기술을 선호하도록 설정을 조작하는 대신).

높은 공유 가능성 : 요소는에서 임의로 가져옵니다 [1, 2*len(a)]. 낮은 공유 가능성 : 요소는에서 임의로 가져옵니다 [1, 1000*len(a)].

지금까지이 분석에서는 두 목록의 크기가 모두 같다고 가정했습니다. 크기가 다른 두 개의리스트의 경우, 예를 들어이 a훨씬 작다 isdisjoint()항상 빠른 :

있는지 확인하십시오 a, 그렇지 않으면 성능이 감소 목록은 작다. 이 실험에서 a목록 크기는로 일정하게 설정되었습니다 5.

요약해서 말하자면:

• 목록이 매우 작은 경우 (<10 개 요소) not set(a).isdisjoint(b)항상 가장 빠릅니다.
• 목록의 요소가 정렬되거나 활용할 수있는 규칙적인 구조를 갖는 경우 생성기 표현식 any(i in a for i in b)은 큰 목록 크기에서 가장 빠릅니다.
• 와 교집합 테스트 not set(a).isdisjoint(b)보다 빠른 항상, bool(set(a) & set(b)).
• 하이브리드 “목록을 통한 반복 테스트, 설정 테스트” a = set(a); any(i in a for i in b)는 일반적으로 다른 방법보다 느립니다.
• 생성기 표현과 하이브리드는 요소를 공유하지 않고 목록에 올 때 다른 두 가지 접근법보다 훨씬 느립니다.

대부분의 경우 isdisjoint()공유기 요소가 없을 때 생성기 표현식이 실행하는 데 시간이 훨씬 오래 걸리므로 메소드를 사용하는 것이 가장 좋습니다.

답변

def lists_overlap3(a, b):
    return bool(set(a) & set(b))

def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

lists_overlap([3,4,5], [1,2,3])

def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

any([item in a for item in b])

return not frozenset(a).isdisjoint(frozenset(b))

def list_overlap(a,b):
     return any(i for i in a if i in b)

return any(i in b for i in a)

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
100.91506409645081
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
19.746716022491455
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
0.092626094818115234

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=list(range(10000))", number=100000)
154.69790101051331
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=list(range(10000))", number=100000)
0.082653045654296875
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=list(range(10000))", number=100000)
0.08434605598449707