복붙노트

[PYTHON] 파이썬에서리스트에서 중복을 제거하는 가장 빠른 알고리즘은 무엇입니까? 그래서 모든 요소가 순차적으로 * 보존됩니다 *. [복제]

PYTHON

파이썬에서리스트에서 중복을 제거하는 가장 빠른 알고리즘은 무엇입니까? 그래서 모든 요소가 순차적으로 * 보존됩니다 *. [복제]

예 :

>>> x = [1, 1, 2, 'a', 'a', 3]
>>> unique(x)
[1, 2, 'a', 3]

목록 요소가 해시 가능하다고 가정합니다.

설명 : 결과는 목록에 첫 번째 사본을 유지해야합니다. 예를 들어 [1, 2, 3, 2, 3, 1]은 [1, 2, 3]이됩니다.

해결법

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

    1.

    def unique(items):
        found = set([])
        keep = []
    
        for item in items:
            if item not in found:
                found.add(item)
                keep.append(item)
    
        return keep
    
    print unique([1, 1, 2, 'a', 'a', 3])
    
  2. ==============================

    2.사용 :

    사용 :

    lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]
    

    그리고 timeit 모듈을 사용하면 :

    $ python -m timeit -s 'import uniquetest' 'uniquetest.etchasketch(uniquetest.lst)'
    

    그리고 다른 여러 기능 (포스터의 이름을 따서 붙인 이름)에 대해서도 다음과 같은 결과를 얻었습니다 (제 1 세대 Intel MacBook Pro에서).

    Allen:                  14.6 µs per loop [1]
    Terhorst:               26.6 µs per loop
    Tarle:                  44.7 µs per loop
    ctcherry:               44.8 µs per loop
    Etchasketch 1 (short):  64.6 µs per loop
    Schinckel:              65.0 µs per loop
    Etchasketch 2:          71.6 µs per loop
    Little:                 89.4 µs per loop
    Tyler:                 179.0 µs per loop
    

    [1] Allen은 목록을 제자리에서 수정한다는 것을 기억하십시오 - timeit 모듈이 코드 100000 번을 실행하고 99999가 속기없는리스트와 함께 있다는 점에서 시간이 왜곡 된 것 같습니다.

    요약 : 세트를 사용한 직접 구현은 혼란스러운 하나의 라이너보다 유리합니다 :-)

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

    3.다음은 지금까지 가장 빠른 솔루션입니다 (다음 입력에 해당).

    다음은 지금까지 가장 빠른 솔루션입니다 (다음 입력에 해당).

    def del_dups(seq):
        seen = {}
        pos = 0
        for item in seq:
            if item not in seen:
                seen[item] = True
                seq[pos] = item
                pos += 1
        del seq[pos:]
    
    lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 
           13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 
           5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 
           9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]
    del_dups(lst)
    print(lst)
    # -> [8, 9, 7, 15, 2, 20, 13, 24, 6, 11, 12, 4, 10, 18, 23, 3, 5, 22, 19, 14, 
    #     21, 1, 0, 16, 17]
    

    사전 검색은 Python 3에서 세트의 것보다 약간 더 빠릅니다.

  4. ==============================

    4.무엇이 가장 빠를 것인지는 중복 목록의 비율에 따라 다릅니다. 고유 한 항목이 거의없는 거의 모든 중복 항목 인 경우 새 목록을 만드는 것이 더 빠를 것입니다. 대부분 고유 항목 인 경우 원본 목록 (또는 사본)에서 제거하는 것이 더 빠릅니다.

    무엇이 가장 빠를 것인지는 중복 목록의 비율에 따라 다릅니다. 고유 한 항목이 거의없는 거의 모든 중복 항목 인 경우 새 목록을 만드는 것이 더 빠를 것입니다. 대부분 고유 항목 인 경우 원본 목록 (또는 사본)에서 제거하는 것이 더 빠릅니다.

    목록을 수정하는 방법은 다음과 같습니다.

    def unique(items):
      seen = set()
      for i in xrange(len(items)-1, -1, -1):
        it = items[i]
        if it in seen:
          del items[i]
        else:
          seen.add(it)
    

    인덱스를 거꾸로 반복하면 항목을 제거해도 반복에 영향을 미치지 않습니다.

  5. ==============================

    5.이것은 내가 찾은 가장 빠른 곳에서의 방법입니다 (큰 비율의 중복을 가정 할 때) :

    이것은 내가 찾은 가장 빠른 곳에서의 방법입니다 (큰 비율의 중복을 가정 할 때) :

    def unique(l):
        s = set(); n = 0
        for x in l:
            if x not in s: s.add(x); l[n] = x; n += 1
        del l[n:]
    

    이것은 Allen의 구현보다 10 % 빠릅니다 (psyco가 컴파일 한 timeit.repeat, JIT를 사용하여 시간 측정). 그것은 어떤 중복의 첫 번째 인스턴스를 유지합니다.

    repton-infinity : 내 타이밍을 확인할 수 있으면 관심이있을거야.

  6. ==============================

    6.필수 생성자 기반 변형 :

    필수 생성자 기반 변형 :

    def unique(seq):
      seen = set()
      for x in seq:
        if x not in seen:
          seen.add(x)
          yield x
    
  7. ==============================

    7.이것은 가장 간단한 방법 일 수 있습니다 :

    이것은 가장 간단한 방법 일 수 있습니다 :

    list(OrderedDict.fromkeys(iterable))
    

    파이썬 3.5부터는 OrderedDict가 이제 C로 구현되었으므로 이제는 가장 짧고, 가장 깨끗하고 빠릅니다.

  8. ==============================

    8.짧막 한 농담:

    짧막 한 농담:

    new_list = reduce(lambda x,y: x+[y][:1-int(y in x)], my_list, [])
    
  9. ==============================

    9.http://www.peterbe.com/plog/uniqifiers-benchmark에서 가져옴

    http://www.peterbe.com/plog/uniqifiers-benchmark에서 가져옴

    def f5(seq, idfun=None):  
        # order preserving 
        if idfun is None: 
            def idfun(x): return x 
        seen = {} 
        result = [] 
        for item in seq: 
            marker = idfun(item) 
            # in old Python versions: 
            # if seen.has_key(marker) 
            # but in new ones: 
            if marker in seen: continue 
            seen[marker] = 1 
            result.append(item) 
        return result
    
  10. ==============================

    10.이것에 대한 내부 라이너 :

    이것에 대한 내부 라이너 :

    >>> x = [1, 1, 2, 'a', 'a', 3]
    >>> [ item for pos,item in enumerate(x) if x.index(item)==pos ]
    [1, 2, 'a', 3]
    
  11. ==============================

    11.이 긴 토론의 모든 내용과 여기에 제시된 다른 답변을 비교하여 가장 빠른 것입니다.이 벤치 마크를 참조하십시오. 그것은 토론에서 가장 빠른 기능 인 f8보다 25 % 더 빠릅니다. David Kirby에게 감사드립니다.

    이 긴 토론의 모든 내용과 여기에 제시된 다른 답변을 비교하여 가장 빠른 것입니다.이 벤치 마크를 참조하십시오. 그것은 토론에서 가장 빠른 기능 인 f8보다 25 % 더 빠릅니다. David Kirby에게 감사드립니다.

    def uniquify(seq):
        seen = set()
        seen_add = seen.add
        return [x for x in seq if x not in seen and not seen_add(x)]
    

    약간의 시간 비교 :

    $ python uniqifiers_benchmark.py 
    * f8_original 3.76
    * uniquify 3.0
    * terhorst 5.44
    * terhorst_localref 4.08
    * del_dups 4.76
    
  12. ==============================

    12.이것을 해결하기 위해 실제로 파이썬에서 정말 멋진 것을 할 수 있습니다. 지어 질 때 자신을 참조 할 수있는 목록 이해력을 생성 할 수 있습니다. 다음과 같이 :

    이것을 해결하기 위해 실제로 파이썬에서 정말 멋진 것을 할 수 있습니다. 지어 질 때 자신을 참조 할 수있는 목록 이해력을 생성 할 수 있습니다. 다음과 같이 :

       # remove duplicates...
       def unique(my_list):
           return [x for x in my_list if x not in locals()['_[1]'].__self__]
    

    편집 : 나는 "자기"를 제거하고, 맥 OS X, 파이썬 2.5.1에서 작동합니다.

    _ [1]은 새로운 목록에 대한 파이썬의 "비밀"참조입니다. 위의 과정은 다소 지저분하지만 필요에 따라 적절하게 적용 할 수 있습니다. 예를 들어, 실제로는 이해력에 대한 참조를 반환하는 함수를 작성할 수 있습니다. 다음과 같이 보일 것입니다 :

    return [x for x in my_list if x not in this_list()]
    
  13. ==============================

    13.중복 물은 반드시 처음부터 목록에 있어야합니까? 오버 헤드가 없으면 요소를 찾지 만 요소를 추가하는 데 약간의 오버 헤드가 있습니다 (오버 헤드는 O (1)이어야 함).

    중복 물은 반드시 처음부터 목록에 있어야합니까? 오버 헤드가 없으면 요소를 찾지 만 요소를 추가하는 데 약간의 오버 헤드가 있습니다 (오버 헤드는 O (1)이어야 함).

    >>> x  = []
    >>> y = set()
    >>> def add_to_x(val):
    ...     if val not in y:
    ...             x.append(val)
    ...             y.add(val)
    ...     print x
    ...     print y
    ... 
    >>> add_to_x(1)
    [1]
    set([1])
    >>> add_to_x(1)
    [1]
    set([1])
    >>> add_to_x(1)
    [1]
    set([1])
    >>> 
    
  14. ==============================

    14.중복을 제거하고 광고 순서를 보존합니다.

    중복을 제거하고 광고 순서를 보존합니다.

    이것은 목록 내장 및 dict의 기본 제공 기능을 활용하는 고속 2 선입니다.

    x = [1, 1, 2, 'a', 'a', 3]
    
    tmpUniq = {} # temp variable used below 
    results = [tmpUniq.setdefault(i,i) for i in x if i not in tmpUniq]
    
    print results
    [1, 2, 'a', 3]
    

    dict.setdefaults () 함수는 값을 반환 할뿐만 아니라 목록 내역에 직접 temp dict에 값을 추가합니다. 내장 함수와 dict의 해시를 사용하면 프로세스의 효율성을 극대화 할 수 있습니다.

  15. ==============================

    15.O (n) dict가 해시 인 경우 O (nlogn) dict가 트리 인 경우 간단하고 고정. 제안에 대한 Matthew에게 감사드립니다. 미안 기본 유형을 모르겠습니다.

    O (n) dict가 해시 인 경우 O (nlogn) dict가 트리 인 경우 간단하고 고정. 제안에 대한 Matthew에게 감사드립니다. 미안 기본 유형을 모르겠습니다.

    def unique(x):    
      output = []
      y = {}
      for item in x:
        y[item] = ""
    
      for item in x:
        if item in y:
          output.append(item)
    
      return output
    
  16. ==============================

    16.파이썬에서 has_key는 O (1)입니다. 해시에서의 삽입 및 검색도 O (1)입니다. n 개의 항목을 두 번 반복하므로 O (n)입니다.

    파이썬에서 has_key는 O (1)입니다. 해시에서의 삽입 및 검색도 O (1)입니다. n 개의 항목을 두 번 반복하므로 O (n)입니다.

    def unique(list):
      s = {}
      output = []
      for x in list:
        count = 1
        if(s.has_key(x)):
          count = s[x] + 1
    
        s[x] = count
      for x in list:
        count = s[x]
        if(count > 0):
          s[x] = 0
          output.append(x)
      return output
    
  17. ==============================

    17.위대하고 효율적인 솔루션이 있습니다. 그러나 절대 가장 효율적인 O (n) 솔루션에 관심이없는 사람이라면 간단한 one-liner O (n ^ 2 * log (n)) 솔루션으로 갈 것입니다.

    위대하고 효율적인 솔루션이 있습니다. 그러나 절대 가장 효율적인 O (n) 솔루션에 관심이없는 사람이라면 간단한 one-liner O (n ^ 2 * log (n)) 솔루션으로 갈 것입니다.

    def unique(xs):
        return sorted(set(xs), key=lambda x: xs.index(x))
    

    또는보다 효율적인 2- 라이너 O (n * log (n)) 해 :

    def unique(xs):
        positions = dict((e,pos) for pos,e in reversed(list(enumerate(xs))))
        return sorted(set(xs), key=lambda x: positions[x])
    
  18. ==============================

    18.다음은 itertools 문서의 두 가지 조리법입니다.

    다음은 itertools 문서의 두 가지 조리법입니다.

    def unique_everseen(iterable, key=None):
        "List unique elements, preserving order. Remember all elements ever seen."
        # unique_everseen('AAAABBBCCDAABBB') --> A B C D
        # unique_everseen('ABBCcAD', str.lower) --> A B C D
        seen = set()
        seen_add = seen.add
        if key is None:
            for element in ifilterfalse(seen.__contains__, iterable):
                seen_add(element)
                yield element
        else:
            for element in iterable:
                k = key(element)
                if k not in seen:
                    seen_add(k)
                    yield element
    
    def unique_justseen(iterable, key=None):
        "List unique elements, preserving order. Remember only the element just seen."
        # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
        # unique_justseen('ABBCcAD', str.lower) --> A B C A D
        return imap(next, imap(itemgetter(1), groupby(iterable, key)))
    
  19. ==============================

    19.필자는 파이썬에 대한 경험이 없지만 알고리즘은 목록을 정렬 한 다음 목록에서 이전 항목과 비교하여 중복을 제거하고 마지막으로 이전 목록과 비교하여 새 목록의 위치를 ​​찾습니다.

    필자는 파이썬에 대한 경험이 없지만 알고리즘은 목록을 정렬 한 다음 목록에서 이전 항목과 비교하여 중복을 제거하고 마지막으로 이전 목록과 비교하여 새 목록의 위치를 ​​찾습니다.

    더 긴 대답 : http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560

  20. ==============================

    20.

    >>> def unique(list):
    ...   y = []
    ...   for x in list:
    ...     if x not in y:
    ...       y.append(x)
    ...   return y
    
  21. ==============================

    21.Terhost의 대답으로 set () 호출에서 빈 목록을 꺼내면 속도가 약간 빨라집니다.

    Terhost의 대답으로 set () 호출에서 빈 목록을 꺼내면 속도가 약간 빨라집니다.

    변화:     found = 집합 ([]) 에:     found = set ()

    그러나, 당신은 세트가 전혀 필요하지 않습니다.

    def unique(items):
        keep = []
    
        for item in items:
            if item not in keep:
                keep.append(item)
    
        return keep
    

    timeit을 사용하여 다음 결과를 얻었습니다.

    세트 포함 ([]) - 4.97210427363 세트 () - 4.65712377445 세트 없음 - 3.44865284975

  22. ==============================

    22.

    x = [] # Your list  of items that includes Duplicates
    
    # Assuming that your list contains items of only immutable data types
    
    dict_x = {} 
    
    dict_x = {item : item for i, item in enumerate(x) if item not in dict_x.keys()}
    # Average t.c. = O(n)* O(1) ; furthermore the dict comphrehension and generator like behaviour of enumerate adds a certain efficiency and pythonic feel to it.
    
    x = dict_x.keys() # if you want your output in list format 
    
  23. ==============================

    23.

    >>> x=[1,1,2,'a','a',3]
    >>> y = [ _x for _x in x if not _x in locals()['_[1]'] ]
    >>> y
    [1, 2, 'a', 3]
    

    "locals () [ '_ [1]']"은 (는) 생성되는 목록의 "비밀 이름"입니다.

  24. ==============================

    24.나는이 것이 빠르다는 것을 모른다. 그러나 적어도 그것은 간단하다.

    나는이 것이 빠르다는 것을 모른다. 그러나 적어도 그것은 간단하다.

    간단히 그것을 먼저 세트로 변환 한 다음 다시리스트로 변환하십시오.

    def unique(container):
      return list(set(container))
    
  25. ==============================

    25.1 회 통과.

    1 회 통과.

    a = [1,1,'a','b','c','c']
    
    new_list = []
    prev = None
    
    while 1:
        try:
            i = a.pop(0)
            if i != prev:
                new_list.append(i)
            prev = i
        except IndexError:
            break
    
  26. ==============================

    26.a = [1,2,3,4,5,7,7,8,8,9,9,3,45]

    a = [1,2,3,4,5,7,7,8,8,9,9,3,45]

    def unique (l) :

    ids={}
    for item in l:
        if not ids.has_key(item):
            ids[item]=item
    return  ids.keys()
    

    인쇄하다

    유일한 인쇄 (a)

    삽입 요소는 theta (n) 요소가 종료되는지 여부를 검색하는 데 일정 시간이 걸립니다. 모든 항목을 테스트하는 것은 또한 theta (n) 그래서 우리는이 해결책이 theta (n) 곰이 마음에 그 파이썬 사전은 해시 테이블에 의해 구현

  27. ==============================

    27.나는 어떤 테스트도하지 않았지만 가능한 알고리즘 중 하나는 두 번째 목록을 만들고 첫 번째 목록을 반복하는 것입니다. 항목이 두 번째 목록에 없으면 두 번째 목록에 추가하십시오.

    나는 어떤 테스트도하지 않았지만 가능한 알고리즘 중 하나는 두 번째 목록을 만들고 첫 번째 목록을 반복하는 것입니다. 항목이 두 번째 목록에 없으면 두 번째 목록에 추가하십시오.

    x = [1, 1, 2, 'a', 'a', 3]
    y = []
    for each in x:
        if each not in y:
            y.append(each)
    
  28. from https://stackoverflow.com/questions/89178/in-python-what-is-the-fastest-algorithm-for-removing-duplicates-from-a-list-so by cc-by-sa and MIT license