[python] 목록 목록에서 중복 제거

>>> 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)의 세심한 측정은 매우 비용이 많이 드는이 프로세스의 일부이며 표준 라이브러리 모듈 timeit이 여기에 도움이됩니다. 그러나 쉘 프롬프트에서 사용하는 것이 더 쉽습니다. 예를 들어, 다음은이 문제에 대한 일반적인 접근 방식을 보여주는 짧은 모듈입니다 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))

온 전성 검사 (방금 수행 할 때 수행됨 python nodup.py)와 기본 권양 기술 (속도를 위해 각 기능에 대해 일정한 전역 이름을 로컬로 지정)을 확인하여 동일한 기반에 놓으십시오.

이제 작은 예제 목록에서 검사를 실행할 수 있습니다.

$ 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

2 차 접근법이 중복 된 값이 거의없는 작은 목록에 매력적으로 보이도록 상수가 충분히 작음을 확인합니다. 중복이없는 짧은 목록 :

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

2 차 접근 방식은 나쁘지 않지만 sort 및 groupby 접근 방식이 더 좋습니다. 기타 등등

(성능에 대한 집착에서 알 수 있듯이)이 작업이 경계를 넘나 드는 애플리케이션의 핵심 내부 루프에있는 경우 다른 대표적인 입력 샘플에 대해 동일한 테스트 세트를 시도해 볼 가치가 있습니다. 하나 또는 다른 접근 방식을 선택합니다 (물론 측정은 빠릅니다).

또한 다른 표현을 유지하는 것도 고려해 볼 가치가 있습니다. 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]]

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

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

kt = [tuple(i) for i in k]
skt = set(kt)

skt = set(tuple(i) for i in k)

>>> [list(tupl) for tupl in {tuple(item) for item in k }]
[[1, 2], [5, 6, 2], [3], [4]]
>>> 

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