순서에 상관없이 2개의 리스트가 동일한 요소를 가지고 있는지 결정하시겠습니까?

순서에 상관없이 2개의 리스트가 동일한 요소를 가지고 있는지 결정하시겠습니까?

이 질문에는 이미 다음과 같은 해답이 있다.

Python에서 주문되지 않은 두 목록(세트 아님)을 효율적으로 비교하는 방법? (10개 답변)

닫힌5년 전.

간단한 질문으로 미안하지만, 답을 찾기가 힘들어.

두 목록을 비교해보면, 같은 내용이지만 순서가 다르다는 점에서 '같다'는 것인지 알고 싶다.

Ex:

x = ['a', 'b']
y = ['b', 'a']

나는 되고 싶다.x == y에 대해 평가하다True.

x와 y의 요소를 가진 다중 집합이 동일한지 여부를 간단히 확인할 수 있다.

import collections
collections.Counter(x) == collections.Counter(y)

이 경우 요소를 해시 가능해야 하며 런타임이 다음 위치에 있음O(n)어디에n리스트의 크기 입니다.

요소도 고유할 경우 세트로 변환할 수 있다(동일한 무증상 런타임이 실제로 조금 더 빠를 수 있음).

set(x) == set(y)

요소가 해시 가능하지 않지만 정렬 가능한 경우 다른 대안(실행 시간:O(n log n))은

sorted(x) == sorted(y)

요소가 해시 가능하지도 정렬 가능하지도 않은 경우 다음과 같은 도우미 함수를 사용할 수 있다.상당히 느려질 것이라는 점에 유의하십시오(O(n²)) 및 일반적으로 해쉬할 수 없고 정렬할 수 없는 요소의 난해한 경우 이외에는 사용해서는 안 된다.

def equal_ignore_order(a, b):
    """ Use only when elements are neither hashable nor sortable! """
    unmatched = list(b)
    for element in a:
        try:
            unmatched.remove(element)
        except ValueError:
            return False
    return not unmatched

순서에 상관없이 2개의 리스트가 동일한 요소를 가지고 있는지 결정하시겠습니까?

예에서 유추해 보십시오.

x = ['a', 'b']
y = ['b', 'a']

리스트의 요소들이 해시블 뿐만 아니라 (그들은 독특하다) 해시블(어떤 문자열과 다른 불변의 비단뱀 물체들이 있는지), 가장 직접적이고 계산적으로 효율적인 답은 파이썬의 빌트인 집합들을 사용한다. (이 답은 학교에서 배운 수학 집합과 의미론적으로 같다.)

set(x) == set(y) # prefer this if elements are hashable

원소가 해시 가능하나 단위가 아닌 경우collections.Counter또한 의미론적으로 멀티셋으로 작동하지만 훨씬 느리다.

from collections import Counter
Counter(x) == Counter(y)

사용 선호sorted:

sorted(x) == sorted(y) 

원소를 주문할 수 있으면이는 고유하지 않거나 해쉬할 수 없는 상황을 설명하겠지만, 세트를 사용하는 것보다 훨씬 느릴 수 있다.

경험적 실험

경험적 실험은 사람이 더 선호해야 한다고 결론짓는다.set, 그러면.sorted...만을 선택하다.Counter카운트나 멀티셋으로서의 추가 사용과 같은 다른 것이 필요한 경우.

첫 번째 설정:

import timeit
import random
from collections import Counter

data = [str(random.randint(0, 100000)) for i in xrange(100)]
data2 = data[:]     # copy the list into a new one

def sets_equal(): 
    return set(data) == set(data2)

def counters_equal(): 
    return Counter(data) == Counter(data2)

def sorted_lists_equal(): 
    return sorted(data) == sorted(data2)

그리고 테스트:

>>> min(timeit.repeat(sets_equal))
13.976069927215576
>>> min(timeit.repeat(counters_equal))
73.17287588119507
>>> min(timeit.repeat(sorted_lists_equal))
36.177085876464844

그래서 우리는 세트를 비교하는 것이 가장 빠른 해결책이고, 정렬된 목록을 비교하는 것이 두 번째로 빠르다고 본다.

이것은 비록 큰 리스트에 거추장스럽기는 하지만 효과가 있는 것 같다.

>>> A = [0, 1]
>>> B = [1, 0]
>>> C = [0, 2]
>>> not sum([not i in A for i in B])
True
>>> not sum([not i in A for i in C])
False
>>> 

그러나 각 목록에 다른 모든 요소를 포함해야 하는 경우 위의 코드가 문제가 된다.

>>> A = [0, 1, 2]
>>> not sum([not i in A for i in B])
True

문제는 다음에 발생한다.len(A) != len(B)그리고, 이 예에서는,len(A) > len(B)이 문제를 한 개의 을 더 하면 된다 이 문제를 방지하려면 명령문을 하나 더 추가하십시오.

>>> not sum([not i in A for i in B]) if len(A) == len(B) else False
False

한 가지 더, 나는 아론 홀이 그의 직책에서 사용한 것과 같은 조건에서 내 해결책을 timeit.repeat으로 벤치마킹했다.의심스럽지만 결과는 실망스럽다.내 방법은 마지막이다.set(x) == set(y)그렇다.

>>> def foocomprehend(): return not sum([not i in data for i in data2])
>>> min(timeit.repeat('fooset()', 'from __main__ import fooset, foocount, foocomprehend'))
25.2893661496
>>> min(timeit.repeat('foosort()', 'from __main__ import fooset, foocount, foocomprehend'))
94.3974742993
>>> min(timeit.repeat('foocomprehend()', 'from __main__ import fooset, foocount, foocomprehend'))
187.224562545

위의 논평에서 언급했듯이 일반적인 경우는 골칫거리다.모든 항목을 해시할 수 있거나 모든 항목을 정렬할 수 있다면 꽤 쉽다.그러나 나는 최근에 일반적인 사건을 해결하려고 노력해야만 했다.여기 내 해결책이 있다.첫 번째 패스에서 놓친 위의 해결책의 복제품이라는 것을 게시하고 나서 깨달았다.어쨌든 list.remove() 대신 슬라이스를 사용하면 불변의 순서를 비교할 수 있다.

def sequences_contain_same_items(a, b):
    for item in a:
        try:
            i = b.index(item)
        except ValueError:
            return False
        b = b[:i] + b[i+1:]
    return not b

참조URL: https://stackoverflow.com/questions/8866652/determine-if-2-lists-have-the-same-elements-regardless-of-order