recorrer - listas por comprensión python

Acceso a los elementos del diccionario por posición en Python 3.6+ de manera eficiente

Question

Entiendo que los diccionarios se insertan en Python 3.6+ , como detalle de implementación en 3.6 y oficial en 3.7+.

Dado que están ordenados, parece extraño que no existan métodos para recuperar el ítem de un diccionario por orden de inserción. Las únicas soluciones disponibles parecen tener complejidad O ( n ), ya sea:

1. Convierta a una lista a través de un proceso O ( n ) y luego use list.__getitem__ .
2. enumerate elementos del diccionario en un bucle y devuelva el valor cuando se alcance el índice deseado. De nuevo, con O ( n ) la complejidad del tiempo.

Dado que obtener un elemento de una list tiene una complejidad O (1), ¿hay alguna forma de lograr la misma complejidad con los diccionarios? Ya sea con dict regular o collections.OrderedDict . dict funcionaría.

Si no es posible, ¿existe alguna razón estructural que impida tal método o es solo una característica que aún no se ha considerado / implementado?

Answer 1

Para un OrderedDict es inherentemente O(n) porque el orden se registra en una lista enlazada .

Para el dictado incorporado, hay un vector (una matriz contigua) en lugar de una lista enlazada, pero casi lo mismo al final: el vector contiene algunos tipos de "dummies", valores internos especiales que significan que "ninguna tecla ha sido almacenado aquí todavía "o" una clave solía estar almacenada aquí pero ya no ". Eso hace que, por ejemplo, eliminar una clave sea extremadamente barato (solo sobrescriba la clave con un valor ficticio).

Pero sin agregar estructuras de datos auxiliares además de eso, no hay forma de saltear los maniquíes sin marchar sobre ellos uno a la vez. Debido a que Python utiliza una forma de direccionamiento abierto para la resolución de colisiones y mantiene el factor de carga en 2/3, al menos un tercio de las entradas del vector son dummies. the_vector[i] puede acceder a the_vector[i] en tiempo O(1) , pero en realidad no tiene una relación predecible con la entrada i''th no ficticia.

Answer 2

Según la respuesta de @TimPeters , hay razones estructurales por las que no puede acceder a los elementos del diccionario por posición en O (1) tiempo.

Vale la pena considerar las alternativas si está buscando la búsqueda O (1) por clave o posición. Existen bibliotecas de terceros, como NumPy / Pandas, que ofrecen dicha funcionalidad, especialmente para matrices numéricas en las que no se requieren punteros.

Con Pandas, puede crear una serie "tipo diccionario" con etiquetas únicas que ofrezcan O (1) búsqueda por "etiqueta" o posición. Lo que sacrifica es el rendimiento al eliminar una etiqueta, lo que incurre en el costo O ( n ), muy parecido a la list .

import pandas as pd

s = pd.Series(list(range(n)))

# O(n) item deletion
del s[i]
s.drop(i)

# O(1) lookup by label
s.loc[i]
s.at[i]
s.get(i)
s[i]

# O(1) lookup by position
s.iloc[i]
s.iat[i]

pd.Series es de ninguna manera un reemplazo dict para dict . Por ejemplo, las claves duplicadas no se evitan y causarán problemas si la serie se utiliza principalmente como una asignación. Sin embargo, cuando los datos se almacenan en un bloque de memoria contiguo, como en el ejemplo anterior, puede ver mejoras significativas en el rendimiento.

Ver también:

1. ¿Cuáles son las ventajas de NumPy sobre las listas regulares de Python? .
2. ¿Cuál es el impacto en el rendimiento de los índices no únicos en pandas?
3. ¿La búsqueda de Pandas DataFrame es tiempo lineal o tiempo constante?