Jaki jest dobry pytonowy sposób znajdowania zduplikowanych obiektów?

Question

Często używam sorted i groupby, aby znaleźć duplikaty przedmiotów w iteracji. Teraz widzę, że jest zawodna:

from itertools import groupby 
data = 3 * ('x ', (1,), u'x') 
duplicates = [k for k, g in groupby(sorted(data)) if len(list(g)) > 1] 
print duplicates 
# [] printed - no duplicates found - like 9 unique values 

Powodem powyżej kodu w Pythonie 2.x nie jest wyjaśnione here.

Co to jest wiarygodny, pytonowy sposób znajdowania duplikatów?

Szukałem podobnych pytań/odpowiedzi na temat SO. Najlepszym z nich jest "In Python, how do I take a list and reduce it to a list of duplicates?", ale akceptowane rozwiązanie nie jest pythonic (jest to multilinię proceduralną dla ... jeśli ... dodaj ... else ... dodaj ... return result), a inne rozwiązania są niewiarygodne (zależy od niespełnionej tranzyty operatora "<" lub jest powolna (O n * n).

[EDIT] Zamknięte. Przyjęta odpowiedź pomogła mi podsumować wnioski w mojej odpowiedzi poniżej bardziej ogólnej.

Lubię używać typów wbudowanych do reprezentowania np. struktury drzew. Właśnie dlatego obawiam się teraz wymieszać.

Answer 1

Uwaga: Zakłada wpisy są hashable

>>> from collections import Counter 
>>> data = 3 * ('x ', (1,), u'x') 
>>> [k for k, c in Counter(data).iteritems() if c > 1] 
[u'x', 'x ', (1,)] 

Answer 2

Wniosek:

• Jeśli wszystkie elementy są hashable i jest przynajmniej Python 2.7, najlepszym rozwiązaniem jest powyżej collections.Counter.
• Jeśli niektóre elementy nie są hashable lub Python 2.7+ nie jest obecny, to rozwiązanie groupby(sorted(..)) jest bardzo dobra w warunkach
  • nie łączą str i Unicode lub
  • nie używać wszelkiego rodzaju z nazwą umieszczoną pomiędzy aphabetically "str" ​​i "unicode". (Typowo „krotki” lub „typ”)
• Jeśli dane są unhashable i mieszanych typów, nic powyżej mogą być używane, a następnie najlepiej jest użyć:
  • Counter(map(pickled.dumps, data)) zamiast Counter(data) i wreszcie unpickle to albo
  • groupby(sorted(data, key=pickled.dumps)) jeśli unpickling jest niepożądane lub brak python 2,7
• A „naive solution” omówione poniżej mogą być lepsze niż wytrawiania dla bardzo niewielkiej liczby elementów approximatel y mniej niż 300.

Wszystkie inne rozwiązania w innych pytań są gorsze komunikatu.

Uwagi:

• Wygląda, że ​​Counter klasy mogą być kopiowane & wklejony do obniżenia wersji Pythona.
• "naive solution", który przeszukuje każdy element w całych danych, może być użyty dla bardzo małej liczby elementów. Ma tę zaletę, że nie wymaga danych hashable i nie zależy od przechodniości domyślnego operatora "<", ale dla ponad 25 elementów hashable jest lepszy licznik i dla ponad 300 niepodłączalnych "dzikich" przedmiotów jest lepszy licznik na marynowane przedmiotów.

myślałem o wstępne sortowanie pozycji według typu lub przedłużyć je hash dla hashable przedmioty, pomaga obecnie, ale nie jest to bezpieczne rozwiązanie, ponieważ sam problem będzie z „<” operator insite listy, krotki itp

Answer 3

Ten temat jest dla mnie interesujący, dlatego zaplanowałem powyższe rozwiązanie w porównaniu z rozwiązaniem zaakceptowanym w innym wątku.

Metoda licznika polega na tym, że ten wątek jest bardzo elegancki; jednak zaakceptowana odpowiedź w tym wątku wydaje się być około 2 razy szybsza.

import random as rn 
import timeit 
from collections import Counter 

a = [rn.randint(0,100000) for i in xrange(10000)] 

def counter_way(x): 
    return [k for k,v in Counter(x).iteritems() if v > 1] 

def accepted_way(x): #accepted answer in the linked thread 
    duplicates = set() 
    found = set() 
    for item in x: 
     if item in found: 
      duplicates.add(item) 
     else:   
      found.add(item) 
    return duplicates 


t1 = timeit.timeit('counter_way(a)', 'from __main__ import counter_way, a', number = 100) 
print "counter_way: ", t1 
t2 = timeit.timeit('accepted_way(a)','from __main__ import accepted_way, a', number = 100) 
print "accepted_way: ", t2 

Wyniki:

counter_way: 1.15775845813 
accepted_way: 0.531060022992 

Próbowałem to w różnych specyfikacjach i wynik zawsze taki sam.

Answer 4

Istnieje jednak pułapka w obu rozwiązaniach. Powodem jest to, że łączy wartości z tym samym hash. To zależy od tego, czy użyte wartości mogą mieć ten sam skrót. To nie jest tak szalony komentarz, jak mogłoby się wydawać (byłem także zaskoczony wcześniej), ponieważ Python w jakiś szczególny sposób miesza pewne wartości. Spróbuj:

from collections import Counter 


def counter_way(x): 
    return [k for k,v in Counter(x).iteritems() if v > 1] 

def accepted_way(x): #accepted answer in the linked thread 
    duplicates = set() 
    found = set() 
    for item in x: 
     if item in found: 
      duplicates.add(item) 
     else:   
      found.add(item) 
    return duplicates 


a = ('x ', (1,), u'x') * 2 

print 'The values:', a 
print 'Counter way duplicates:', counter_way(a) 
print 'Accepted way duplicates:', accepted_way(a) 
print '-' * 50 

# Now the problematic values. 
a = 2 * (0, 1, True, False, 0.0, 1.0) 

print 'The values:', a 
print 'Counter way duplicates:', counter_way(a) 
print 'Accepted way duplicates:', accepted_way(a) 

wartościach 1, 1,0, i prawda mają ten sam hash z definicji, i podobnie 0, 0.0, i fałszywe. Drukuje następujących na mojej konsoli (myślę o ostatnich dwóch liniach - wszystkie wartości powinny być rzeczywiście duplikatów):

c:\tmp\___python\hynekcer\so10247815>python d.py 
The values: ('x ', (1,), u'x', 'x ', (1,), u'x') 
Counter way duplicates: [u'x', 'x ', (1,)] 
Accepted way duplicates: set([u'x', 'x ', (1,)]) 
-------------------------------------------------- 
The values: (0, 1, True, False, 0.0, 1.0, 0, 1, True, False, 0.0, 1.0) 
Counter way duplicates: [0, 1] 
Accepted way duplicates: set([False, True]) 

Answer 5

Tylko dlatego, że był ciekawy, tutaj jest rozwiązanie, które sprawia, że ​​różnica między 0, False , 0,0 itd. Oparte jest ono na sortowaniu sekwencji z my_cmp, która uwzględnia również typ elementu. Jest to bardzo powolne w porównaniu z wyżej wymienionymi rozwiązaniami, oczywiście. Dzieje się tak z powodu sortowania. Ale porównaj wyniki!

import sys 
import timeit 
from collections import Counter 

def empty(x): 
    return 

def counter_way(x): 
    return [k for k,v in Counter(x).iteritems() if v > 1] 

def accepted_way(x): #accepted answer in the linked thread 
    duplicates = set() 
    found = set() 
    for item in x: 
     if item in found: 
      duplicates.add(item) 
     else:   
      found.add(item) 
    return duplicates 


def my_cmp(a, b): 
    result = cmp(a, b) 
    if result == 0: 
     return cmp(id(type(a)), id(type(b))) 
    return result  


def duplicates_via_sort_with_types(x, my_cmp=my_cmp): 

    last = '*** the value that cannot be in the sequence by definition ***' 
    duplicates = [] 
    added = False 
    for e in sorted(x, cmp=my_cmp): 
     if my_cmp(e, last) == 0: 
      ##print 'equal:', repr(e), repr(last), added 
      if not added: 
       duplicates.append(e) 
       ##print 'appended:', e 
       added = True 
     else: 
      ##print 'different:', repr(e), repr(last), added 
      last = e 
      added = False 
    return duplicates 


a = [0, 1, True, 'a string', u'a string', False, 0.0, 1.0, 2, 2.0, 1000000, 1000000.0] * 1000 

print 'Counter way duplicates:', counter_way(a) 
print 'Accepted way duplicates:', accepted_way(a) 
print 'Via enhanced sort:', duplicates_via_sort_with_types(a) 
print '-' * 50 

# ... and the timing 
t3 = timeit.timeit('empty(a)','from __main__ import empty, a', number = 100) 
print "empty: ", t3 
t1 = timeit.timeit('counter_way(a)', 'from __main__ import counter_way, a', number = 100) 
print "counter_way: ", t1 
t2 = timeit.timeit('accepted_way(a)','from __main__ import accepted_way, a', number = 100) 
print "accepted_way: ", t2 
t4 = timeit.timeit('duplicates_via_sort_with_types(a)','from __main__ import duplicates_via_sort_with_types, a', number = 100) 
print "duplicates_via_sort_with_types: ", t4 

Drukuje na mojej konsoli:

c:\tmp\___python\hynekcer\so10247815>python e.py 
Counter way duplicates: [0, 1, 2, 'a string', 1000000] 
Accepted way duplicates: set([False, True, 2.0, u'a string', 1000000.0]) 
Via enhanced sort: [False, 0.0, 0, True, 1.0, 1, 2.0, 2, 1000000.0, 1000000, 'a string', u'a string'] 
-------------------------------------------------- 
empty: 2.11195471969e-05 
counter_way: 0.76977053612 
accepted_way: 0.496547434023 
duplicates_via_sort_with_types: 11.2378848197