Indexando una lista con un índice único

Tengo una lista que dice l = [10,10,20,15,10,20] . Quiero asignar a cada valor único un cierto “índice” para obtener [1,1,2,3,1,2] .

Este es mi código:

 a = list(set(l)) res = [a.index(x) for x in l] 

Lo que resulta ser muy lento.

l tiene 1M elementos, y 100K elementos únicos. También he intentado mapa con lambda y clasificación, que no ayudó. ¿Cuál es la forma ideal de hacer esto?

La lentitud de su código surge porque a.index(x) realiza una búsqueda lineal y usted realiza esa búsqueda lineal para cada uno de los elementos en l . Por lo tanto, para cada uno de los elementos 1M realiza (hasta) comparaciones de 100K.

La forma más rápida de transformar un valor en otro es buscarlo en un mapa. Deberá crear el mapa y completar la relación entre los valores originales y los valores que desea. Luego recupere el valor del mapa cuando encuentre otro del mismo valor en su lista.

Aquí hay un ejemplo que hace una sola pasada a través de l . Puede haber espacio para una mayor optimización para eliminar la necesidad de reasignar repetidamente la res al agregarla.

 res = [] conversion = {} i = 0 for x in l: if x not in conversion: value = conversion[x] = i i += 1 else: value = conversion[x] res.append(value) 

Puede hacer esto en tiempo O(N) usando un defaultdict y una lista de comprensión:

 >>> from itertools import count >>> from collections import defaultdict >>> lst = [10, 10, 20, 15, 10, 20] >>> d = defaultdict(count(1).next) >>> [d[k] for k in lst] [1, 1, 2, 3, 1, 2] 

En Python 3 use __next__ lugar de next .


Si te estás preguntando cómo funciona?

El default_factory (es decir, count(1).next en este caso) que se pasa al defaultdict solo se llama cuando Python encuentra una clave faltante, por lo que para 10 el valor será 1, luego para los próximos diez ya no es una clave faltante por lo tanto, se usa el 1 previamente calculado, ahora 20 es nuevamente una clave que falta y Python llamará a default_factory nuevamente para obtener su valor y así sucesivamente.

d al final se verá así:

 >>> d defaultdict(, {10: 1, 20: 2, 15: 3}) 

Bueno, supongo que depende de si desea que devuelva los índices en ese orden específico o no. Si quieres que el ejemplo regrese:

  [1,1,2,3,1,2] 

Luego puedes mirar las otras respuestas enviadas. Sin embargo, si solo te importa obtener un índice único para cada número único, tengo una solución rápida para ti.

  import numpy as np l = [10,10,20,15,10,20] a = np.array(l) x,y = np.unique(a,return_inverse = True) 

y para este ejemplo la salida de y es:

  y = [0,0,2,1,0,2] 

Probé esto para 1,000,000 entradas y fue hecho esencialmente inmediatamente.

Su solución es lenta porque su complejidad es O(nm) siendo m el número de elementos únicos en l : a.index() es O(m) y lo llama para cada elemento en l .

Para hacerlo O(n) , elimine el index() y almacene los índices en un diccionario:

 >>> idx, indexes = 1, {} >>> for x in l: ... if x not in indexes: ... indexes[x] = idx ... idx += 1 ... >>> [indexes[x] for x in l] [1, 1, 2, 3, 1, 2] 

Si l contiene solo números enteros en un rango conocido, también puede almacenar índices en una lista en lugar de un diccionario para búsquedas más rápidas.

Puede usar collections.OrderedDict() para conservar los artículos únicos en orden y, recorra la enumeración de estos artículos únicos ordenados para obtener un dict de los artículos y los índices (según su orden) luego pase este diccionario con la lista principal a operator.itemgetter() para obtener el índice correspondiente para cada elemento:

 >>> from collections import OrderedDict >>> from operator import itemgetter >>> itemgetter(*lst)({j:i for i,j in enumerate(OrderedDict.fromkeys(lst),1)}) (1, 1, 2, 3, 1, 2) 

Para completar, también puede hacerlo con entusiasmo:

 from itertools import count wordid = dict(zip(set(list_), count(1))) 

Esto usa un conjunto para obtener las palabras únicas en la list_ , empareja cada una de esas palabras únicas con el siguiente valor de count() (que cuenta hacia arriba) y construye un diccionario a partir de los resultados.

Respuesta original , escrita por nneonneo.