tengo un contenedor cont. Si quiero saber si tiene duplicados, solo verificaré len(cont) == len(set(cont)).Python: encontrar un duplicado en un recipiente de manera eficiente
Supongamos que quiero encontrar un elemento duplicado si existe (cualquier elemento duplicado arbitraria). ¿Hay alguna forma ordenada y eficiente de escribir eso?
[Python 3]
Ok, mi primera respuesta ha sido bastante floja, así que pensé en probar algunas formas diferentes de hacer esto y reportar las diferencias. Aquí está mi código.
import sys
import itertools
def getFirstDup(c, toTest):
# Original idea using list slicing => 5.014 s
if toTest == '1':
for i in xrange(0, len(c)):
if c[i] in c[:i]:
return c[i]
# Using two sets => 4.305 s
elif toTest == '2':
s = set()
for i in c:
s2 = s.copy()
s.add(i)
if len(s) == len(s2):
return i
# Using dictionary LUT => 0.763 s
elif toTest == '3':
d = {}
for i in c:
if i in d:
return i
else:
d[i] = 1
# Using set operations => 0.772 s
elif toTest == '4':
s = set()
for i in c:
if i in s:
return i
else:
s.add(i)
# Sorting then walking => 5.130 s
elif toTest == '5':
c = sorted(c)
for i in xrange(1, len(c)):
if c[i] == c[i - 1]:
return c[i]
# Sorting then groupby-ing => 5.086 s
else:
c = sorted(c)
for k, g in itertools.groupby(c):
if len(list(g)) > 1:
return k
return None
c = list(xrange(0, 10000000))
c[5000] = 0
for i in xrange(0, 10):
print getFirstDup(c, sys.argv[1])
Básicamente, trato de esto de seis maneras diferentes, como se indica en el archivo fuente. He utilizado el comando Linux time y recogieron los tiempos de ejecución en tiempo real, la ejecución de los comandos al igual que
time python ./test.py 1
con 1 ser que el algoritmo que quería probar. Cada algoritmo busca el primer duplicado en 10,000,000 de enteros y se ejecuta diez veces. Hay una duplicación en la lista, que está "en su mayoría ordenadas", aunque lo intenté revertir listas ordenadas y sin notar una diferencia proporcional entre los algoritmos.
Mi sugerencia original hizo mal en 5.014 s. Mi comprensión de la solución de icyrock.com también fue deficiente a las 4.305 s. Luego intenté usar un diccionario para crear una LUT, que dio el mejor tiempo de ejecución a 0.763 s. He intentado utilizar el operador in en conjuntos, y obtuve 0,772 s, casi tan buenos como el diccionario LUT. Traté de ordenar y caminar la lista, que dio un tiempo lastimoso de 5.130 s. Finalmente, probé la sugerencia de John Machin de las itertools, que dio un tiempo de 5.086 s.
En resumen, un diccionario LUT parece ser el camino a seguir, con operaciones de conjuntos (que puede utilizar en su aplicación LUT) que es un cercano segundo lugar.
Actualización: Me trató la sugerencia de razpeitia, y aparte del hecho de que lo que necesita saber exactamente lo que copia de la llave que está buscando, el algoritmo real hizo el peor hasta el momento (66.366 s).
Actualización 2: Estoy seguro de que alguien va a decir que esta prueba es parcial porque la ubicación duplicado es cerca de un extremo de la lista. ¡Intenta ejecutar el código usando una ubicación diferente antes de la votación negativa e informa tus resultados!
Esa es una manera realmente mala de probar. Debe ponerlos cada uno en su propia función y usar el módulo [timeit] (http://docs.python.org/library/timeit.html). Esto cortará cosas como el tiempo de inicio. – aaronasterling
@aaronsterling: Esto no fue especialmente elegante. Estoy más interesado en las tendencias generales que en los tiempos específicos, y además estaba harto de que mi primer intento fuera rechazado por personas que supusieron que era un mal algoritmo, pero que no tenían datos para respaldarlo. Esto no es gran información, pero son datos; la próxima vez usaré el módulo timeit. – Zeke
+1 por poner el esfuerzo. ¡No tome personalmente los votos negativos, piense en ello como una experiencia de aprendizaje! – fmark
puede empezar a añadir que el conjunto y tan pronto como se intenta agregar el elemento que ya está en el conjunto que has encontrado un duplicado.
Tiene que escanear todos los elementos para los duplicados, ya que pueden ser los últimos que revisa, por lo que no puede ser más eficiente que el peor caso O (N) de tiempo, al igual que la búsqueda lineal. Pero una simple búsqueda lineal para encontrar un duplicado utilizará la memoria O (N), porque necesita hacer un seguimiento de lo que ha visto hasta ahora.
Si la matriz está ordenada puede encontrar duplicados en O (N) sin utilizar cualquier memoria adicional, ya que los pares duplicados serán uno junto al otro.
Prueba esto:
def getFirstDup(cont):
for i in xrange(0, len(cont)):
if cont[i] in cont[:i]:
return cont[i]
return None
Bueno, pero posiblemente sería mejor como generador – fmark
@fmark: si necesitaba más de un duplicado, entonces sí, pero su pregunta me lleva a creer que solo quiere el primer duplicado. – Zeke
no tan bonito ... solo funciona con contenedores ordenados, y quién sabe qué cantidad de cosas tendrá que pasar para cortar tanto la colección. – Claudiu
No es evidente cuál es el punto de encontrar un elemento arbitrario que es un duplicado o 1 o más de otros elementos de la colección ... qué quieres eliminarlo? fusionar sus atributos con los de sus gemelos/trillizos/.../N-tuplets? En cualquier caso, es una operación O (N), que si se repite hasta que no se detectan más duplicados es una operación O (N ** 2).
Sin embargo, puede obtener una gran cantidad en el almacén de algoritmos: ordenar la colección - O (N * log (N)) y luego usar itertools.groupby para agrupar los duplicados y navegar por los racimos, ignorando los racimos de tamaño 1 y haciendo lo que quieras con los racimos de tamaño> 1 - todo eso es solo aproximadamente O (N).
Buen punto. En mi caso, fue solo para reportar un duplicado (ya que se supone que genera una excepción). Es difícil pensar cuando uno podría querer hacer esto de otra manera. – max
from collections import Counter
cont = [1, 2, 3]
c = Counter(cont)
x = someItem
if c[x] == 0:
print("Not in cont")
elif c[x] == 1:
print("Unique")
else:
print("Duplicate")
'Counter' solo se implementa desde 2.7 en adelante si recuerdo correctamente, con 2.5 o 2.6 puede usar' defaultdict (int) 'dentro de un bucle e incrementarlo manualmente, aunque obviamente es menos eficiente. –
Si el contenedor es una lista, sólo puede pasar el valor que está buscando a su método count() y comprueba el resultado:
>>> l = [1,1,2,3]
>>> l.count(1)
2
>>>
Un diccionario no puede tener claves duplicadas, ni puede un conjunto. Fuera de estos, necesitaría saber qué tipo de contenedor es. Supongo que el verdadero objetivo es siempre asegurarse de no haber olvidado una solución obvia al problema antes de ir a programar una solución personalizada. Caigo presa de este mismo a veces :)
Según http://wiki.python.org/moin/TimeComplexity la mayor parte de las operaciones de lista son terriblemente ineficientes (solo confirmó que x in myList no parece ser O(N) en python3).
El método dado por su creador original es eficiente porque es un tiempo O (N) y el espacio (este es el "mejor" puede, sin hacer suposiciones adicionales acerca de su lista, ya que las operaciones de lista como x in myList son O(N))
Existe una optimización importante que es posible, que consiste en crear iterativamente el conjunto. Esto regresaría rápidamente en ciertos tipos de listas, p. [0,1,1,2,3,4,5,...]. Sin embargo, está asumiendo implícitamente un poco sobre la distribución de sus listas (por ejemplo, ¿optimiza para este caso, u optimiza para duplicados al final, o ambos?). Lo bueno de esta optimización es que no afecta la velocidad asintótica. Así es como me gustaría codificarlo con elegancia:
def hasDuplicate(iter):
visited = set()
for item in iter:
if item in visited:
return True
visited.add(item)
return False
También podría devolver el primer duplicado, pero no se puede volver None; Tendría que plantear una excepción ya que el iterable podría contener None.
nota al margen: hay formas de mejorar la eficiencia del espacio para un golpe menor a la eficiencia del tiempo (por ejemplo, filtros de floración).
Otras sugerencias, similares a la respuesta de jonesy. Al menos en python3 (no se han probado en python 2.7), cuando c [-5000] = 0, esto se vuelve más rápido que la solución 3 y 4 de la respuesta original. De lo contrario, es solo un poco más rápido que la solución 1 y 2 ...
elif toTest == '7':
for i in c:
if c.count(i)>1:
return i
¡Su método ES eficiente! =) Es el tiempo y el espacio 'O (N)' (lo mejor que puedes hacer es que 'x in myList' es' O (N) ', mira http://wiki.python.org/moin/TimeComplexity). Hay formas de mejorar la eficiencia de espacio para un golpe menor a la eficiencia de tiempo (por ejemplo, filtros de floración). La otra forma en que puede mejorar significativamente es regresar instantáneamente en ciertos tipos de listas, p. [0,1,1,2,3,4,5, ...].Esto supone un poco sobre la distribución de sus listas (por ejemplo, ¿se optimiza para este caso, o se duplica al final, o ambas cosas?), Pero puede ser una optimización que vale la pena ya que no afecta la velocidad asintótica. – ninjagecko