[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.
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.사용 :
사용 :
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.다음은 지금까지 가장 빠른 솔루션입니다 (다음 입력에 해당).
다음은 지금까지 가장 빠른 솔루션입니다 (다음 입력에 해당).
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.무엇이 가장 빠를 것인지는 중복 목록의 비율에 따라 다릅니다. 고유 한 항목이 거의없는 거의 모든 중복 항목 인 경우 새 목록을 만드는 것이 더 빠를 것입니다. 대부분 고유 항목 인 경우 원본 목록 (또는 사본)에서 제거하는 것이 더 빠릅니다.
무엇이 가장 빠를 것인지는 중복 목록의 비율에 따라 다릅니다. 고유 한 항목이 거의없는 거의 모든 중복 항목 인 경우 새 목록을 만드는 것이 더 빠를 것입니다. 대부분 고유 항목 인 경우 원본 목록 (또는 사본)에서 제거하는 것이 더 빠릅니다.
목록을 수정하는 방법은 다음과 같습니다.
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.이것은 내가 찾은 가장 빠른 곳에서의 방법입니다 (큰 비율의 중복을 가정 할 때) :
이것은 내가 찾은 가장 빠른 곳에서의 방법입니다 (큰 비율의 중복을 가정 할 때) :
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.필수 생성자 기반 변형 :
필수 생성자 기반 변형 :
def unique(seq): seen = set() for x in seq: if x not in seen: seen.add(x) yield x
-
==============================
7.이것은 가장 간단한 방법 일 수 있습니다 :
이것은 가장 간단한 방법 일 수 있습니다 :
list(OrderedDict.fromkeys(iterable))
파이썬 3.5부터는 OrderedDict가 이제 C로 구현되었으므로 이제는 가장 짧고, 가장 깨끗하고 빠릅니다.
-
==============================
8.짧막 한 농담:
짧막 한 농담:
new_list = reduce(lambda x,y: x+[y][:1-int(y in x)], my_list, [])
-
==============================
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.이것에 대한 내부 라이너 :
이것에 대한 내부 라이너 :
>>> x = [1, 1, 2, 'a', 'a', 3] >>> [ item for pos,item in enumerate(x) if x.index(item)==pos ] [1, 2, 'a', 3]
-
==============================
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.이것을 해결하기 위해 실제로 파이썬에서 정말 멋진 것을 할 수 있습니다. 지어 질 때 자신을 참조 할 수있는 목록 이해력을 생성 할 수 있습니다. 다음과 같이 :
이것을 해결하기 위해 실제로 파이썬에서 정말 멋진 것을 할 수 있습니다. 지어 질 때 자신을 참조 할 수있는 목록 이해력을 생성 할 수 있습니다. 다음과 같이 :
# 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.중복 물은 반드시 처음부터 목록에 있어야합니까? 오버 헤드가 없으면 요소를 찾지 만 요소를 추가하는 데 약간의 오버 헤드가 있습니다 (오버 헤드는 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.중복을 제거하고 광고 순서를 보존합니다.
중복을 제거하고 광고 순서를 보존합니다.
이것은 목록 내장 및 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.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.파이썬에서 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.위대하고 효율적인 솔루션이 있습니다. 그러나 절대 가장 효율적인 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.다음은 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.필자는 파이썬에 대한 경험이 없지만 알고리즘은 목록을 정렬 한 다음 목록에서 이전 항목과 비교하여 중복을 제거하고 마지막으로 이전 목록과 비교하여 새 목록의 위치를 찾습니다.
필자는 파이썬에 대한 경험이 없지만 알고리즘은 목록을 정렬 한 다음 목록에서 이전 항목과 비교하여 중복을 제거하고 마지막으로 이전 목록과 비교하여 새 목록의 위치를 찾습니다.
더 긴 대답 : http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560
-
==============================
20.
>>> def unique(list): ... y = [] ... for x in list: ... if x not in y: ... y.append(x) ... return y
-
==============================
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.
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.
>>> 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.나는이 것이 빠르다는 것을 모른다. 그러나 적어도 그것은 간단하다.
나는이 것이 빠르다는 것을 모른다. 그러나 적어도 그것은 간단하다.
간단히 그것을 먼저 세트로 변환 한 다음 다시리스트로 변환하십시오.
def unique(container): return list(set(container))
-
==============================
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.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.나는 어떤 테스트도하지 않았지만 가능한 알고리즘 중 하나는 두 번째 목록을 만들고 첫 번째 목록을 반복하는 것입니다. 항목이 두 번째 목록에 없으면 두 번째 목록에 추가하십시오.
나는 어떤 테스트도하지 않았지만 가능한 알고리즘 중 하나는 두 번째 목록을 만들고 첫 번째 목록을 반복하는 것입니다. 항목이 두 번째 목록에 없으면 두 번째 목록에 추가하십시오.
x = [1, 1, 2, 'a', 'a', 3] y = [] for each in x: if each not in y: y.append(each)
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
'PYTHON' 카테고리의 다른 글
[PYTHON] 파이썬에서 문자열의 반복 된 문자 계산하기 (0) | 2018.10.03 |
---|---|
[PYTHON] 파이썬 속성은 어떻게 작동합니까? (0) | 2018.10.03 |
[PYTHON] 파이썬에서 XML 문자열을 사전으로 변환하는 방법은 무엇입니까? (0) | 2018.10.03 |
[PYTHON] 파이썬 '자체'변수를 초급자에게 설명하기 [duplicate] (0) | 2018.10.03 |
[PYTHON] 이 파이썬 스 니펫에서 세미콜론이 허용되는 이유는 무엇입니까? (0) | 2018.10.03 |