목록에서 중복 제거

목록에서 중복 제거

파이썬으로 된 목록이 있습니다.

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

그리고 중복된 요소를 제거하고 싶습니다. 그것이 나는 사용할 수 .set하지만 유감스럽게도 그 목록은 해시할 수 없고 목록 집합을 만들 수 없습니다. 수 .따라서 모든 목록을 튜플로 전환한 다음 set을 사용하여 목록으로 되돌릴 수 있습니다.하지만 이것은 빠르지 않습니다.

가장 효율적인 방법은 무엇입니까?

위 목록의 결과는 다음과 같습니다.

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)

"루프인"(loop in)(오프라인 방식)이 가장 빠릅니다.긴 목록의 경우 그룹화 방식을 제외한 모든 사용자보다 빠릅니다.이게 말이 됩니까?

쇼트 리스트(코드에 있는 것)의 경우 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

>>> 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을 신중하게 이 많이 드는 이며, 라이브러리 모듈 "포인트코" "능성을드에 "대정력대 " "한드 " (" "A 특입코 B" 중게는측신 "하하정것 "은우매비 " 용이많이의스 "다 "니입듈일모리러브부이이 "라며준표세프로이드는"▁perform)▁careful,▁module▁")▁b▁(ance▁processments▁a▁code▁library▁inputpoint▁a▁of▁specific코다니입▁of듈모▁acode리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차 접근법은 나쁘지 않지만, 정렬과 그룹화가 더 낫습니다.등

(성능에 대한 집착이 시사하듯이) 이 작업이 Push-the-Boundary 애플리케이션의 핵심 내부 루프에 있는 경우, 다른 대표적인 입력 샘플에 대해 동일한 테스트 세트를 시도할 가치가 있으며, 휴리스틱하게 하나 또는 다른 접근 방식을 선택할 수 있는 간단한 측정을 감지할 수 있습니다(그러나 측정은 빨라야 합니다).물론).

또한 다른 대표성을 유지하는 것을 고려할 가치가 있습니다.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각 요소에 대해

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

꼭 더 빠를지는 모르겠지만 튜플과 세트를 사용할 필요는 없습니다.

튜플 및 {} 목록을 사용하여 중복 항목을 제거할 수 있습니다.

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

a_list = [
          [1,2],
          [1,2],
          [2,3],
          [3,4]
]

print (list(map(list,set(map(tuple,a_list)))))

출력:[[1, 2], [3, 4], [2, 3]]

심지어 당신의 "긴" 목록도 꽤 짧습니다.또한 실제 데이터와 일치하도록 선택하셨습니까?성능은 이러한 데이터의 실제 모습에 따라 달라집니다.예를 들어, 더 긴 목록을 만들기 위해 짧은 목록을 반복해서 표시할 수 있습니다.이는 2차 솔루션이 벤치마크에서는 선형이지만 실제로는 그렇지 않다는 것을 의미합니다.

실제로 큰 목록의 경우 집합 코드가 가장 좋습니다. 즉, 공간이 많이 필요하지만 선형 코드입니다.방법별 정렬 및 그룹화는 O(n log n)이며, 방법 내 루프는 분명히 2차이므로 n이 커짐에 따라 이러한 방법이 어떻게 확장되는지 알 수 있습니다.이것이 분석 중인 데이터의 실제 크기라면 누가 신경을 쓰겠습니까?아주 작습니다.

덧붙여서, 세트를 만들기 위해 중간 목록을 구성하지 않으면, 즉 교체할 경우 눈에 띄게 속도가 빨라지는 것을 보고 있습니다.

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

와 함께

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

실제 솔루션은 다음과 같은 추가 정보에 따라 달라질 수 있습니다.목록 목록이 정말 필요한 표현이라고 확신하십니까?

모든.set-이 문제에 대한 관련 솔루션은 지금까지 전체를 만드는 것을 요구합니다.set반복하기 전에

목록 목록을 반복하고 "보임"에 추가함으로써 이를 게으르게 만들고 동시에 질서를 유지할 수 있습니다.set그런 다음 이 추적기에서 목록을 찾을 수 없는 경우에만 목록을 제공합니다.set.

이것.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]]

참고:tuple목록은 해시할 수 없으므로 변환이 필요합니다.

튜플을 키로 하는 사전을 만들고 키를 인쇄합니다.

• 튜플을 키로 사용하고 인덱스를 값으로 사용하여 사전 만들기
• 사전 키 목록 인쇄

---

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

이상하게도 위의 답변은 '중복'을 제거합니다. 하지만 중복된 값도 제거하려면 어떻게 해야 합니까?다음은 유용해야 하며 메모리에 새 개체를 만들지 않습니다!

def dictRemoveDuplicates(self):
    a=[[1,'somevalue1'],[1,'somevalue2'],[2,'somevalue1'],[3,'somevalue4'],[5,'somevalue5'],[5,'somevalue1'],[5,'somevalue1'],[5,'somevalue8'],[6,'somevalue9'],[6,'somevalue0'],[6,'somevalue1'],[7,'somevalue7']]


print(a)
temp = 0
position = -1
for pageNo, item in a:
    position+=1
    if pageNo != temp:
        temp = pageNo
        continue
    else:
        a[position] = 0
        a[position - 1] = 0
a = [x for x in a if x != 0]         
print(a)

O/P는 다음과 같습니다.

[[1, 'somevalue1'], [1, 'somevalue2'], [2, 'somevalue1'], [3, 'somevalue4'], [5, 'somevalue5'], [5, 'somevalue1'], [5, 'somevalue1'], [5, 'somevalue8'], [6, 'somevalue9'], [6, 'somevalue0'], [6, 'somevalue1'], [7, 'somevalue7']]
[[2, 'somevalue1'], [3, 'somevalue4'], [7, 'somevalue7']]

가장 간단한 해결책은 목록 목록을 튜플 목록으로 변환한 다음 적용하는 것입니다.dict.fromkeys()메소드를 다시 목록으로 변환합니다.

예:

당신은 가지고 있다k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

튜플목로변환k = list(map(tuple, k))

이것은 당신에게 줄 것입니다.[(1, 2), (4,), (5, 6, 2), (1, 2), (3,), (4,)]

나서: 그런다다수행다니합음을음.unique = list(dict.fromkeys(k))

당신은 갖게 될 것입니다.[(1, 2), (4,), (5, 6, 2), (3,)]

이상입니다.

이게 통할 겁니다.

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

약간의 배경은, 저는 방금 파이썬으로 시작했고 이해력을 배웠습니다.

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
dedup = [elem.split('.') for elem in set(['.'.join(str(int_elem) for int_elem in _list) for _list in k])]

만약 당신이 제안한 솔루션의 '빠르지는 않지만' 부분이 '충분히 간결하지는 않다'고 불만을 제기한다면, Python 3.5+에서 언팩 연산자와 간결한 튜플 표기법의 도움을 받아 체인화된 데이터 구조 변환을 매우 짧게 만들 수 있습니다(물론 이것은 O(n^2). 하지만 여전히 언팩이 직접 변환보다 약간 더 빠릅니다).

입력:

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
k = [*map(list, {*map(tuple, k)})]

# If you prefer comprehensions to map()
# k = [[*t] for t in {(*l,) for l in k}]

# Order-preserving alternative:
# k = [*map(list, dict.fromkeys(map(tuple, k)))]

print(k)

출력:

[[1, 2], [4], [5, 6, 2], [3]]

요소 순서를 그대로 유지하려는 경우

사용할 수 있습니다.dict.fromkeys()Python 3.7 이후에는 순서가 변경되지 않습니다.

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

[list(x) for x in dict.fromkeys(tuple(x) for x in k)]

#[[1, 2], [4], [5, 6, 2], [3]]

요소의 순서가 중요하지 않은 경우:

[list(x) for x in set(tuple(x) for x in k)]

#[[5, 6, 2], [1, 2], [3], [4]]

더 일반적이고 간단한 또 다른 해결책은 객체의 문자열 버전으로 키를 지정한 사전을 만들고 마지막에 값()을 가져오는 것입니다.

>>> dict([(unicode(a),a) for a in [["A", "A"], ["A", "A"], ["A", "B"]]]).values()
[['A', 'B'], ['A', 'A']]

단점은 문자열 표현이 충분히 고유한 키인 개체에만 적용된다는 것입니다(대부분의 기본 개체에 해당).

k=[[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [3], [8], [9]]
kl=[]
kl.extend(x for x in k if x not in kl)
k=list(kl)
print(k)

지문을 채취하고,

[[1, 2], [4], [5, 6, 2], [3], [5, 2], [8], [9]]

언급URL : https://stackoverflow.com/questions/2213923/removing-duplicates-from-a-list-of-lists