Python에서 목록 중복 테스트

소개

Python에서는 한 목록의 요소가 다른 목록에 있는지 확인하는 것이 다양한 데이터 조작 작업에 필수적입니다. 이 문서에서는 이러한 중복을 테스트하고 효율성을 평가하며 모범 사례를 제공하는 다양한 방법을 살펴봅니다.

접근 방법

1. 생성기 표현식

any(i in a for i in b)

이 메소드는 하나의 목록을 반복하고 다른 목록의 멤버십을 확인하여 일치하는 경우 True를 반환합니다. 설립하다. 시간 복잡도는 O(n)입니다. 여기서 n은 더 큰 목록의 길이입니다.

2. 교차점 설정

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

이 접근 방식은 두 목록을 모두 집합으로 변환하고 교차점을 찾습니다. 교차점이 비어 있지 않으면 True를 반환합니다. 이에 대한 최악의 시간 복잡도는 O(n·m)입니다. 여기서 n과 m은 목록의 길이입니다.

3. 하이브리드 집합 교차점

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

이 메소드는 하나의 목록만 세트로 변환하고 다른 목록을 반복하여 세트 멤버십을 확인합니다. 중간 집합 생성을 방지하여 기존 집합 교차보다 속도가 빠릅니다.

4. Isdisjoint 방법

not set(a).isdisjoint(b)

이 접근 방식은 고정 세트의 isdisjoint 방법을 사용하여 공통 요소가 있는지 확인합니다. 그렇지 않은 경우 결과는 False입니다. 그렇지 않으면 True입니다.

효율성 비교

최악의 경우:

• 생성기 표현식: O(n)
• 집합 교점: O(n·m)
• 하이브리드 집합 교점: O(n m)
• Isdisjoint 방법: O(1)

대부분의 경우 isdisjoint 방법은 상수 시간 집합 멤버십 확인의 이점을 활용하므로 가장 빠릅니다.

생성기 표현식의 가장 좋은 사례:

• 목록의 처음 몇 요소가 겹치는 경우. 이 경우 생성기 표현식은 True를 신속하게 반환할 수 있습니다.

고려할 요소:

• 목록 크기
• 분포 목록 내의 요소
• 공유 요소의 빈도

최고 사례

• 작은 목록(
• 목록 구조가 예측 가능한 경우(예: 정렬) 생성기 표현식이 더 빠를 수 있습니다.
• 목록 사이에 상당한 크기 차이가 있는 경우 작은 목록을 첫 번째 인수로 사용하여 isdisjoint 메서드를 사용합니다.
• 공유 요소가 거의 없거나 전혀 없는 목록의 경우 일반적으로 isdisjoint 방법이 더 효율적입니다.