[python] 한 목록이 다른 목록의 하위 집합인지 어떻게 확인할 수 있습니까?

PYTHON / 글쓴이

목록이 다른 목록의 하위 집합인지 확인해야합니다. 부울 리턴 만 있으면됩니다.

교차 후 작은 목록에서 동등성을 테스트하는 것이 가장 빠른 방법입니까? 비교해야 할 데이터 세트의 수를 고려할 때 성능이 가장 중요합니다.

토론을 기반으로 추가 사실 추가 :

  1. 많은 테스트에서 목록 중 하나가 동일합니까? 정적 조회 테이블 중 하나이므로 수행합니다.

  2. 목록이어야합니까? 정적 조회 테이블은 성능이 가장 좋은 것이 될 수 있습니다. 동적은 정적 조회를 수행하기 위해 키를 추출하는 명령입니다.

시나리오를 고려할 때 최적의 솔루션은 무엇입니까?

답변

파이썬이 제공하는 퍼포먼스 함수는 set.issubset입니다. 그러나 귀하의 질문에 대한 답변인지 확실하지 않은 몇 가지 제한 사항이 있습니다.

목록에는 항목이 여러 번 포함될 수 있으며 특정 주문이 있습니다. 세트는하지 않습니다. 또한 세트는 해시 가능한 객체 에서만 작동 합니다.

서브 세트 또는 서브 시퀀스에 대해 질문하고 있습니까 (즉, 문자열 검색 알고리즘이 필요함)? 많은 테스트에서 목록 중 하나가 동일합니까? 목록에 포함 된 데이터 유형은 무엇입니까? 그리고 그 문제에 대해 목록이 필요합니까?

다른 게시물 은 dict과 교차하고 목록 이 유형을 더 명확하게 만들고 세트와 같은 기능을 위해 사전 키보기를 사용하도록 권장했습니다. 이 경우 사전 키가 집합처럼 동작하기 때문에 작동하는 것으로 알려져 있습니다 (파이썬에서 집합을 사용하기 전에 사전을 사용 했음). 세 시간 동안 문제가 어떻게 구체적이지 않은지 궁금합니다.

답변

>>> a = [1, 3, 5]
>>> b = [1, 3, 5, 8]
>>> c = [3, 5, 9]
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

>>> a = ['yes', 'no', 'hmm']
>>> b = ['yes', 'no', 'hmm', 'well']
>>> c = ['sorry', 'no', 'hmm']
>>>
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

답변

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

all(x in two for x in one)

설명 : 생성자 one가 해당 항목이 list에 있는지 여부를 점검 하여 목록을 반복하여 부울을 작성 합니다 two. 모든 항목이 진실이면를 all()반환 True합니다 False.

all모든 항목을 처리하지 않고 누락 된 요소의 첫 번째 인스턴스에서 False 를 반환 하는 이점도 있습니다.

답변

항목이 해시 가능하다고 가정

>>> from collections import Counter
>>> not Counter([1, 2]) - Counter([1])
False
>>> not Counter([1, 2]) - Counter([1, 2])
True
>>> not Counter([1, 2, 2]) - Counter([1, 2])
False

중복 항목에 신경 쓰지 않는 경우 (예 : [1, 2, 2]그리고 [1, 2]그럼 그냥 사용 :

>>> set([1, 2, 2]).issubset([1, 2])
True

교차 후 작은 목록에서 동등성을 테스트하는 것이 가장 빠른 방법입니까?

.issubset가장 빠른 방법입니다. 테스트하기 전에 길이를 확인하면 issubset반복하여 확인해야하는 O (N + M) 항목이 있으므로 속도가 향상되지 않습니다.

답변

한 가지 더 해결책은을 사용하는 것 intersection입니다.

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one).intersection(set(two)) == set(one)

세트의 교차점에는 set one

(또는)

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one) & (set(two)) == set(one)

답변

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(x in two for x in one) == set([True])

list1이 목록 2에있는 경우 :

  • (x in two for x in one)의 목록을 생성합니다 True.

  • 우리가 할 때 set(x in two for x in one)하나의 요소 (True) 만 있습니다.

답변

중복 된 집합은 집합 이론을 사용하여 오답을 초래하기 때문에 집합 이론은 목록에 적합하지 않습니다.

예를 들면 다음과 같습니다.

a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
set(b) > set(a)

의미가 없습니다. 예, 그것은 틀린 답을 제공하지만 세트 이론은 단지 1,3,5 대 1,3,4,5를 비교하기 때문에 정확하지 않습니다. 모든 중복을 포함해야합니다.

대신 각 항목의 각 항목을 세고 확인하기 위해 동일하게 수행해야합니다. O (N ^ 2) 연산을 사용하지 않고 빠른 정렬이 필요하지 않기 때문에 비용이 많이 들지 않습니다.

#!/usr/bin/env python

from collections import Counter

def containedInFirst(a, b):
  a_count = Counter(a)
  b_count = Counter(b)
  for key in b_count:
    if a_count.has_key(key) == False:
      return False
    if b_count[key] > a_count[key]:
      return False
  return True


a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

a = [1, 3, 3, 3, 4, 4, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

그런 다음 이것을 실행하면 다음을 얻습니다.

$ python contained.py
b in a:  False
b in a:  True