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

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.

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

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ć :-(.

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))

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

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:

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:

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()

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

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]

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"]

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

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

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

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

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\

def check_duplicates(my_list):
    seen = {}
    for item in my_list:
        if seen.get(item):
            return True
        seen[item] = True
    return False