español - ¿Cuál es la forma más rápida de agregar datos a una lista sin duplicación en python(2.5)?

qgis girona

Question

Tengo alrededor de medio millón de elementos que deben colocarse en una lista, no puedo tener duplicaciones, y si un elemento ya está allí, necesito obtener su índice. Hasta ahora tengo

if Item in List:
    ItemNumber=List.index(Item)
else:
    List.append(Item)
    ItemNumber=List.index(Item)

El problema es que a medida que la lista crece, se vuelve cada vez más lenta hasta que, en algún momento, no vale la pena hacerlo. Estoy limitado a Python 2.5 porque es un sistema integrado.

Answer 1

¿Cuál es el rango de su medio millón de artículos? Es posible que pueda utilizar la memoria de manera muy ineficiente si puede hacer algunas declaraciones sobre el rango de estos elementos. Creo que un enfoque en esta línea sería el más rápido posible, pero podría no ser práctico para una aplicación incrustada a menos que pueda hacer algunas garantías muy estrictas.

¿Esta respuesta te ayuda a orientarte hacia el intercambio de tiempo / memoria al que me refiero? Puedo ayudar a aclarar más si lo desea.

Answer 2

Puede utilizar un set (en CPython desde la versión 2.4) para buscar de manera eficiente los valores duplicados. Si realmente también necesita un sistema indexado, puede usar un conjunto y una lista.

Al realizar búsquedas en un conjunto, se eliminará la sobrecarga de if Item in List , pero no la de List.index(Item)

Tenga en cuenta que ItemNumber=List.index(Item) será muy ineficiente después de List.append(Item) . Conoce la longitud de la lista, por lo que su índice se puede recuperar con ItemNumber = len(List)-1 .

Para eliminar completamente la sobrecarga de List.index (debido a que ese método buscará en la lista - muy ineficiente en conjuntos más grandes), puede usar un artículo de mapeo de dict de nuevo a su índice.

Podría volver a escribirlo de la siguiente manera:

# earlier in the program, NOT inside the loop
Dup = {}

# inside your loop to add items:
if Item in Dup:
    ItemNumber = Dup[Item]
else:
    List.append(Item)
    Dup[Item] = ItemNumber = len(List)-1

Answer 3

Puedes mejorar mucho el cheque:

check = set(List)

for Item in NewList:
    if Item in check: ItemNumber = List.index(Item)
    else:
        ItemNumber = len(List)
        List.append(Item)

O, mejor aún, si el orden no es importante, puedes hacer esto:

oldlist = set(List)
addlist = set(AddList)
newlist = list(oldlist | addlist)

Y si necesita recorrer los elementos que fueron duplicados:

for item in (oldlist & addlist):
    pass # do stuff

Answer 4

Si realmente necesita mantener los datos en una matriz, usaría un diccionario separado para realizar un seguimiento de los duplicados. Esto requiere el doble de memoria, pero no se ralentizará significativamente.

existing = dict()
if Item in existing:
    ItemNumber = existing[Item]
else:
    ItemNumber = existing[Item] = len(List)
    List.append(Item)

Sin embargo, si no necesita guardar el orden de los elementos, solo debe utilizar un set . Esto tomará casi tan poco espacio como una lista, pero será tan rápido como un diccionario.

Items = set()
# ...
Items.add(Item) # will do nothing if Item is already added

Ambos requieren que su objeto sea hashable . En Python, la mayoría de los tipos son hashable a menos que sean un contenedor cuyos contenidos puedan modificarse. Por ejemplo: las list no son hashables porque puedes modificar su contenido, pero las tuple son hashables porque no puedes.

Si intentaba almacenar valores que no son hashable, no hay una solución general rápida.