Jak sprawdzić, czy na płaskiej liście znajdują się duplikaty?

185

Na przykład, biorąc pod uwagę listę ['one', 'two', 'one'], algorytm powinien zwrócić True, a biorąc pod uwagę, ['one', 'two', 'three']że powinien zwrócić False.

teggy
źródło

Odpowiedzi:

398

Służy set()do usuwania duplikatów, jeśli wszystkie wartości są haszowalne :

>>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True
Denis Otkidach
źródło
17
Przed przeczytaniem tego spróbowałem your_list! = List (set (your_list)), który nie będzie działał, ponieważ kolejność elementów ulegnie zmianie. Użycie len jest dobrym sposobem na rozwiązanie tego problemu
igniteflow
1
często nie działa dla szeregu zmiennoprzecinkowych. Zobacz stackoverflow.com/questions/60914705
Manas Dogra
54

Zalecane tylko dla krótkich list:

any(thelist.count(x) > 1 for x in thelist)

Czy nie używać na długiej liście - może to potrwać proporcjonalna do kwadratu liczby pozycji na liście!

W przypadku dłuższych list z elementami haszującymi (ciągi, liczby i c):

def anydup(thelist):
  seen = set()
  for x in thelist:
    if x in seen: return True
    seen.add(x)
  return False

Jeśli twoich przedmiotów nie da się ukryć (listy podrzędne, dykta itp.), Staje się bardziej włochaty, choć nadal można uzyskać O (N logN), jeśli są co najmniej porównywalne. Ale musisz znać lub przetestować właściwości elementów (możliwe do skrótu lub nie, porównywalne lub nie), aby uzyskać najlepszą możliwą wydajność - O (N) w przypadku skrótów, O (N log N) w przypadku nieudanych skrótów, w przeciwnym razie zależy od O (N do kwadratu) i nic nie można na to poradzić :-(.

Alex Martelli
źródło
21
Denis Otkidach zaproponował rozwiązanie, w którym wystarczy zbudować nowy zestaw z listy, a następnie sprawdzić jego długość. Jego zaletą jest to, że pozwala ciężkiemu podnieść kod C w Pythonie. Twoje rozwiązanie zapętla się w kodzie Pythona, ale ma tę zaletę, że powoduje zwarcie po znalezieniu pojedynczego dopasowania. Jeśli istnieje prawdopodobieństwo, że lista prawdopodobnie nie ma duplikatów, podoba mi się wersja Denisa Otkidacha, ale jeśli istnieje prawdopodobieństwo, że na początku listy może pojawić się duplikat, to rozwiązanie jest lepsze.
steveha
1
Warto dopracować za szczegóły, chociaż myślę, że Denis miał lepsze rozwiązanie.
Steve314,
@steveha - przedwczesna optymalizacja?
Steve314
@ Steve314, jaka przedwczesna optymalizacja? Napisałbym to tak, jak napisał to Denis Otkidach, więc starałem się zrozumieć, dlaczego Alex Martelli (znany ze słownika Python Cookbook) napisał to inaczej. Po tym, jak trochę się nad tym zastanowiłem, zdałem sobie sprawę, że wersja Alexa powoduje zwarcie i opublikowałem kilka uwag na temat różnic. Jak przejść od dyskusji o różnicach do przedwczesnej optymalizacji, która jest źródłem wszelkiego zła?
steveha
3
Jeśli elementy są haszowalne, ustalone rozwiązanie jest bardziej bezpośrednie, a sposób, w jaki to wyraziłem, szybszy (wychodzi, gdy tylko odpowiedź będzie znana - „zwarcia”, ujął to Steveha). Budowanie proponowanego słownika (najszybszy jako zbiór. Licznik) jest oczywiście znacznie wolniejsze (wymaga, aby allwszystkie liczyły się jako 1). Dykt ze wszystkimi wartościami Prawda, o którym również wspominasz, jest absurdalnie, bezużyteczną naśladownictwem set, bez żadnej wartości dodanej. Big-O to nie wszystko w programowaniu.
Alex Martelli,
12

To stare, ale odpowiedzi tutaj doprowadziły mnie do nieco innego rozwiązania. Jeśli jesteś skłonny do nadużywania rozumienia, możesz w ten sposób doprowadzić do zwarcia.

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))
pirospada
źródło
9

Jeśli lubisz funkcjonalny styl programowania, oto przydatna funkcja, samodokumentowany i przetestowany kod za pomocą 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()

Stamtąd możesz przetestować niepowtarzalność, sprawdzając, czy drugi element zwracanej pary jest pusty:

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]

Zauważ, że nie jest to wydajne, ponieważ jawnie konstruujesz rozkład. Ale zgodnie z zasadą zmniejszania można uzyskać coś równoważnego (ale nieco mniej wydajnego), aby odpowiedzieć 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
Xavier Decoret
źródło
Najpierw powinienem przeczytać powiązane pytania. Jest to opisane w stackoverflow.com/questions/1723072/...
Xavier Decoret
1
Zgłasza mi błąd „niepoprawnej składni” funkcji lambda funkcji decompose ()
raffaem
Jest tak, ponieważ w Pythonie 3.x usunięto rozpakowywanie list argumentów lambda.
MSeifert,
5

Pomyślałem, że przydałoby się porównać terminy różnych przedstawionych tutaj rozwiązań. Do tego użyłem własnej biblioteki simple_benchmark:

wprowadź opis zdjęcia tutaj

Rzeczywiście, w tym przypadku rozwiązanie Denisa Otkidacha jest najszybsze.

Niektóre z podejść wykazują również znacznie bardziej stromą krzywą, są to podejścia, które skalują się kwadratowo z liczbą elementów (pierwsze rozwiązanie Alexa Martellisa, wjandrea i oba rozwiązania Xaviera Decoretsa). Należy również wspomnieć, że rozwiązanie pand z Keiku ma bardzo duży stały czynnik. Ale w przypadku większych list prawie dogania inne rozwiązania.

W przypadku, gdy duplikat znajduje się na pierwszej pozycji. Jest to przydatne, aby zobaczyć, które rozwiązania powodują zwarcie:

wprowadź opis zdjęcia tutaj

Tutaj kilka podejść nie powoduje zwarcia: Kaiku, Frank, Xavier_Decoret (pierwsze rozwiązanie), Turn, Alex Martelli (pierwsze rozwiązanie) i podejście przedstawione przez Denisa Otkidacha (który był najszybszy w przypadku bez duplikatów).

Dołączyłem tutaj funkcję z własnej biblioteki: iteration_utilities.all_distinct która może konkurować z najszybszym rozwiązaniem w przypadku braku duplikatów i działa w stałym czasie dla przypadku duplikowania na początku (choć nie tak szybko).

Kod testu porównawczego:

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)

A dla argumentów:


# 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()
MSeifert
źródło
Dla porównania: Funkcja all_distinct jest napisany w C .
użytkownik
5

Niedawno odpowiedziałem na powiązane pytanie, aby ustalić wszystkie duplikaty na liście za pomocą generatora. Ma tę zaletę, że jeśli zostanie użyte tylko do ustalenia „jeśli jest duplikat”, wystarczy zdobyć pierwszy przedmiot, a resztę można zignorować, co jest ostatecznym skrótem.

Jest to interesujące podejście oparte na zestawie, które zaadaptowałem prosto z moooeeeep :

def getDupes(l):
    seen = set()
    seen_add = seen.add
    for x in l:
        if x in seen or seen_add(x):
            yield x

W związku z tym byłaby pełna lista duplikatów list(getDupes(etc)). Aby po prostu przetestować „jeśli” istnieje duplikat, należy go owinąć w następujący sposób:

def hasDupes(l):
    try:
        if getDupes(l).next(): return True    # Found a dupe
    except StopIteration:
        pass
    return False

To dobrze się skaluje i zapewnia stały czas działania wszędzie tam, gdzie duplikat znajduje się na liście - testowałem z listami do 1m wpisów. Jeśli wiesz coś o danych, w szczególności o tym, że duplikaty najprawdopodobniej pojawią się w pierwszej połowie, lub o innych rzeczach, które pozwolą ci zmienić wymagania, na przykład konieczność uzyskania rzeczywistych duplikatów, istnieje kilka naprawdę alternatywnych lokalizatorów duplikatów to może przewyższyć. Dwa polecam to ...

Proste podejście oparte na nagraniu, bardzo czytelne:

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

Wykorzystaj narzędzia itertools (zasadniczo ifilter / izip / tee) na posortowanej liście, bardzo wydajne, jeśli otrzymujesz wszystkie duplikaty, ale nie tak szybko, aby uzyskać tylko pierwszy:

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

Były to najlepsze wyniki z podejść, które próbowałem uzyskać pełną listę duplikatów , przy czym pierwszy duplikat występował w dowolnym miejscu na liście elementów o długości 1 m od początku do środka. Zaskakujące było to, jak niewiele wrzucił krok sortowania. Twój przebieg może się różnić, ale oto moje konkretne wyniki czasowe:

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
F1Rumors
źródło
.next()Wezwanie w drugim bloku kodu nie działa na Python 3.x. Myślę, że next(getDupes(l))powinien działać w różnych wersjach Pythona, więc warto to zmienić.
MSeifert,
Również ifilteri ìzipmoże być po prostu zastąpione przez wbudowany filteroraz zipw Pythonie 3.x.
MSeifert,
@MSeifert rozwiązanie działa dla Pythona 2.x jak napisano, i tak, dla py3 możesz użyć filtra i mapy bezpośrednio ... ale ktoś korzystający z rozwiązania py3 w bazie kodu py2 nie uzyskałby korzyści, ponieważ nie działałby jako generator. W tym przypadku wyraźne jest lepsze niż niejawne;)
F1Rumors
3

Innym sposobem robienia tego zwięźle jest Counter .

Aby ustalić, czy na oryginalnej liście są jakieś duplikaty:

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

Lub uzyskać listę elementów, które mają duplikaty:

def get_dupes(l):
    return [k for k, v in Counter(l).items() if v > 1]
Skręcać
źródło
2
my_list = ['one', 'two', 'one']

duplicates = []

for value in my_list:
  if my_list.count(value) > 1:
    if value not in duplicates:
      duplicates.append(value)

print(duplicates) //["one"]
Jay Desai
źródło
1

Stwierdziłem, że zapewnia to najlepszą wydajność, ponieważ powoduje zwarcie operacji, gdy znaleziono pierwszą kopię, a następnie algorytm ten ma złożoność czasową i przestrzenną O (n), gdzie n jest długością listy:

def has_duplicated_elements(iterable):
    """ Given an `iterable`, return True if there are duplicated entries. """
    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
użytkownik
źródło
0

Naprawdę nie wiem, co robi zestaw za kulisami, więc po prostu lubię to upraszczać.

def dupes(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
Szczery
źródło
0

Prostsze rozwiązanie jest następujące. Po prostu sprawdź True / False .duplicated()metodą pandy , a następnie zbierz sumę. Zobacz także dokumentację pandas.Series.duplicated - panda 0.24.1

import pandas as pd

def has_duplicated(l):
    return pd.Series(l).duplicated().sum() > 0

print(has_duplicated(['one', 'two', 'one']))
# True
print(has_duplicated(['one', 'two', 'three']))
# False
Keiku
źródło
0

Jeśli lista zawiera elementy nieukrywalne, możesz użyć rozwiązania Alexa Martellego, ale z listą zamiast zestawu, chociaż jest wolniejsza dla większych danych wejściowych: O (N ^ 2).

def has_duplicates(iterable):
    seen = []
    for x in iterable:
        if x in seen:
            return True
        seen.append(x)
    return False
wjandrea
źródło
0

Użyłem podejścia pirospade ze względu na jego prostotę i zmodyfikowałem go nieco na krótkiej liście z rejestru Windows bez rozróżniania wielkości liter.

Jeśli nieprzetworzony ciąg wartości PATH zostanie podzielony na poszczególne ścieżki, wszystkie ścieżki „puste” (ciągi puste lub tylko białe znaki) można usunąć za pomocą:

PATH_nonulls = [s for s in PATH if s.strip()]

def HasDupes(aseq) :
    s = set()
    return any(((x.lower() in s) or s.add(x.lower())) for x in aseq)

def GetDupes(aseq) :
    s = set()
    return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))

def DelDupes(aseq) :
    seen = set()
    return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]

Oryginalna ścieżka zawiera zarówno „zerowe” wpisy, jak i duplikaty do celów testowych:

[list]  Root paths in HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment:PATH[list]  Root paths in HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment
  1  C:\Python37\
  2
  3
  4  C:\Python37\Scripts\
  5  c:\python37\
  6  C:\Program Files\ImageMagick-7.0.8-Q8
  7  C:\Program Files (x86)\poppler\bin
  8  D:\DATA\Sounds
  9  C:\Program Files (x86)\GnuWin32\bin
 10  C:\Program Files (x86)\Intel\iCLS Client\
 11  C:\Program Files\Intel\iCLS Client\
 12  D:\DATA\CCMD\FF
 13  D:\DATA\CCMD
 14  D:\DATA\UTIL
 15  C:\
 16  D:\DATA\UHELP
 17  %SystemRoot%\system32
 18
 19
 20  D:\DATA\CCMD\FF%SystemRoot%
 21  D:\DATA\Sounds
 22  %SystemRoot%\System32\Wbem
 23  D:\DATA\CCMD\FF
 24
 25
 26  c:\
 27  %SYSTEMROOT%\System32\WindowsPowerShell\v1.0\
 28

Ścieżki zerowe zostały usunięte, ale nadal mają duplikaty, np. (1, 3) i (13, 20):

    [list]  Null paths removed from HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment:PATH
  1  C:\Python37\
  2  C:\Python37\Scripts\
  3  c:\python37\
  4  C:\Program Files\ImageMagick-7.0.8-Q8
  5  C:\Program Files (x86)\poppler\bin
  6  D:\DATA\Sounds
  7  C:\Program Files (x86)\GnuWin32\bin
  8  C:\Program Files (x86)\Intel\iCLS Client\
  9  C:\Program Files\Intel\iCLS Client\
 10  D:\DATA\CCMD\FF
 11  D:\DATA\CCMD
 12  D:\DATA\UTIL
 13  C:\
 14  D:\DATA\UHELP
 15  %SystemRoot%\system32
 16  D:\DATA\CCMD\FF%SystemRoot%
 17  D:\DATA\Sounds
 18  %SystemRoot%\System32\Wbem
 19  D:\DATA\CCMD\FF
 20  c:\
 21  %SYSTEMROOT%\System32\WindowsPowerShell\v1.0\

I wreszcie duplikaty zostały usunięte:

[list]  Massaged path list from in HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment:PATH
  1  C:\Python37\
  2  C:\Python37\Scripts\
  3  C:\Program Files\ImageMagick-7.0.8-Q8
  4  C:\Program Files (x86)\poppler\bin
  5  D:\DATA\Sounds
  6  C:\Program Files (x86)\GnuWin32\bin
  7  C:\Program Files (x86)\Intel\iCLS Client\
  8  C:\Program Files\Intel\iCLS Client\
  9  D:\DATA\CCMD\FF
 10  D:\DATA\CCMD
 11  D:\DATA\UTIL
 12  C:\
 13  D:\DATA\UHELP
 14  %SystemRoot%\system32
 15  D:\DATA\CCMD\FF%SystemRoot%
 16  %SystemRoot%\System32\Wbem
 17  %SYSTEMROOT%\System32\WindowsPowerShell\v1.0\
Hewey Dewey
źródło
0
def check_duplicates(my_list):
    seen = {}
    for item in my_list:
        if seen.get(item):
            return True
        seen[item] = True
    return False
Ahmed Meraj
źródło
Jak działa funkcja? Jestem ciekawy, jak zapełniony jest słownik „widziany”.
mountaincaler