El hecho de que yo era curiosa, aquí está la solución que marca la diferencia entre el 0, Falso , 0.0, etc. Se basa en ordenar la secuencia con my_cmp
que toma en consideración también el tipo de artículo. Es muy lento en comparación con las soluciones mencionadas anteriormente, por supuesto. Esto es debido a la clasificación. ¡Pero compare los resultados!
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
Imprime en mi consola:
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
¿Cuál es la complejidad de tiempo aquí? O (n * ln (n))? – Akavall
¿Asume que todas las entradas de la lista son hashable (ya que está creando claves de contador con ellas)? ¿Qué pasa si hay una lista como uno de los elementos de datos? – PaulMcG
Cuando lo pienso más, creo que la complejidad del tiempo es en realidad O (n). Cuando Counter crea un diccionario, tenemos que pasar por cada elemento una vez, luego cuando estamos recorriendo un diccionario, también observas cada elemento una vez (y el tiempo de búsqueda es constante). Por lo tanto, cuando aumenta el tamaño del problema, el tiempo para ejecutarlo aumenta en proporción lineal, es decir O (n). – Akavall