[PYTHON] 목록 목록에서 중복 제거
PYTHON목록 목록에서 중복 제거
나는 파이썬에서리스트의 목록을 가지고있다 :
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
그리고 그것에서 중복 요소를 제거하고 싶습니다. 그것은 내가 사용할 수있는 목록이 아닌 일반적인 목록일까요? 그러나 불행히도이 목록은 해시 가능하지 않으며 일련의 목록을 만들 수 없습니다. 튜플 만. 그래서 모든 목록을 터플로 바꿀 수 있고, 세트를 사용하여 목록으로 돌아갈 수 있습니다. 그러나 이것은 빠르지 않다.
이것이 가장 효율적인 방법으로 어떻게 할 수 있습니까?
위 목록의 결과는 다음과 같습니다.
k = [[5, 6, 2], [1, 2], [3], [4]]
나는 질서 유지에 신경 쓰지 않는다.
참고 :이 질문은 유사하지만 아주 필요한 것은 아닙니다. SO를 검색했지만 정확한 복제본을 찾지 못했습니다.
벤치마킹 :
import itertools, time
class Timer(object):
def __init__(self, name=None):
self.name = name
def __enter__(self):
self.tstart = time.time()
def __exit__(self, type, value, traceback):
if self.name:
print '[%s]' % self.name,
print 'Elapsed: %s' % (time.time() - self.tstart)
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [6], [8], [9]] * 5
N = 100000
print len(k)
with Timer('set'):
for i in xrange(N):
kt = [tuple(i) for i in k]
skt = set(kt)
kk = [list(i) for i in skt]
with Timer('sort'):
for i in xrange(N):
ks = sorted(k)
dedup = [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]
with Timer('groupby'):
for i in xrange(N):
k = sorted(k)
dedup = list(k for k, _ in itertools.groupby(k))
with Timer('loop in'):
for i in xrange(N):
new_k = []
for elem in k:
if elem not in new_k:
new_k.append(elem)
짧은 목록을 위해 가장 빠른 "루프 인"(2 차 방법). 긴리스트의 경우 groupby 메소드를 제외한 모든 사람들이 더 빠릅니다. 이게 말이 돼?
짧은 목록 (코드에있는 목록)을 보려면 100000 회 반복 :
[set] Elapsed: 1.3900001049
[sort] Elapsed: 0.891000032425
[groupby] Elapsed: 0.780999898911
[loop in] Elapsed: 0.578000068665
긴 목록 (코드에서 5 번 복제 된 목록) :
[set] Elapsed: 3.68700003624
[sort] Elapsed: 3.43799996376
[groupby] Elapsed: 1.03099989891
[loop in] Elapsed: 1.85900020599
해결법
-
==============================
1.
>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] >>> import itertools >>> k.sort() >>> list(k for k,_ in itertools.groupby(k)) [[1, 2], [3], [4], [5, 6, 2]]itertools는 종종 이런 종류의 문제에 대해 가장 빠르고 강력한 솔루션을 제공하며 친밀하게 친숙해질 가치가 있습니다! -)
편집 : 언급에서 언급했듯이, 일반적인 최적화 노력은 큰 투입물 (big-O 접근법)에 초점을 맞추고 있습니다. 왜냐하면 그것은 노력에 대한 좋은 수익을 제공하는 것이 훨씬 쉽기 때문입니다. 그러나 때로는 (근본적으로 성능 제한의 경계를 뛰어 넘는 코드의 깊은 내부 루프에서 "비극적으로 결정적인 병목 현상"을 위해), 확률 분포를 제공하고, 최적화 할 성능 측정치 (어쩌면 상한선 또는 상한선)를 결정해야 할 수도 있습니다. 첫 번째로 입력 데이터 특성에 따라 다른 알고리즘을 선택하는 등의 가능성이있는 검사를 수행하는 등 90 번째 센티미터가 평균 또는 중앙값보다 중요합니다.
"포인트"성능 (코드 A와 특정 입력에 대한 코드 B)을주의 깊게 측정하는 것은이 매우 많은 비용이 드는 프로세스의 일부이며 여기서는 표준 라이브러리 모듈 시간이 도움이됩니다. 그러나 쉘 프롬프트에서 사용하는 것이 더 쉽습니다. 예를 들어, 다음은이 문제에 대한 일반적인 접근 방식을 보여주는 간단한 모듈입니다. nodup.py로 저장하십시오.
import itertools k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] def doset(k, map=map, list=list, set=set, tuple=tuple): return map(list, set(map(tuple, k))) def dosort(k, sorted=sorted, xrange=xrange, len=len): ks = sorted(k) return [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]] def dogroupby(k, sorted=sorted, groupby=itertools.groupby, list=list): ks = sorted(k) return [i for i, _ in itertools.groupby(ks)] def donewk(k): newk = [] for i in k: if i not in newk: newk.append(i) return newk # sanity check that all functions compute the same result and don't alter k if __name__ == '__main__': savek = list(k) for f in doset, dosort, dogroupby, donewk: resk = f(k) assert k == savek print '%10s %s' % (f.__name__, sorted(resk))위도 체크 (파이썬 nodup.py를 할 때 수행됨)와 기본 hoisting 기술 (속도에 대한 각 함수의 로컬 전역 이름을 일정하게 유지)을 사용하여 모든 것들을 동일하게 배치하십시오.
이제 우리는 작은 예제 목록에 대한 검사를 할 수 있습니다 :
$ python -mtimeit -s'import nodup' 'nodup.doset(nodup.k)' 100000 loops, best of 3: 11.7 usec per loop $ python -mtimeit -s'import nodup' 'nodup.dosort(nodup.k)' 100000 loops, best of 3: 9.68 usec per loop $ python -mtimeit -s'import nodup' 'nodup.dogroupby(nodup.k)' 100000 loops, best of 3: 8.74 usec per loop $ python -mtimeit -s'import nodup' 'nodup.donewk(nodup.k)' 100000 loops, best of 3: 4.44 usec per loop이차 접근법은 중복 값이 거의없는 작은 목록의 경우 매력적 이도록 충분히 작은 상수를 가지고 있음을 확인했습니다. 중복없는 짧은 목록으로 :
$ python -mtimeit -s'import nodup' 'nodup.donewk([[i] for i in range(12)])' 10000 loops, best of 3: 25.4 usec per loop $ python -mtimeit -s'import nodup' 'nodup.dogroupby([[i] for i in range(12)])' 10000 loops, best of 3: 23.7 usec per loop $ python -mtimeit -s'import nodup' 'nodup.doset([[i] for i in range(12)])' 10000 loops, best of 3: 31.3 usec per loop $ python -mtimeit -s'import nodup' 'nodup.dosort([[i] for i in range(12)])' 10000 loops, best of 3: 25 usec per loop2 차 접근법은 나쁘지 않지만 sortby와 groupby가 더 좋습니다. 기타 등
성능에 대한 집착에 따라이 작업이 푸싱 경계 응용 프로그램의 핵심 내부 루프에있는 경우 다른 대표적인 입력 샘플에 대해 동일한 테스트 집합을 시도하여 경험적으로 하나 또는 다른 접근법을 선택하십시오 (그러나 측정 값은 물론 빠르지 만).
또한 k에 대한 다른 표현을 유지하는 것도 고려해 볼 가치가 있습니다 - 처음에는 튜플 집합이 아닌 목록 목록이되어야하는 이유는 무엇입니까? 중복 제거 작업이 빈번하고 프로파일 링이 프로그램의 성능 병목 현상을 나타내면 튜플 세트를 항상 유지하고 필요한 경우에만 목록을 가져 오는 것이 전체적으로 더 빠를 수 있습니다.
-
==============================
2.
>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] >>> k = sorted(k) >>> k [[1, 2], [1, 2], [3], [4], [4], [5, 6, 2]] >>> dedup = [k[i] for i in range(len(k)) if i == 0 or k[i] != k[i-1]] >>> dedup [[1, 2], [3], [4], [5, 6, 2]]필자는 필연적으로 더 빠를 지 모르지만 튜플과 세트를 사용할 필요는 없다.
-
==============================
3.수동으로 수행하여 새 k 목록을 만들고 지금까지 찾지 못한 항목을 추가합니다.
수동으로 수행하여 새 k 목록을 만들고 지금까지 찾지 못한 항목을 추가합니다.
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] new_k = [] for elem in k: if elem not in new_k: new_k.append(elem) k = new_k print k # prints [[1, 2], [4], [5, 6, 2], [3]]이해하기 쉽고 각 요소의 첫 번째 항목의 순서를 유지하는 것이 유용 할 수 있지만 각 요소에 대해 new_k 전체를 검색 할 때 복잡성이 2 차적이라고 생각합니다.
-
==============================
4."긴"목록조차도 꽤 짧습니다. 또한 실제 데이터와 일치하도록 선택 했습니까? 성능은 이러한 데이터가 실제로 어떻게 보이는지에 따라 달라집니다. 예를 들어, 짧은 목록을 반복하여 반복하여 목록을 만들 수 있습니다. 즉, 이차 솔루션은 벤치 마크에서 선형이지만 실제는 아닙니다.
"긴"목록조차도 꽤 짧습니다. 또한 실제 데이터와 일치하도록 선택 했습니까? 성능은 이러한 데이터가 실제로 어떻게 보이는지에 따라 달라집니다. 예를 들어, 짧은 목록을 반복하여 반복하여 목록을 만들 수 있습니다. 즉, 이차 솔루션은 벤치 마크에서 선형이지만 실제는 아닙니다.
실제로 큰 목록의 경우 세트 코드가 최선의 선택입니다. 공간이 부족하더라도 선형입니다. sort와 groupby 메쏘드는 O (n log n)이고 메쏘드의 반복문은 분명히 2 차적이므로, n이 실제로 커질수록 어떻게 확장 될지 알 수 있습니다. 이것이 분석 할 데이터의 실제 크기라면 누가 신경 쓰겠습니까? 그것은 아주 작습니다.
덧붙여 말하자면, 세트를 만들기 위해 중간 목록을 구성하지 않으면 눈에 띄는 속도 향상이 나타납니다. 즉,
kt = [tuple(i) for i in k] skt = set(kt)와
skt = set(tuple(i) for i in k)실제 해결책은 더 많은 정보에 달려 있습니다. 목록의 목록이 실제로 필요한 표현인지 확신합니까?
-
==============================
5.중복을 제거하는 데 튜플 및 {} 목록을 사용할 수 있습니다.
중복을 제거하는 데 튜플 및 {} 목록을 사용할 수 있습니다.
>>> [list(tupl) for tupl in {tuple(item) for item in k }] [[1, 2], [5, 6, 2], [3], [4]] >>> -
==============================
6.이 문제에 대한 모든 세트 관련 솔루션은 반복하기 전에 전체 세트를 생성해야합니다.
이 문제에 대한 모든 세트 관련 솔루션은 반복하기 전에 전체 세트를 생성해야합니다.
이것을 게으른 것으로 만들 수 있고, 동시에리스트를 반복하고 "보이는"세트에 추가함으로써 순서를 보존 할 수 있습니다. 그런 다음이 추적기 집합에 목록이없는 경우에만 목록을 생성합니다.
이 unique_everseen 제조법은 itertools 문서에서 사용할 수 있습니다. 타사 툴즈 라이브러리에서도 사용할 수 있습니다.
from toolz import unique k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] # lazy iterator res = map(list, unique(map(tuple, k))) print(list(res)) [[1, 2], [4], [5, 6, 2], [3]]목록은 해시 가능하지 않으므로 튜플 변환이 필요합니다.
-
==============================
7.이것은 효과가있다.
이것은 효과가있다.
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] k_cleaned = [] for ele in k: if set(ele) not in [set(x) for x in k_cleaned]: k_cleaned.append(ele) print(k_cleaned) # output: [[1, 2], [4], [5, 6, 2], [3]] -
==============================
8.아마 더 일반적이고 간단한 해결책은 문자열 버전의 객체에 의해 키가 생성되고 끝에 values ()를 가져 오는 사전을 만드는 것입니다.
아마 더 일반적이고 간단한 해결책은 문자열 버전의 객체에 의해 키가 생성되고 끝에 values ()를 가져 오는 사전을 만드는 것입니다.
>>> dict([(unicode(a),a) for a in [["A", "A"], ["A", "A"], ["A", "B"]]]).values() [['A', 'B'], ['A', 'A']]catch는 문자열 표현이 고유 한 키 (대부분의 원시 객체에 해당) 인 객체에만 적용됩니다.
-
==============================
9.튜플을 키로하여 사전을 만들고 키를 인쇄하십시오.
튜플을 키로하여 사전을 만들고 키를 인쇄하십시오.
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] dict_tuple = {tuple(item): index for index, item in enumerate(k)} print [list(itm) for itm in dict_tuple.keys()] # prints [[1, 2], [5, 6, 2], [3], [4]]
from https://stackoverflow.com/questions/2213923/removing-duplicates-from-a-list-of-lists by cc-by-sa and MIT license
'PYTHON' 카테고리의 다른 글
| [PYTHON] 파이썬 서버 "일반적으로 각 소켓 주소를 한 번만 사용할 수 있습니다" (0) | 2018.11.20 |
|---|---|
| [PYTHON] PIP : " 'ipython'을 (를) 제거 할 수 없습니다. 이것은 distutils가 설치 한 프로젝트이므로 정확하게 결정할 수 없습니다 ... " (0) | 2018.11.20 |
| [PYTHON] -e 옵션은 pip 설치시 유용합니다. (0) | 2018.11.20 |
| [PYTHON] URL에서 mp3를 재생하는 방법 (0) | 2018.11.20 |
| [PYTHON] 파이썬에서 많은리스트의 연결 (0) | 2018.11.20 |