예를 들어 list가 주어지면 ['one', 'two', 'one']알고리즘은을 반환해야 True하고, 주어진 알고리즘은을 반환 ['one', 'two', 'three']해야합니다 False.
답변
set()모든 값이 해시 가능한 경우 중복을 제거하는 데 사용하십시오 .
>>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True답변
짧은 목록에만 권장 됩니다.
any(thelist.count(x) > 1 for x in thelist)긴 목록 에는 사용 하지 마십시오. 목록에있는 항목 수의 제곱 에 비례하여 시간이 걸릴 수 있습니다 !
해시 가능한 항목 (문자열, 숫자 및 & C)이있는 더 긴 목록의 경우 :
def anydup(thelist):
seen = set()
for x in thelist:
if x in seen: return True
seen.add(x)
return False아이템이 해시 가능하지 않은 경우 (하위 목록, dicts 등) 더 비싸지 만 적어도 비교 가능한 경우 O (N logN)을 얻을 수 있습니다. 그러나 가능한 최고의 성능을 얻으려면 항목의 특성 (해시 가능 여부, 비교 가능 여부)을 알고 테스트해야합니다. 그것은 O (N squared)로 내려 가고 그것에 대해 할 수있는 일은 없습니다 :-(.
답변
이것은 오래되었지만 여기의 대답으로 인해 약간 다른 해결책이 생겼습니다. 이해력을 남용하려는 경우 이러한 방식으로 단락시킬 수 있습니다.
xs = [1, 2, 1]
s = set()
any(x in s or s.add(x) for x in xs)
# You can use a similar approach to actually retrieve the duplicates.
s = set()
duplicates = set(x for x in xs if x in s or s.add(x))답변
함수형 프로그래밍 스타일을 좋아한다면 doctest를 사용하여 자체 문서화되고 테스트 된 유용한 함수가 있습니다.
def decompose(a_list):
"""Turns a list into a set of all elements and a set of duplicated elements.
Returns a pair of sets. The first one contains elements
that are found at least once in the list. The second one
contains elements that appear more than once.
>>> decompose([1,2,3,5,3,2,6])
(set([1, 2, 3, 5, 6]), set([2, 3]))
"""
return reduce(
lambda (u, d), o : (u.union([o]), d.union(u.intersection([o]))),
a_list,
(set(), set()))
if __name__ == "__main__":
import doctest
doctest.testmod()여기에서 반환 된 쌍의 두 번째 요소가 비어 있는지 확인하여 단일성을 테스트 할 수 있습니다.
def is_set(l):
"""Test if there is no duplicate element in l.
>>> is_set([1,2,3])
True
>>> is_set([1,2,1])
False
>>> is_set([])
True
"""
return not decompose(l)[1]분해를 명시 적으로 구성하기 때문에 이는 효율적이지 않습니다. 그러나 reduce 사용 라인을 따라 5에 대답하는 것과 동등한 (그러나 약간 덜 효율적인) 것을 얻을 수 있습니다.
def is_set(l):
try:
def func(s, o):
if o in s:
raise Exception
return s.union([o])
reduce(func, l, set())
return True
except:
return False답변
여기에 제시된 다양한 솔루션의 타이밍을 비교하는 것이 유용 할 것이라고 생각했습니다. 이를 위해 내 라이브러리를 사용했습니다 simple_benchmark.
따라서이 경우 Denis Otkidach 의 솔루션 이 가장 빠릅니다.
일부 접근 방식은 훨씬 가파른 곡선을 나타내며, 요소 수에 따라 2 차적으로 확장되는 접근 방식입니다 (Alex Martellis 첫 번째 솔루션, wjandrea 및 Xavier Decorets 솔루션 모두). 또한 Keiku의 팬더 솔루션은 매우 큰 상수를 가지고 있습니다. 그러나 큰 목록의 경우 다른 솔루션과 거의 일치합니다.
그리고 중복이 첫 번째 위치에있는 경우. 이것은 어떤 솔루션이 단락되는지 확인하는 데 유용합니다.
여기에는 Kaiku, Frank, Xavier_Decoret (첫 번째 솔루션), Turn, Alex Martelli (첫 번째 솔루션) 및 Denis Otkidach가 제시 한 접근법 (중복없는 경우에서 가장 빠름)이 있습니다.
여기에 내 라이브러리의 함수가 포함되어 있습니다.이 기능은 iteration_utilities.all_distinct중복이없는 경우 가장 빠른 솔루션과 경쟁 할 수 있으며 시작시 복제 된 경우에 대해 일정한 시간에 수행합니다 (가장 빠르지는 않지만).
벤치 마크 코드 :
from collections import Counter
from functools import reduce
import pandas as pd
from simple_benchmark import BenchmarkBuilder
from iteration_utilities import all_distinct
b = BenchmarkBuilder()
@b.add_function()
def Keiku(l):
return pd.Series(l).duplicated().sum() > 0
@b.add_function()
def Frank(num_list):
unique = []
dupes = []
for i in num_list:
if i not in unique:
unique.append(i)
else:
dupes.append(i)
if len(dupes) != 0:
return False
else:
return True
@b.add_function()
def wjandrea(iterable):
seen = []
for x in iterable:
if x in seen:
return True
seen.append(x)
return False
@b.add_function()
def user(iterable):
clean_elements_set = set()
clean_elements_set_add = clean_elements_set.add
for possible_duplicate_element in iterable:
if possible_duplicate_element in clean_elements_set:
return True
else:
clean_elements_set_add( possible_duplicate_element )
return False
@b.add_function()
def Turn(l):
return Counter(l).most_common()[0][1] > 1
def getDupes(l):
seen = set()
seen_add = seen.add
for x in l:
if x in seen or seen_add(x):
yield x
@b.add_function()
def F1Rumors(l):
try:
if next(getDupes(l)): return True # Found a dupe
except StopIteration:
pass
return False
def decompose(a_list):
return reduce(
lambda u, o : (u[0].union([o]), u[1].union(u[0].intersection([o]))),
a_list,
(set(), set()))
@b.add_function()
def Xavier_Decoret_1(l):
return not decompose(l)[1]
@b.add_function()
def Xavier_Decoret_2(l):
try:
def func(s, o):
if o in s:
raise Exception
return s.union([o])
reduce(func, l, set())
return True
except:
return False
@b.add_function()
def pyrospade(xs):
s = set()
return any(x in s or s.add(x) for x in xs)
@b.add_function()
def Alex_Martelli_1(thelist):
return any(thelist.count(x) > 1 for x in thelist)
@b.add_function()
def Alex_Martelli_2(thelist):
seen = set()
for x in thelist:
if x in seen: return True
seen.add(x)
return False
@b.add_function()
def Denis_Otkidach(your_list):
return len(your_list) != len(set(your_list))
@b.add_function()
def MSeifert04(l):
return not all_distinct(l)그리고 논쟁을 위해 :
# No duplicate run
@b.add_arguments('list size')
def arguments():
for exp in range(2, 14):
size = 2**exp
yield size, list(range(size))
# Duplicate at beginning run
@b.add_arguments('list size')
def arguments():
for exp in range(2, 14):
size = 2**exp
yield size, [0, *list(range(size)]
# Running and plotting
r = b.run()
r.plot()답변
최근에 발전기를 사용하여 목록의 모든 복제본 을 설정 하는 관련 질문에 대답했습니다 . ‘중복이있는 경우’만 설정하면 첫 번째 항목을 가져와 나머지를 무시할 수 있다는 장점이 있습니다. 이는 바로 가기입니다.
이것은 moooeeeep 에서 직접 적용한 흥미로운 세트 기반 접근 방식입니다 .
def getDupes(l):
seen = set()
seen_add = seen.add
for x in l:
if x in seen or seen_add(x):
yield x따라서 전체 듀피 목록은 다음과 같습니다 list(getDupes(etc)). 듀프가있는 경우 단순히 “if”를 테스트하려면 다음과 같이 랩핑해야합니다.
def hasDupes(l):
try:
if getDupes(l).next(): return True # Found a dupe
except StopIteration:
pass
return False이것은 확장 성이 뛰어나고 Dupe가 목록에있는 어느 곳에서나 일관된 작동 시간을 제공합니다. 최대 1m 항목 목록으로 테스트했습니다. 데이터에 대해 구체적으로 말하면, 듀피가 상반기에 나타날 가능성이 있거나 실제 듀피를 얻는 것과 같이 요구 사항을 왜곡시킬 수있는 다른 것들이 있다면 실제로 대체 듀피 로케이터가 있습니다. 그 성능을 능가 할 수 있습니다. 내가 추천하는 두 가지는 …
읽기 쉬운 간단한 dict 기반 접근 방식 :
def getDupes(c):
d = {}
for i in c:
if i in d:
if d[i]:
yield i
d[i] = False
else:
d[i] = True정렬 된 목록에서 itertools (본질적으로 ifilter / izip / tee)를 활용하십시오. 첫 번째를 얻는 것만 큼 빠르지는 않지만 모든 속임수를 얻는 경우 매우 효율적입니다.
def getDupes(c):
a, b = itertools.tee(sorted(c))
next(b, None)
r = None
for k, g in itertools.ifilter(lambda x: x[0]==x[1], itertools.izip(a, b)):
if k != r:
yield k
r = k이들은 전체 dupe 목록에 대해 시도한 접근법에서 최고의 성과를 냈으며 첫 번째 dupe는 처음부터 중간까지 1m 요소 목록에서 발생했습니다. 정렬 단계가 추가되는 오버 헤드가 얼마나 적은지는 놀라운 일이었습니다. 마일리지가 다를 수 있지만 다음은 구체적인 시간 결과입니다.
Finding FIRST duplicate, single dupe places "n" elements in to 1m element array
Test set len change : 50 - . . . . . -- 0.002
Test in dict : 50 - . . . . . -- 0.002
Test in set : 50 - . . . . . -- 0.002
Test sort/adjacent : 50 - . . . . . -- 0.023
Test sort/groupby : 50 - . . . . . -- 0.026
Test sort/zip : 50 - . . . . . -- 1.102
Test sort/izip : 50 - . . . . . -- 0.035
Test sort/tee/izip : 50 - . . . . . -- 0.024
Test moooeeeep : 50 - . . . . . -- 0.001 *
Test iter*/sorted : 50 - . . . . . -- 0.027
Test set len change : 5000 - . . . . . -- 0.017
Test in dict : 5000 - . . . . . -- 0.003 *
Test in set : 5000 - . . . . . -- 0.004
Test sort/adjacent : 5000 - . . . . . -- 0.031
Test sort/groupby : 5000 - . . . . . -- 0.035
Test sort/zip : 5000 - . . . . . -- 1.080
Test sort/izip : 5000 - . . . . . -- 0.043
Test sort/tee/izip : 5000 - . . . . . -- 0.031
Test moooeeeep : 5000 - . . . . . -- 0.003 *
Test iter*/sorted : 5000 - . . . . . -- 0.031
Test set len change : 50000 - . . . . . -- 0.035
Test in dict : 50000 - . . . . . -- 0.023
Test in set : 50000 - . . . . . -- 0.023
Test sort/adjacent : 50000 - . . . . . -- 0.036
Test sort/groupby : 50000 - . . . . . -- 0.134
Test sort/zip : 50000 - . . . . . -- 1.121
Test sort/izip : 50000 - . . . . . -- 0.054
Test sort/tee/izip : 50000 - . . . . . -- 0.045
Test moooeeeep : 50000 - . . . . . -- 0.019 *
Test iter*/sorted : 50000 - . . . . . -- 0.055
Test set len change : 500000 - . . . . . -- 0.249
Test in dict : 500000 - . . . . . -- 0.145
Test in set : 500000 - . . . . . -- 0.165
Test sort/adjacent : 500000 - . . . . . -- 0.139
Test sort/groupby : 500000 - . . . . . -- 1.138
Test sort/zip : 500000 - . . . . . -- 1.159
Test sort/izip : 500000 - . . . . . -- 0.126
Test sort/tee/izip : 500000 - . . . . . -- 0.120 *
Test moooeeeep : 500000 - . . . . . -- 0.131
Test iter*/sorted : 500000 - . . . . . -- 0.157답변
간결하게이 작업을 수행하는 또 다른 방법은 Counter 입니다.
원본 목록에 중복이 있는지 확인하려면 다음을 수행하십시오.
from collections import Counter
def has_dupes(l):
# second element of the tuple has number of repetitions
return Counter(l).most_common()[0][1] > 1또는 중복 된 항목 목록을 얻으려면
def get_dupes(l):
return [k for k, v in Counter(l).items() if v > 1]