python - indexes - Indexar una lista con un índice único

remove index mongodb

Question

Tengo una lista que dice l = [10,10,20,15,10,20] . Quiero asignarle 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]

Que resulta ser muy lento.

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

Answer 1

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

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

entonces puedes mirar las otras respuestas enviadas. Sin embargo, si solo te importa obtener un índice único para cada número único, entonces 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 se hizo esencialmente de manera inmediata.

Answer 2

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

La forma más rápida de transformar un valor en otro es buscarlo en un mapa. Tendrá que crear el mapa y completar la relación entre los valores originales y los valores que desee. 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 margen para una mayor optimización para eliminar la necesidad de reasignar repetidamente res cuando se agrega a ella.

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)

Answer 3

Para completitud, también puede hacerlo con entusiasmo:

from itertools import count

wordid = dict(zip(set(list_), count(1)))

Utiliza un conjunto para obtener las palabras únicas en 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.

Answer 4

Puede usar collections.OrderedDict() para conservar los elementos únicos en orden y, pasar por encima de la enumeración de estos elementos únicos ordenados para obtener un dict de elementos y esos índices (según su orden) y luego pasar este diccionario con la lista principal de 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)

Answer 5

Puedes hacerlo en O(N) vez usando un valor 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 preguntas cómo funciona?

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

d al final se verá así:

>>> d
defaultdict(<method-wrapper ''next'' of itertools.count object at 0x1057c83b0>,
            {10: 1, 20: 2, 15: 3})

Answer 6

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) , deshacerse del index() y almacenar í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 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.