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]