카테고리 보관물: Python

Python

목록에서 중복 항목을 찾고 다른 목록을 만들려면 어떻게해야합니까? 중복 목록을

Python 목록에서 중복 항목을 찾고 다른 중복 목록을 만들려면 어떻게해야합니까? 이 목록에는 정수만 포함됩니다.

답변

중복을 제거하려면을 사용하십시오 set(a). 중복을 인쇄하려면 다음과 같이하십시오.

a = [1,2,3,2,1,5,6,5,5,5]

import collections
print([item for item, count in collections.Counter(a).items() if count > 1])

## [1, 2, 5]

참고 Counter특히 효율적인 (없는 타이밍 아마 과잉 여기)합니다. set더 잘 수행합니다. 이 코드는 소스 순서로 고유 한 요소 목록을 계산합니다.

seen = set()
uniq = []
for x in a:
    if x not in seen:
        uniq.append(x)
        seen.add(x)

또는 더 간결하게 :

seen = set()
uniq = [x for x in a if x not in seen and not seen.add(x)]

나는 후자의 스타일을 권장하지 않습니다. 왜냐하면 무엇 not seen.add(x)을하고 있는지 명확하지 않기 때문입니다 (set add()메소드는 항상을 반환 None하므로 필요합니다 not).

라이브러리없이 복제 된 요소 목록을 계산하려면 다음을 수행하십시오.

seen = {}
dupes = []

for x in a:
    if x not in seen:
        seen[x] = 1
    else:
        if seen[x] == 1:
            dupes.append(x)
        seen[x] += 1

리스트 요소가 해시 가능하지 않은 경우, 세트 / 딕션을 사용할 수 없으며 2 차 시간 솔루션에 의존해야합니다 (각 요소와 비교). 예를 들면 다음과 같습니다.

a = [[1], [2], [3], [1], [5], [3]]

no_dupes = [x for n, x in enumerate(a) if x not in a[:n]]
print no_dupes # [[1], [2], [3], [5]]

dupes = [x for n, x in enumerate(a) if x in a[:n]]
print dupes # [[1], [3]]

답변

>>> l = [1,2,3,4,4,5,5,6,1]
>>> set([x for x in l if l.count(x) > 1])
set([1, 4, 5])

답변

이전에 항목을 보았는지 여부에 관계없이 카운트가 필요하지 않습니다. 이 문제에 대한 답변 을 채택 했습니다 .

def list_duplicates(seq):
  seen = set()
  seen_add = seen.add
  # adds all elements it doesn't know yet to seen and all other to seen_twice
  seen_twice = set( x for x in seq if x in seen or seen_add(x) )
  # turn the set into a list (as requested)
  return list( seen_twice )

a = [1,2,3,2,1,5,6,5,5,5]
list_duplicates(a) # yields [1, 2, 5]

속도가 중요한 경우를 대비하여 다음과 같은 타이밍이 있습니다.

# file: test.py
import collections

def thg435(l):
    return [x for x, y in collections.Counter(l).items() if y > 1]

def moooeeeep(l):
    seen = set()
    seen_add = seen.add
    # adds all elements it doesn't know yet to seen and all other to seen_twice
    seen_twice = set( x for x in l if x in seen or seen_add(x) )
    # turn the set into a list (as requested)
    return list( seen_twice )

def RiteshKumar(l):
    return list(set([x for x in l if l.count(x) > 1]))

def JohnLaRooy(L):
    seen = set()
    seen2 = set()
    seen_add = seen.add
    seen2_add = seen2.add
    for item in L:
        if item in seen:
            seen2_add(item)
        else:
            seen_add(item)
    return list(seen2)

l = [1,2,3,2,1,5,6,5,5,5]*100

결과는 다음과 같습니다. (@ JohnLaRooy!)

$ python -mtimeit -s 'import test' 'test.JohnLaRooy(test.l)'
10000 loops, best of 3: 74.6 usec per loop
$ python -mtimeit -s 'import test' 'test.moooeeeep(test.l)'
10000 loops, best of 3: 91.3 usec per loop
$ python -mtimeit -s 'import test' 'test.thg435(test.l)'
1000 loops, best of 3: 266 usec per loop
$ python -mtimeit -s 'import test' 'test.RiteshKumar(test.l)'
100 loops, best of 3: 8.35 msec per loop

흥미롭게도 타이밍 자체 외에도 파이가 사용될 때 순위도 약간 변경됩니다. 가장 흥미롭게도 카운터 기반 접근 방식은 pypy의 최적화로부터 큰 이점을 얻는 반면 내가 제안한 방법 캐싱 접근 방식은 거의 효과가없는 것으로 보입니다.

$ pypy -mtimeit -s 'import test' 'test.JohnLaRooy(test.l)'
100000 loops, best of 3: 17.8 usec per loop
$ pypy -mtimeit -s 'import test' 'test.thg435(test.l)'
10000 loops, best of 3: 23 usec per loop
$ pypy -mtimeit -s 'import test' 'test.moooeeeep(test.l)'
10000 loops, best of 3: 39.3 usec per loop

이 효과는 입력 데이터의 “중복성”과 관련이 있습니다. 나는 l = [random.randrange(1000000) for i in xrange(10000)]이 결과를 설정 하고 얻었습니다.

$ pypy -mtimeit -s 'import test' 'test.moooeeeep(test.l)'
1000 loops, best of 3: 495 usec per loop
$ pypy -mtimeit -s 'import test' 'test.JohnLaRooy(test.l)'
1000 loops, best of 3: 499 usec per loop
$ pypy -mtimeit -s 'import test' 'test.thg435(test.l)'
1000 loops, best of 3: 1.68 msec per loop

답변

당신은 사용할 수 있습니다 iteration_utilities.duplicates:

>>> from iteration_utilities import duplicates

>>> list(duplicates([1,1,2,1,2,3,4,2]))
[1, 1, 2, 2]

또는 각 복제본 중 하나만 원하는 경우 다음과 결합 할 수 있습니다 iteration_utilities.unique_everseen.

>>> from iteration_utilities import unique_everseen

>>> list(unique_everseen(duplicates([1,1,2,1,2,3,4,2])))
[1, 2]

또한 해싱 할 수없는 요소를 처리 할 수 ​​있습니다 (단, 성능 저하).

>>> list(duplicates([[1], [2], [1], [3], [1]]))
[[1], [1]]

>>> list(unique_everseen(duplicates([[1], [2], [1], [3], [1]])))
[[1]]

그것은 다른 접근 방식 중 일부만이 처리 할 수있는 것입니다.

벤치 마크

여기에 언급 된 대부분의 접근법을 포함하는 빠른 벤치 마크를 수행했습니다.

첫 번째 벤치 마크에는 일부 목록 길이 만 포함 되었기 때문에 일부 접근 방식에는 O(n**2) .

그래프에서 y 축은 시간을 나타내므로 값이 작을수록 좋습니다. 또한 log-log를 플로팅하여 광범위한 값을 더 잘 시각화 할 수 있습니다.

여기에 이미지 설명을 입력하십시오

O(n**2)접근 방식을 제거하고 목록에서 최대 50 만 개의 요소를 벤치 마크했습니다.

여기에 이미지 설명을 입력하십시오

보시다시피 iteration_utilities.duplicates접근 방식은 다른 접근 방식보다 훨씬 빠릅니다.unique_everseen(duplicates(...)) 보다 빠르며 보다 빠르거나 동일합니다.

여기서 주목해야 할 또 하나의 흥미로운 점은 팬더 접근 방식이 작은 목록의 경우 속도가 느리지 만 더 긴 목록의 경우 경쟁하기 쉽다는 것입니다.

그러나 이러한 벤치 마크에서는 대부분의 접근 방식이 거의 동일하게 수행되므로 어느 것이 사용되는지는 중요하지 않습니다 ( O(n**2)런타임 이있는 3은 제외 ).

from iteration_utilities import duplicates, unique_everseen
from collections import Counter
import pandas as pd
import itertools

def georg_counter(it):
    return [item for item, count in Counter(it).items() if count > 1]

def georg_set(it):
    seen = set()
    uniq = []
    for x in it:
        if x not in seen:
            uniq.append(x)
            seen.add(x)

def georg_set2(it):
    seen = set()
    return [x for x in it if x not in seen and not seen.add(x)]

def georg_set3(it):
    seen = {}
    dupes = []

    for x in it:
        if x not in seen:
            seen[x] = 1
        else:
            if seen[x] == 1:
                dupes.append(x)
            seen[x] += 1

def RiteshKumar_count(l):
    return set([x for x in l if l.count(x) > 1])

def moooeeeep(seq):
    seen = set()
    seen_add = seen.add
    # adds all elements it doesn't know yet to seen and all other to seen_twice
    seen_twice = set( x for x in seq if x in seen or seen_add(x) )
    # turn the set into a list (as requested)
    return list( seen_twice )

def F1Rumors_implementation(c):
    a, b = itertools.tee(sorted(c))
    next(b, None)
    r = None
    for k, g in zip(a, b):
        if k != g: continue
        if k != r:
            yield k
            r = k

def F1Rumors(c):
    return list(F1Rumors_implementation(c))

def Edward(a):
    d = {}
    for elem in a:
        if elem in d:
            d[elem] += 1
        else:
            d[elem] = 1
    return [x for x, y in d.items() if y > 1]

def wordsmith(a):
    return pd.Series(a)[pd.Series(a).duplicated()].values

def NikhilPrabhu(li):
    li = li.copy()
    for x in set(li):
        li.remove(x)

    return list(set(li))

def firelynx(a):
    vc = pd.Series(a).value_counts()
    return vc[vc > 1].index.tolist()

def HenryDev(myList):
    newList = set()

    for i in myList:
        if myList.count(i) >= 2:
            newList.add(i)

    return list(newList)

def yota(number_lst):
    seen_set = set()
    duplicate_set = set(x for x in number_lst if x in seen_set or seen_set.add(x))
    return seen_set - duplicate_set

def IgorVishnevskiy(l):
    s=set(l)
    d=[]
    for x in l:
        if x in s:
            s.remove(x)
        else:
            d.append(x)
    return d

def it_duplicates(l):
    return list(duplicates(l))

def it_unique_duplicates(l):
    return list(unique_everseen(duplicates(l)))

벤치 마크 1

from simple_benchmark import benchmark
import random

funcs = [
    georg_counter, georg_set, georg_set2, georg_set3, RiteshKumar_count, moooeeeep,
    F1Rumors, Edward, wordsmith, NikhilPrabhu, firelynx,
    HenryDev, yota, IgorVishnevskiy, it_duplicates, it_unique_duplicates
]

args = {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(2, 12)}

b = benchmark(funcs, args, 'list size')

b.plot()

벤치 마크 2

funcs = [
    georg_counter, georg_set, georg_set2, georg_set3, moooeeeep,
    F1Rumors, Edward, wordsmith, firelynx,
    yota, IgorVishnevskiy, it_duplicates, it_unique_duplicates
]

args = {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(2, 20)}

b = benchmark(funcs, args, 'list size')
b.plot()

기권

1 이것은 내가 작성한 타사 라이브러리에서 가져온 것입니다 iteration_utilities.

답변

관련 질문을 보면서이 질문을 보았는데 아무도 왜 발전기 기반 솔루션을 제공하지 않았습니까? 이 문제를 해결하는 방법은 다음과 같습니다.

>>> print list(getDupes_9([1,2,3,2,1,5,6,5,5,5]))
[1, 2, 5]

나는 확장성에 관심이 있었기 때문에 작은 목록에서 잘 작동하는 순진한 항목을 포함하여 몇 가지 접근 방식을 테스트했지만 목록이 커질수록 끔찍하게 확장됩니다 (주의는 timeit을 사용하는 것이 좋았지 만 이것은 예시 적입니다).

나는 비교를 위해 @moooeeeep (입력 목록이 완전히 임의의 경우 가장 빠름)과 itertools 접근 방식을 포함하여 대부분 정렬 된 목록에 대해 더 빠릅니다. @ firelynx의 팬더 접근 방식을 포함합니다. 끔찍하고 간단합니다. 참고-정렬 / 티 / 우편 접근 방식은 내 컴퓨터에서 주로 대부분의 정렬 된 목록에 대해 가장 빠르며, moooeeeep는 셔플 목록에 대해 가장 빠르지 만 마일리지는 다를 수 있습니다.

장점

  • 동일한 코드를 사용하여 ‘임의’복제본을 테스트하는 매우 빠르고 간단합니다.

가정

  • 중복은 한 번만보고해야합니다
  • 중복 주문을 보존 할 필요는 없습니다
  • 목록의 아무 곳에 나 중복이있을 수 있습니다.

가장 빠른 솔루션, 1m 항목 :

def getDupes(c):
        '''sort/tee/izip'''
        a, b = itertools.tee(sorted(c))
        next(b, None)
        r = None
        for k, g in itertools.izip(a, b):
            if k != g: continue
            if k != r:
                yield k
                r = k

테스트 된 접근법

import itertools
import time
import random

def getDupes_1(c):
    '''naive'''
    for i in xrange(0, len(c)):
        if c[i] in c[:i]:
            yield c[i]

def getDupes_2(c):
    '''set len change'''
    s = set()
    for i in c:
        l = len(s)
        s.add(i)
        if len(s) == l:
            yield i

def getDupes_3(c):
    '''in dict'''
    d = {}
    for i in c:
        if i in d:
            if d[i]:
                yield i
                d[i] = False
        else:
            d[i] = True

def getDupes_4(c):
    '''in set'''
    s,r = set(),set()
    for i in c:
        if i not in s:
            s.add(i)
        elif i not in r:
            r.add(i)
            yield i

def getDupes_5(c):
    '''sort/adjacent'''
    c = sorted(c)
    r = None
    for i in xrange(1, len(c)):
        if c[i] == c[i - 1]:
            if c[i] != r:
                yield c[i]
                r = c[i]

def getDupes_6(c):
    '''sort/groupby'''
    def multiple(x):
        try:
            x.next()
            x.next()
            return True
        except:
            return False
    for k, g in itertools.ifilter(lambda x: multiple(x[1]), itertools.groupby(sorted(c))):
        yield k

def getDupes_7(c):
    '''sort/zip'''
    c = sorted(c)
    r = None
    for k, g in zip(c[:-1],c[1:]):
        if k == g:
            if k != r:
                yield k
                r = k

def getDupes_8(c):
    '''sort/izip'''
    c = sorted(c)
    r = None
    for k, g in itertools.izip(c[:-1],c[1:]):
        if k == g:
            if k != r:
                yield k
                r = k

def getDupes_9(c):
    '''sort/tee/izip'''
    a, b = itertools.tee(sorted(c))
    next(b, None)
    r = None
    for k, g in itertools.izip(a, b):
        if k != g: continue
        if k != r:
            yield k
            r = k

def getDupes_a(l):
    '''moooeeeep'''
    seen = set()
    seen_add = seen.add
    # adds all elements it doesn't know yet to seen and all other to seen_twice
    for x in l:
        if x in seen or seen_add(x):
            yield x

def getDupes_b(x):
    '''iter*/sorted'''
    x = sorted(x)
    def _matches():
        for k,g in itertools.izip(x[:-1],x[1:]):
            if k == g:
                yield k
    for k, n in itertools.groupby(_matches()):
        yield k

def getDupes_c(a):
    '''pandas'''
    import pandas as pd
    vc = pd.Series(a).value_counts()
    i = vc[vc > 1].index
    for _ in i:
        yield _

def hasDupes(fn,c):
    try:
        if fn(c).next(): return True    # Found a dupe
    except StopIteration:
        pass
    return False

def getDupes(fn,c):
    return list(fn(c))

STABLE = True
if STABLE:
    print 'Finding FIRST then ALL duplicates, single dupe of "nth" placed element in 1m element array'
else:
    print 'Finding FIRST then ALL duplicates, single dupe of "n" included in randomised 1m element array'
for location in (50,250000,500000,750000,999999):
    for test in (getDupes_2, getDupes_3, getDupes_4, getDupes_5, getDupes_6,
                 getDupes_8, getDupes_9, getDupes_a, getDupes_b, getDupes_c):
        print 'Test %-15s:%10d - '%(test.__doc__ or test.__name__,location),
        deltas = []
        for FIRST in (True,False):
            for i in xrange(0, 5):
                c = range(0,1000000)
                if STABLE:
                    c[0] = location
                else:
                    c.append(location)
                    random.shuffle(c)
                start = time.time()
                if FIRST:
                    print '.' if location == test(c).next() else '!',
                else:
                    print '.' if [location] == list(test(c)) else '!',
                deltas.append(time.time()-start)
            print ' -- %0.3f  '%(sum(deltas)/len(deltas)),
        print
    print

‘all dupes’테스트의 결과는 일관성이있어이 배열에서 “first”duplicate와 “all”duplicate를 찾습니다.

Finding FIRST then ALL duplicates, single dupe of "nth" placed element in 1m element array
Test set len change :    500000 -  . . . . .  -- 0.264   . . . . .  -- 0.402
Test in dict        :    500000 -  . . . . .  -- 0.163   . . . . .  -- 0.250
Test in set         :    500000 -  . . . . .  -- 0.163   . . . . .  -- 0.249
Test sort/adjacent  :    500000 -  . . . . .  -- 0.159   . . . . .  -- 0.229
Test sort/groupby   :    500000 -  . . . . .  -- 0.860   . . . . .  -- 1.286
Test sort/izip      :    500000 -  . . . . .  -- 0.165   . . . . .  -- 0.229
Test sort/tee/izip  :    500000 -  . . . . .  -- 0.145   . . . . .  -- 0.206  *
Test moooeeeep      :    500000 -  . . . . .  -- 0.149   . . . . .  -- 0.232
Test iter*/sorted   :    500000 -  . . . . .  -- 0.160   . . . . .  -- 0.221
Test pandas         :    500000 -  . . . . .  -- 0.493   . . . . .  -- 0.499

목록이 먼저 뒤섞이면 정렬 가격이 명백해집니다. 효율이 눈에 띄게 떨어지고 @moooeeeep 접근 방식이 지배적이며 set & dict 접근 방식은 비슷하지만 성능이 떨어집니다.

Finding FIRST then ALL duplicates, single dupe of "n" included in randomised 1m element array
Test set len change :    500000 -  . . . . .  -- 0.321   . . . . .  -- 0.473
Test in dict        :    500000 -  . . . . .  -- 0.285   . . . . .  -- 0.360
Test in set         :    500000 -  . . . . .  -- 0.309   . . . . .  -- 0.365
Test sort/adjacent  :    500000 -  . . . . .  -- 0.756   . . . . .  -- 0.823
Test sort/groupby   :    500000 -  . . . . .  -- 1.459   . . . . .  -- 1.896
Test sort/izip      :    500000 -  . . . . .  -- 0.786   . . . . .  -- 0.845
Test sort/tee/izip  :    500000 -  . . . . .  -- 0.743   . . . . .  -- 0.804
Test moooeeeep      :    500000 -  . . . . .  -- 0.234   . . . . .  -- 0.311  *
Test iter*/sorted   :    500000 -  . . . . .  -- 0.776   . . . . .  -- 0.840
Test pandas         :    500000 -  . . . . .  -- 0.539   . . . . .  -- 0.540

답변

팬더 사용하기 :

>>> import pandas as pd
>>> a = [1, 2, 1, 3, 3, 3, 0]
>>> pd.Series(a)[pd.Series(a).duplicated()].values
array([1, 3, 3])

답변

카운터는 Python 2.7의 새로운 기능입니다.


Python 2.5.4 (r254:67916, May 31 2010, 15:03:39)
[GCC 4.1.2 20080704 (Red Hat 4.1.2-46)] on linux2
a = [1,2,3,2,1,5,6,5,5,5]
import collections
print [x for x, y in collections.Counter(a).items() if y > 1]
Type "help", "copyright", "credits" or "license" for more information.
  File "", line 1, in
AttributeError: 'module' object has no attribute 'Counter'
>>>

이전 버전에서는 일반적인 dict을 대신 사용할 수 있습니다.

a = [1,2,3,2,1,5,6,5,5,5]
d = {}
for elem in a:
    if elem in d:
        d[elem] += 1
    else:
        d[elem] = 1

print [x for x, y in d.items() if y > 1]