funciones - lista de diccionarios python

¿Se ordenará naturalmente un dict de Python con enteros como claves?

Question

Si creo un dictado de Python que usa enteros como claves, ¿puedo asumir de forma segura que la iteración del dictado recuperará los elementos en orden de acuerdo con el valor de la clave?

es decir, será

my_dict = {}
for x in range(0,100):
my_dict[x] = str(x)
for item in my_dict.items():
print item

¿Siempre resulta en imprimir la lista en orden de valor clave?

Answer 1

En resumen, no. Estoy seguro de que notó que los diccionarios utilizan los hashes de las claves como índices en una matriz, y como los hash de los ints en sus propios valores, dedujo que los valores insertados terminarán en orden por clave si sus claves son enteros. Si bien las primeras 2 partes de esa declaración son verdaderas, la inferencia no lo es, incluso como un efecto secundario no documentado. Las claves dict se derivan de los hashes de las claves, pero no son los hashes completos. Esto significa que, incluso con las teclas de enteros, aún puede obtener inserciones fuera de orden, ya que 2 valores podrían colisionar en la misma ubicación (o incluso tener valores derivados de hash "fuera de orden") y, por lo tanto, terminar insertando las teclas fuera de orden en el dictado

Básicamente, piense en él como el índice en la matriz de almacenamiento interno del dict que es un número de bits de orden inferior del hash de la clave. El hecho de que un número sea mayor que otro no significa que un valor creado a partir de sus bits truncados de orden inferior sea mayor o incluso diferente.

Answer 2

Los diccionarios de Python no están ordenados de ninguna manera significativa; son tablas hash.

Python viene con colecciones.OrderedDict, pero esto se ordena por orden de inserción, no por orden de clave.

Aquí hay dos módulos tipo diccionario que ordenan por teclas:

https://pypi.python.org/pypi/treap/

https://pypi.python.org/pypi/red-black-tree-mod/

Algunos dicen que las golosinas son más rápidas en promedio que los árboles rojo-negro, pero los árboles rojo-negro tienen una desviación estándar más baja en los tiempos de operación. Otros cuestionan esto, aunque en mis pruebas lo primero resultó ser cierto.

Tanto las golosinas como los árboles rojo-negros hacen casi todo en O (logn), pero mantienen sus llaves en orden constantemente. Los diccionarios de Python son O (1) para la mayoría de las operaciones. Sin embargo, poner todas las teclas en orden es O (n) para las golosinas y los árboles rojo-negro, mientras que es O (nlogn) para los diccionarios.

¿Cuándo debes usar cuál?

1. Si está clasificando en un bucle, probablemente esté mejor con un treap o un árbol rojo-negro.
2. Si está clasificando una vez al final de su programa o algo, probablemente esté mejor con list_ = list (dict_); list_.sort ()
3. Si está conservando el orden de sus entradas, como de un archivo de configuración o algo así, probablemente esté mejor con OrderedDict.

HTH

Answer 3

No lo creo. Tiene que hacer uso de collections.OrderedDict para garantizar el pedido. Sin embargo, esto ordenará las entradas en el orden en que se agregaron.

Answer 4

No, los diccionarios de Python no tienen orden inherente, independientemente de los valores clave. Si necesita hacer pedidos, atenerse a matrices o listas, o mejor aún, eche un vistazo a los pandas , que permitirán una habilidad similar a los diccionarios para llamar por valor clave, así como muchas otras funciones poderosas ( http://pandas.pydata.org/pandas-docs/stable/10min.html ).

Answer 5

No, no puedes. Ordena siempre si quieres iterar de una manera ordenada.