How do I find the duplicates in a list and create another list with them?

Как мне найти дубликаты в списке целых чисел и создать другой список дубликатов?

Чтобы удалить дубликаты, используйте 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]]

Очень простое решение, но со сложностью 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])

Вам не нужно подсчитывать, просто независимо от того, был ли элемент виден ранее. Адаптировал этот ответ к этой проблеме.:

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

Вы можете использовать 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.}