[python] 파이썬에서 정렬되지 않은 두 개의 목록 (비 세트)을 효율적으로 비교하는 방법은 무엇입니까?

a = [1, 2, 3, 1, 2, 3]
b = [3, 2, 1, 3, 2, 1]

a와 b는 정확히 같은 요소를 가지기 때문에 다른 순서로만 고려되어야합니다.

내 실제 목록은 정수가 아닌 객체 (내 클래스 인스턴스)로 구성됩니다.

답변

O (n) : Counter () 메서드가 가장 좋습니다 (객체가 해시 가능한 경우).

def compare(s, t):
    return Counter(s) == Counter(t)

O (n log n) : sorted () 메소드가 다음에 최상입니다 (객체가 정렬 가능한 경우).

def compare(s, t):
    return sorted(s) == sorted(t)

O (n * n) : 객체가 해시 가능하거나 정렬 가능하지 않은 경우 동등성을 사용할 수 있습니다.

def compare(s, t):
    t = list(t)   # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t

답변

둘 다 정렬 할 수 있습니다.

sorted(a) == sorted(b)

계산의 종류 도보다 효율적으로 될 수있다 (하지만 객체 해쉬 될 필요).

>>> from collections import Counter
>>> a = [1, 2, 3, 1, 2, 3]
>>> b = [3, 2, 1, 3, 2, 1]
>>> print (Counter(a) == Counter(b))
True

답변

항목이 항상 해시 가능하다는
것을 알고 있다면 A Counter()(O)를
사용할 수 있습니다. 항목이 항상 정렬 가능하다는 것을 알고 있다면 sorted()O (n log n)를 사용할 수 있습니다

일반적으로 정렬 할 수 없거나 요소를 가질 수 없으므로 다음과 같은 폴 백이 필요합니다. 불행히도 O (n ^ 2)

len(a)==len(b) and all(a.count(i)==b.count(i) for i in a)

답변

가장 좋은 방법은 목록을 정렬하고 비교하는 것입니다. ( Counter해시 가능하지 않은 객체에는 사용 이 작동하지 않습니다.) 이것은 정수에 대해 간단합니다.

sorted(a) == sorted(b)

임의의 객체로 조금 까다로워집니다. 객체 식별, 즉 동일한 객체가 두 목록 모두에 있는지 여부에 관심 이있는 경우이 id()기능을 정렬 키로 사용할 수 있습니다 .

sorted(a, key=id) == sorted(b, key==id)

(Python 2.x에서는 실제로 key= 객체와 객체를 비교할 수 있기 때문에 매개 변수 . 순서는 임의이지만 안정적이므로이 목적에 잘 작동합니다. 객체의 순서는 중요하지 않습니다. 파이썬 3에서는 다양한 유형의 객체를 비교하는 것이 허용되지 않습니다. 예를 들어 문자열을 정수와 비교할 수 없습니다. 따라서 객체가있는 경우 객체의 ID를 명시 적으로 사용하는 것이 가장 좋습니다.)

반면 에 값을 기준 으로 목록의 개체를 비교하려면 먼저 “값”의 의미를 정의해야합니다. 그런 다음 키로 제공 할 수있는 방법이 필요합니다 (Python 3의 경우 일관된 유형). 많은 임의의 객체에 작동하는 한 가지 잠재적 인 방법은 객체를 기준으로 정렬하는 것 repr()입니다. 물론 이것은 repr()큰 목록 등을 위해 많은 추가 시간과 메모리 구축 문자열을 낭비 할 수 있습니다.

sorted(a, key=repr) == sorted(b, key==repr)

객체가 모두 고유 한 유형 인 __lt__()경우 객체가 다른 객체와 비교하는 방법을 알 수 있도록 객체를 정의 할 수 있습니다. 그런 다음 정렬하고 key=매개 변수 에 대해 걱정할 필요가 없습니다 . 물론을 정의 __hash__()하고 사용할 수도 Counter있습니다.

답변

https://docs.python.org/3.5/library/unittest.html#unittest.TestCase.assertCountEqual

assertCountEqual (첫 번째, 두 번째, msg = 없음)

순서에 관계없이 시퀀스에 두 번째와 동일한 요소가 포함되어 있는지 먼저 테스트하십시오. 그렇지 않은 경우 시퀀스 간의 차이를 나열하는 오류 메시지가 생성됩니다.

첫 번째와 두 번째를 비교할 때 중복 요소는 무시되지 않습니다. 두 시퀀스에서 각 요소의 개수가 같은지 확인합니다. assertEqual (Counter (list (first)), Counter (list (second)))와 동일하지만 해싱 할 수없는 객체 시퀀스에서도 작동합니다.

버전 3.2의 새로운 기능.

또는 2.7에서 :
https://docs.python.org/2.7/library/unittest.html#unittest.TestCase.assertItemsEqual

답변

목록에 해시 불가능한 항목 (예 : 객체 목록)이 포함 된 경우 카운터 클래스 와 id () 함수를 다음과 같이 사용할 수 있습니다.

from collections import Counter
...
if Counter(map(id,a)) == Counter(map(id,b)):
    print("Lists a and b contain the same objects")

답변

아래 코드가 귀하의 경우에 효과가 있기를 바랍니다.

if ((len(a) == len(b)) and
   (all(i in a for i in b))):
    print 'True'
else:
    print 'False'

이 목록 모두의 모든 요소 보장됩니다 a및이 b에 상관없이 동일한 순서인지 아닌지의 동일합니다.

더 나은 이해를 위해이 질문에 대한 내 대답을 참조하십시오