Как мне найти дубликаты в списке и создать из них другой список?
Как мне найти дубликаты в списке целых чисел и создать другой список дубликатов?
Переведено автоматически
Ответ 1
Чтобы удалить дубликаты, используйте 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 = set()
dupes = []
for x in a:
if x in seen:
dupes.append(x)
else:
seen.add(x)
или, более кратко:
seen = set()
dupes = [x for x in a if x in seen or seen.add(x)]
Если элементы списка нельзя хэшировать, вы не можете использовать наборы / dicts и должны прибегнуть к решению с квадратичным временем (сравните каждый с каждым). Например:
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]]
Ответ 2
Очень простое решение, но со сложностью O (n * n).
>>> xs = [1,2,3,4,4,5,5,6,1]
>>> set([x for x in xs if xs.count(x) > 1])
set([1, 4, 5])
Ответ 3
Вам не нужно подсчитывать, просто независимо от того, был ли элемент виден ранее. Адаптировал этот ответ к этой проблеме.:
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, в то время как предложенный мной метод кэширования, похоже, почти не дает эффекта.
$ 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
Ответ 4
Вы можете использовать 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 представляет время, поэтому меньшее значение означает лучшее. Это также логарифмический график, чтобы широкий диапазон значений можно было лучше визуализировать.:
Удалив O(n**2)
подходы, я выполнил другой тест до полумиллиона элементов в списке:
Как вы можете видеть, iteration_utilities.duplicates
подход быстрее, чем любой из других подходов, и даже объединение в цепочку unique_everseen(duplicates(...))
было быстрее или одинаково быстрым, чем другие подходы.
Здесь следует отметить еще одну интересную вещь: подходы pandas очень медленные для небольших списков, но могут легко конкурировать с более длинными списками.
Однако, как показывают эти тесты, большинство подходов работают примерно одинаково, поэтому не имеет большого значения, какой из них используется (за исключением 3, которые имели O(n**2)
время выполнения).
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
.