복붙노트

[PYTHON] 평면 목록에 중복 된 항목이 있는지 어떻게 확인합니까?

PYTHON

평면 목록에 중복 된 항목이 있는지 어떻게 확인합니까?

예를 들어 [ 'one', 'two', 'one'] 목록이 주어지면 알고리즘은 True를 반환해야하지만 [ 'one', 'two', 'three']는 False를 반환해야합니다.

해결법

  1. ==============================

    1.모든 값이 해시 가능하면 중복을 제거하려면 set ()을 사용하십시오.

    모든 값이 해시 가능하면 중복을 제거하려면 set ()을 사용하십시오.

    >>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True
  2. ==============================

    2.짧은 목록에만 권장됩니다.

    짧은 목록에만 권장됩니다.

    any(thelist.count(x) > 1 for x in thelist)

    긴 목록에 사용하지 마십시오. 목록에있는 항목 수의 제곱에 비례하여 시간이 걸릴 수 있습니다!

    해시 가능 항목 (문자열, 숫자 및 & c)이있는 긴 목록 :

    def anydup(thelist):
  seen = set()
  for x in thelist:
    if x in seen: return True
    seen.add(x)
  return False

    항목이 해시 가능 (하위 목록, 사전 등)이 아니라면 더 털이납니다. 적어도 비교할 수 있으면 O (N logN)을 얻을 수 있습니다. 그러나 해시 가능 객체에 대해서는 O (N), 해시 가능하지 않은 비교 객체에 대해서는 O (N log N), 그렇지 않으면 해시 가능 객체에 대해서는 O (N log N), 가능하지 않은 경우에는 해시 가능 객체에 대한 특성을 알고 있거나 테스트해야합니다 그것은 O (N 제곱)까지 내려 갔고 아무 것도 그것에 대해 할 수있는 것이 없었습니다 :-(.

  3. ==============================

    3.함수형 프로그래밍 스타일을 좋아한다면 doctest를 사용하여 자체적으로 문서화하고 테스트 한 유용한 함수가 있습니다.

    함수형 프로그래밍 스타일을 좋아한다면 doctest를 사용하여 자체적으로 문서화하고 테스트 한 유용한 함수가 있습니다.

    def decompose(a_list):
    """Turns a list into a set of all elements and a set of duplicated elements.

    Returns a pair of sets. The first one contains elements
    that are found at least once in the list. The second one
    contains elements that appear more than once.

    >>> decompose([1,2,3,5,3,2,6])
    (set([1, 2, 3, 5, 6]), set([2, 3]))
    """
    return reduce(
        lambda (u, d), o : (u.union([o]), d.union(u.intersection([o]))),
        a_list,
        (set(), set()))

if __name__ == "__main__":
    import doctest
    doctest.testmod()

    거기에서 반환 된 쌍의 두 번째 요소가 비어 있는지 확인하여 단일성을 테스트 할 수 있습니다.

    def is_set(l):
    """Test if there is no duplicate element in l.

    >>> is_set([1,2,3])
    True
    >>> is_set([1,2,1])
    False
    >>> is_set([])
    True
    """
    return not decompose(l)[1]

    이것은 분해를 명시 적으로 구성했기 때문에 효율적이지 않습니다. 그러나 reduce를 사용하는 줄에서 5에 대답하는 것과 동등한 (그러나 약간은 덜 효율적) 것을 생각해 낼 수 있습니다 :

    def is_set(l):
    try:
        def func(s, o):
            if o in s:
                raise Exception
            return s.union([o])
        reduce(func, l, set())
        return True
    except:
        return False
  4. ==============================

    4.이것은 오래되었지만 여기에 대한 답은 약간 다른 해결책으로 이어졌습니다. 학대에 대한 이해가 부족한 경우,이 방법으로 단락시킬 수 있습니다.

    이것은 오래되었지만 여기에 대한 답은 약간 다른 해결책으로 이어졌습니다. 학대에 대한 이해가 부족한 경우,이 방법으로 단락시킬 수 있습니다.

    xs = [1, 2, 1]
s = set()
any(x in s or s.add(x) for x in xs)
# You can use a similar approach to actually retrieve the duplicates.
s = set()
duplicates = set(x for x in xs if x in s or s.add(x))
  5. ==============================

    5.최근에 발전기를 사용하여 목록에있는 모든 복제본을 설정하는 관련 질문에 답했습니다. '중복이있는 경우'를 설정하기 만하면 첫 번째 항목을 가져와야하고 나머지는 무시할 수 있다는 이점이 있습니다. 이것이 바로 바로 가기입니다.

    최근에 발전기를 사용하여 목록에있는 모든 복제본을 설정하는 관련 질문에 답했습니다. '중복이있는 경우'를 설정하기 만하면 첫 번째 항목을 가져와야하고 나머지는 무시할 수 있다는 이점이 있습니다. 이것이 바로 바로 가기입니다.

    이것은 moooeeeep에서 곧바로 적용한 흥미로운 세트 기반 접근 방식입니다.

    def getDupes(l):
    seen = set()
    seen_add = seen.add
    for x in l:
        if x in seen or seen_add(x):
            yield x

    따라서 dupes의 전체 목록은 list (getDupes (etc))입니다. 속보가 단순히 "if"인지 테스트하려면 다음과 같이 줄 바꿈되어야합니다.

    def hasDupes(l):
    try:
        if getDupes(c).next(): return True    # Found a dupe
    except StopIteration:
        pass
    return False

    이것은 잘 배율이 있고 목록에 속한 사람이 어디에 있든 일관된 작동 시간을 제공합니다. 최대 1m 항목의 목록으로 테스트했습니다. 데이터에 대해 아는 사람, 특히 그 두세들은 상반기에 나타나기도하고, 실제 속임수를 필요로하는 것과 같이 요구 사항을 왜곡시킬 수있는 다른 것들도 있습니다. 그런 다음 실제로는 두 개의 다른 속임수 로케이터가 있습니다 저것은 성능이 뛰어날지도 모른다. 내가 추천하는 두 가지는 ...

    간단한 사전에 기반한 접근 방식으로 매우 읽기 쉽습니다.

    def getDupes(c):
    d = {}
    for i in c:
        if i in d:
            if d[i]:
                yield i
                d[i] = False
        else:
            d[i] = True

    정렬 된 목록에서 itertools (본질적으로 ifilter / izip / tee)를 활용하십시오. 첫 번째를 빨리 얻지는 못하지만 모든 속행을 얻는다면 매우 효율적입니다.

    def getDupes(c):
    a, b = itertools.tee(sorted(c))
    next(b, None)
    r = None
    for k, g in itertools.ifilter(lambda x: x[0]==x[1], itertools.izip(a, b)):
        if k != r:
            yield k
            r = k

    이들은 처음부터 끝까지 1m 엘리먼트 목록에서 발생하는 첫 번째 사기 (dupe)와 함께 전체 사기 목록에 대해 시도한 접근법의 최고 수행자였습니다. 정렬 단계가 추가 된 것은 놀라운 것이 아닙니다. 귀하의 마일리지는 다를 수 있지만 여기에 제 시간에 지정된 결과가 있습니다 :

    Finding FIRST duplicate, single dupe places "n" elements in to 1m element array

Test set len change :        50 -  . . . . .  -- 0.002
Test in dict        :        50 -  . . . . .  -- 0.002
Test in set         :        50 -  . . . . .  -- 0.002
Test sort/adjacent  :        50 -  . . . . .  -- 0.023
Test sort/groupby   :        50 -  . . . . .  -- 0.026
Test sort/zip       :        50 -  . . . . .  -- 1.102
Test sort/izip      :        50 -  . . . . .  -- 0.035
Test sort/tee/izip  :        50 -  . . . . .  -- 0.024
Test moooeeeep      :        50 -  . . . . .  -- 0.001 *
Test iter*/sorted   :        50 -  . . . . .  -- 0.027

Test set len change :      5000 -  . . . . .  -- 0.017
Test in dict        :      5000 -  . . . . .  -- 0.003 *
Test in set         :      5000 -  . . . . .  -- 0.004
Test sort/adjacent  :      5000 -  . . . . .  -- 0.031
Test sort/groupby   :      5000 -  . . . . .  -- 0.035
Test sort/zip       :      5000 -  . . . . .  -- 1.080
Test sort/izip      :      5000 -  . . . . .  -- 0.043
Test sort/tee/izip  :      5000 -  . . . . .  -- 0.031
Test moooeeeep      :      5000 -  . . . . .  -- 0.003 *
Test iter*/sorted   :      5000 -  . . . . .  -- 0.031

Test set len change :     50000 -  . . . . .  -- 0.035
Test in dict        :     50000 -  . . . . .  -- 0.023
Test in set         :     50000 -  . . . . .  -- 0.023
Test sort/adjacent  :     50000 -  . . . . .  -- 0.036
Test sort/groupby   :     50000 -  . . . . .  -- 0.134
Test sort/zip       :     50000 -  . . . . .  -- 1.121
Test sort/izip      :     50000 -  . . . . .  -- 0.054
Test sort/tee/izip  :     50000 -  . . . . .  -- 0.045
Test moooeeeep      :     50000 -  . . . . .  -- 0.019 *
Test iter*/sorted   :     50000 -  . . . . .  -- 0.055

Test set len change :    500000 -  . . . . .  -- 0.249
Test in dict        :    500000 -  . . . . .  -- 0.145
Test in set         :    500000 -  . . . . .  -- 0.165
Test sort/adjacent  :    500000 -  . . . . .  -- 0.139
Test sort/groupby   :    500000 -  . . . . .  -- 1.138
Test sort/zip       :    500000 -  . . . . .  -- 1.159
Test sort/izip      :    500000 -  . . . . .  -- 0.126
Test sort/tee/izip  :    500000 -  . . . . .  -- 0.120 *
Test moooeeeep      :    500000 -  . . . . .  -- 0.131
Test iter*/sorted   :    500000 -  . . . . .  -- 0.157
  6. ==============================

    6.이 작업을 간략하게 수행하는 또 다른 방법은 카운터를 사용하는 것입니다.

    이 작업을 간략하게 수행하는 또 다른 방법은 카운터를 사용하는 것입니다.

    원래 목록에 중복 된 부분 만 있는지 확인하려면 :

    from collections import Counter

def has_dupes(l):
    # second element of the tuple has number of repetitions
    return Counter(l).most_common()[0][1] > 1

    또는 중복 된 항목 목록을 얻으려면 :

    def get_dupes(l):
    return [k for k, v in Counter(l).items() if v > 1]
  7. ==============================

    7.첫 번째 복제본을 찾았을 때 연산을 단락 시켰기 때문에이 알고리즘은 시간과 공간의 복잡성을 낳습니다. O (n) 여기서 n은리스트의 길이입니다.

    첫 번째 복제본을 찾았을 때 연산을 단락 시켰기 때문에이 알고리즘은 시간과 공간의 복잡성을 낳습니다. O (n) 여기서 n은리스트의 길이입니다.

    def has_duplicated_elements(self, iterable):
    """ Given an `iterable`, return True if there are duplicated entries. """
    clean_elements_set = set()
    clean_elements_set_add = clean_elements_set.add

    for possible_duplicate_element in iterable:

        if possible_duplicate_element in clean_elements_set:
            return True

        else:
            clean_elements_set_add( possible_duplicate_element )

    return False

    8. from https://stackoverflow.com/questions/1541797/how-do-i-check-if-there-are-duplicates-in-a-flat-list by cc-by-sa and MIT license

'PYTHON' 카테고리의 다른 글

[PYTHON] 어떻게 파이썬 3으로 INI 파일을 읽고 쓰는가?  (0) 2018.10.10
[PYTHON] 새로운 LIST에 두 개의 LIST 값 합계를 더한다.  (0) 2018.10.10
[PYTHON] 어떻게 파이썬을 사용하여 SQLite에 행을 삽입 한 후 삽입 된 ID를 검색 할 수 있습니까?  (0) 2018.10.10
[PYTHON] 모든 목록 요소에서 int () 함수를 호출 하시겠습니까?  (0) 2018.10.10
[PYTHON] stdin에서 암호 읽기  (0) 2018.10.10
,

티스토리툴바