순서에 관계없이 두 목록에 동일한 요소가 있는지 확인합니까?

순서에 관계없이 두 목록에 동일한 요소가 있는지 확인합니까? [복제]

---

이 질문에 이미 답변이 있습니다.

• 파이썬에서 두 개의 정렬되지 않은 목록 (세트가 아님)을 효율적으로 비교하는 방법은 무엇입니까? 9 답변

간단한 질문에 대해 죄송하지만 답을 찾기가 어렵습니다.

두 목록을 비교할 때 내용은 같지만 순서가 다르다는 점에서 "동일"한지 알고 싶습니다.

전의:

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²)) 일반적으로해야 하지 unhashable 및 unsortable 요소의 난해한 케이스의 외부 사용.

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

---

순서에 관계없이 두 목록에 동일한 요소가 있는지 확인합니까?

귀하의 예에서 추론 :

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

목록의 요소가 반복되지 않을 것이며 (유일하지 않음) 해시 가능 (문자열 및 기타 특정 불변 파이썬 객체가 있음), 가장 직접적이고 계산적으로 효율적인 답변 은 Python의 내장 집합을 사용합니다 (의미 적으로 수학과 유사 함). 학교에서 배운 세트).

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
>>> 

However, if each list must contain all the elements of other then the above code is problematic.

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

The problem arises when len(A) != len(B) and, in this example, len(A) > len(B). To avoid this, you can add one more statement.

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

One more thing, I benchmarked my solution with timeit.repeat, under the same conditions used by Aaron Hall in his post. As suspected, the results are disappointing. My method is the last one. set(x) == set(y) it is.

>>> 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

---

As mentioned in comments above, the general case is a pain. It is fairly easy if all items are hashable or all items are sortable. However I have recently had to try solve the general case. Here is my solution. I realised after posting that this is a duplicate to a solution above that I missed on the first pass. Anyway, if you use slices rather than list.remove() you can compare immutable sequences.

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