python - the algorithms
En Python, ¿cuál es el algoritmo más rápido para eliminar duplicados de una lista para que todos los elementos sean únicos*mientras se preserva el orden*? (27)
Esta pregunta ya tiene una respuesta aquí:
Por ejemplo:
>>> x = [1, 1, 2, ''a'', ''a'', 3]
>>> unique(x)
[1, 2, ''a'', 3]
Supongamos que los elementos de la lista son hashable.
Aclaración: el resultado debe mantener el primer duplicado en la lista. Por ejemplo, [1, 2, 3, 2, 3, 1] se convierte en [1, 2, 3].
¿Los duplicados necesariamente deben estar en la lista en primer lugar? No hay sobrecarga en cuanto a mirar los elementos hacia arriba, pero hay un poco más de sobrecarga al agregar elementos (aunque la sobrecarga debe ser O (1)).
>>> x = []
>>> y = set()
>>> def add_to_x(val):
... if val not in y:
... x.append(val)
... y.add(val)
... print x
... print y
...
>>> add_to_x(1)
[1]
set([1])
>>> add_to_x(1)
[1]
set([1])
>>> add_to_x(1)
[1]
set([1])
>>>
Aquí está la solución más rápida hasta el momento (para la siguiente entrada):
def del_dups(seq):
seen = {}
pos = 0
for item in seq:
if item not in seen:
seen[item] = True
seq[pos] = item
pos += 1
del seq[pos:]
lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18,
13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1,
5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9,
9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]
del_dups(lst)
print(lst)
# -> [8, 9, 7, 15, 2, 20, 13, 24, 6, 11, 12, 4, 10, 18, 23, 3, 5, 22, 19, 14,
# 21, 1, 0, 16, 17]
La búsqueda del diccionario es ligeramente más rápida que la del conjunto en Python 3.
Aquí hay algunas soluciones excelentes y eficientes. Sin embargo, para cualquiera que no esté preocupado con la solución O(n) más eficiente, O(n) solución simple O(n^2*log(n)) :
def unique(xs):
return sorted(set(xs), key=lambda x: xs.index(x))
o la solución O(n*log(n)) dos líneas más eficiente:
def unique(xs):
positions = dict((e,pos) for pos,e in reversed(list(enumerate(xs))))
return sorted(set(xs), key=lambda x: positions[x])
Aquí hay dos recetas de la documentación de itertools :
def unique_everseen(iterable, key=None):
"List unique elements, preserving order. Remember all elements ever seen."
# unique_everseen(''AAAABBBCCDAABBB'') --> A B C D
# unique_everseen(''ABBCcAD'', str.lower) --> A B C D
seen = set()
seen_add = seen.add
if key is None:
for element in ifilterfalse(seen.__contains__, iterable):
seen_add(element)
yield element
else:
for element in iterable:
k = key(element)
if k not in seen:
seen_add(k)
yield element
def unique_justseen(iterable, key=None):
"List unique elements, preserving order. Remember only the element just seen."
# unique_justseen(''AAAABBBCCDAABBB'') --> A B C D A B
# unique_justseen(''ABBCcAD'', str.lower) --> A B C A D
return imap(next, imap(itemgetter(1), groupby(iterable, key)))
Eliminar duplicados y conservar el orden:
Este es un 2-liner rápido que aprovecha la funcionalidad incorporada de las listas de comprensión y dictados.
x = [1, 1, 2, ''a'', ''a'', 3]
tmpUniq = {} # temp variable used below
results = [tmpUniq.setdefault(i,i) for i in x if i not in tmpUniq]
print results
[1, 2, ''a'', 3]
La función dict.setdefaults () devuelve el valor así como también lo agrega al dict temporal directamente en la lista de comprensión. El uso de las funciones incorporadas y los valores hash del dict trabajará para maximizar la eficiencia del proceso.
En realidad, puedes hacer algo realmente genial en Python para resolver esto. Puede crear una lista de comprensión que se haría referencia a sí misma a medida que se construye. Como sigue:
# remove duplicates...
def unique(my_list):
return [x for x in my_list if x not in locals()[''_[1]''].__self__]
Editar: eliminé el "sí mismo" y funciona en Mac OS X, Python 2.5.1.
El _ [1] es la referencia "secreta" de Python a la nueva lista. Lo anterior, por supuesto, es un poco desordenado, pero podría adaptarlo a sus necesidades según sea necesario. Por ejemplo, puede escribir una función que devuelva una referencia a la comprensión; se vería más como:
return [x for x in my_list if x not in this_list()]
Esta puede ser la forma más simple:
list(OrderedDict.fromkeys(iterable))
A partir de Python 3.5, OrderedDict ahora se implementa en C, por lo que ahora es el más corto, más limpio y más rápido.
Este es el más rápido, comparando todas las cosas de esta here y las otras respuestas dadas aquí, refiriéndose a este benchmark . Es otro 25% más rápido que la función más rápida de la discusión, f8 . Gracias a David Kirby por la idea.
def uniquify(seq):
seen = set()
seen_add = seen.add
return [x for x in seq if x not in seen and not seen_add(x)]
Alguna comparación de tiempo:
$ python uniqifiers_benchmark.py
* f8_original 3.76
* uniquify 3.0
* terhorst 5.44
* terhorst_localref 4.08
* del_dups 4.76
Este es el método más rápido en el lugar que he encontrado (suponiendo una gran proporción de duplicados):
def unique(l):
s = set(); n = 0
for x in l:
if x not in s: s.add(x); l[n] = x; n += 1
del l[n:]
Esto es un 10% más rápido que la implementación de Allen, en la que se basa (cronometrado con timeit.repeat, JIT compilado por psyco). Mantiene la primera instancia de cualquier duplicado.
repton-infinity: Me interesaría si pudieras confirmar mis tiempos.
Lo que va a ser más rápido depende de qué porcentaje de su lista esté duplicado. Si se trata de casi todos los duplicados, con pocos elementos únicos, la creación de una nueva lista probablemente sea más rápida. Si se trata principalmente de elementos únicos, eliminarlos de la lista original (o una copia) será más rápido.
Aquí hay uno para modificar la lista en su lugar:
def unique(items):
seen = set()
for i in xrange(len(items)-1, -1, -1):
it = items[i]
if it in seen:
del items[i]
else:
seen.add(it)
La iteración hacia atrás sobre los índices asegura que la eliminación de elementos no afecta la iteración.
No he hecho ninguna prueba, pero un posible algoritmo podría ser crear una segunda lista e iterar a través de la primera lista. Si un artículo no está en la segunda lista, agréguelo a la segunda lista.
x = [1, 1, 2, ''a'', ''a'', 3]
y = []
for each in x:
if each not in y:
y.append(each)
No sé si este es rápido o no, pero al menos es simple.
Simplemente, conviértalo primero en un conjunto y luego nuevamente en una lista
def unique(container):
return list(set(container))
No tengo experiencia con Python, pero un algoritmo sería ordenar la lista, luego eliminar duplicados (comparando con elementos anteriores en la lista) y finalmente encontrar la posición en la nueva lista comparando con la lista anterior.
Respuesta más larga: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560
O (n) si dict es hash, O (nlogn) si dict es arbol, y simple, fijo. Gracias a Matthew por la sugerencia. Lo siento, no sé los tipos subyacentes.
def unique(x):
output = []
y = {}
for item in x:
y[item] = ""
for item in x:
if item in y:
output.append(item)
return output
Obligatoria basada en el generador de variación:
def unique(seq):
seen = set()
for x in seq:
if x not in seen:
seen.add(x)
yield x
Si sacas la lista vacía de la llamada a set () en la respuesta de Terhost, obtienes un pequeño impulso de velocidad.
Cambio: found = set ([])
to: found = set ()
Sin embargo, no necesita el conjunto en absoluto.
def unique(items):
keep = []
for item in items:
if item not in keep:
keep.append(item)
return keep
Usando timeit obtuve estos resultados:
con set ([]) - 4.97210427363
con set () - 4.65712377445
sin juego - 3.44865284975
Tomado de here
def f5(seq, idfun=None):
# order preserving
if idfun is None:
def idfun(x): return x
seen = {}
result = []
for item in seq:
marker = idfun(item)
# in old Python versions:
# if seen.has_key(marker)
# but in new ones:
if marker in seen: continue
seen[marker] = 1
result.append(item)
return result
Un pase.
a = [1,1,''a'',''b'',''c'',''c'']
new_list = []
prev = None
while 1:
try:
i = a.pop(0)
if i != prev:
new_list.append(i)
prev = i
except IndexError:
break
Un trazador de líneas in situ para esto:
>>> x = [1, 1, 2, ''a'', ''a'', 3]
>>> [ item for pos,item in enumerate(x) if x.index(item)==pos ]
[1, 2, ''a'', 3]
Un trazador de líneas:
new_list = reduce(lambda x,y: x+[y][:1-int(y in x)], my_list, [])
Utilizando:
lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]
Y usando el módulo timeit:
$ python -m timeit -s ''import uniquetest'' ''uniquetest.etchasketch(uniquetest.lst)''
Y así sucesivamente para las otras funciones (que nombré después de sus carteles), tengo los siguientes resultados (en mi primera generación Intel MacBook Pro):
Allen: 14.6 µs per loop [1]
Terhorst: 26.6 µs per loop
Tarle: 44.7 µs per loop
ctcherry: 44.8 µs per loop
Etchasketch 1 (short): 64.6 µs per loop
Schinckel: 65.0 µs per loop
Etchasketch 2: 71.6 µs per loop
Little: 89.4 µs per loop
Tyler: 179.0 µs per loop
[1] Tenga en cuenta que Allen modifica la lista en su lugar: creo que esto ha sesgado el tiempo, ya que el módulo timeit ejecuta el código 100000 veces y 99999 de ellas están con la lista de dupe-less.
Resumen : la implementación directa con conjuntos gana por confusos conceptos de una sola línea :-)
a = [1,2,3,4,5,7,7,8,8,9,9,3,45]
def único (l):
ids={}
for item in l:
if not ids.has_key(item):
ids[item]=item
return ids.keys()
imprimir una
imprimir único (a)
----------------------------
Insertar elementos tomará theta (n) recuperando si el elemento está saliendo o no tomará tiempo constante probando todos los elementos también tomará theta (n) para que podamos ver que esta solución tomará theta (n) Tenga en cuenta ese diccionario en python implementado por tabla hash
has_key en python es O (1). La inserción y recuperación de un hash también es O (1). Pasa por n elementos dos veces, entonces O (n).
def unique(list):
s = {}
output = []
for x in list:
count = 1
if(s.has_key(x)):
count = s[x] + 1
s[x] = count
for x in list:
count = s[x]
if(count > 0):
s[x] = 0
output.append(x)
return output
>>> def unique(list):
... y = []
... for x in list:
... if x not in y:
... y.append(x)
... return y
>>> x=[1,1,2,''a'',''a'',3]
>>> y = [ _x for _x in x if not _x in locals()[''_[1]''] ]
>>> y
[1, 2, ''a'', 3]
"locals () [''_ [1]'']" es el "nombre secreto" de la lista que se está creando.
def unique(items):
found = set([])
keep = []
for item in items:
if item not in found:
found.add(item)
keep.append(item)
return keep
print unique([1, 1, 2, ''a'', ''a'', 3])
x = [] # Your list of items that includes Duplicates
# Assuming that your list contains items of only immutable data types
dict_x = {}
dict_x = {item : item for i, item in enumerate(x) if item not in dict_x.keys()}
# Average t.c. = O(n)* O(1) ; furthermore the dict comphrehension and generator like behaviour of enumerate adds a certain efficiency and pythonic feel to it.
x = dict_x.keys() # if you want your output in list format