Solo perché ero curioso, ecco la soluzione che fa la differenza fra 0, False , 0.0, ecc. Si basa sull'ordinamento della sequenza con my_cmp che prende in considerazione anche il tipo dell'articolo. È molto lento rispetto alle soluzioni sopra menzionate, ovviamente. Questo a causa dell'ordinamento. Ma confronta i risultati!
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
Esso stampa sulla mia console:
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
Qual è la complessità tempo qui? O (n * ln (n))? – Akavall
Questo presuppone che tutte le voci della lista siano lavabili (dato che si stanno creando chiavi contatore con esse)? E se ci fosse una lista come uno degli elementi di dati? – PaulMcG
Quando ci penso di più, penso che la complessità del tempo sia in realtà O (n). Quando Counter crea un dizionario, dobbiamo passare attraverso ogni elemento una volta, quindi quando eseguiamo il looping di un dizionario, guardate anche ogni elemento una volta (e cercate il tempo è costante). Quindi, quando la dimensione del problema aumenta, il tempo di eseguirlo aumenta in proporzione lineare, cioè O (n). – Akavall