tuplas - convertir tupla a diccionario python
¿Por qué es arbitrario el orden en los diccionarios y conjuntos? (5)
"Arbitrario" no es lo mismo que "no determinado".
Lo que están diciendo es que no hay propiedades útiles del orden de iteración del diccionario que estén "en la interfaz pública". Casi seguramente hay muchas propiedades del orden de iteración que están totalmente determinadas por el código que actualmente implementa la iteración del diccionario, pero los autores no les están prometiendo como algo que puede usar. Esto les da más libertad para cambiar estas propiedades entre las versiones de Python (o incluso en diferentes condiciones de operación, o completamente al azar en tiempo de ejecución) sin preocuparse de que su programa se rompa.
Por lo tanto, si escribes un programa que depende de cualquier propiedad en todo orden de diccionario, entonces estás "rompiendo el contrato" de usar el tipo de diccionario, y los desarrolladores de Python no están prometiendo que esto siempre funcionará, incluso si parece funcionar por ahora cuando lo pruebes. Es básicamente el equivalente de confiar en "comportamiento indefinido" en C.
No entiendo cómo el bucle sobre un diccionario o conjunto en python se realiza por orden ''arbitraria''.
Quiero decir, es un lenguaje de programación, así que todo en el lenguaje debe estar 100% determinado, ¿correcto? Python debe tener algún tipo de algoritmo que decida qué parte del diccionario o conjunto se elige, primero, segundo y así sucesivamente.
¿Qué me estoy perdiendo?
Las otras respuestas a esta pregunta son excelentes y bien escritas. El OP pregunta "cómo" que interpreto como "cómo se salen con" o "por qué".
La documentación de Python dice que los diccionarios no se ordenan porque el diccionario Python implementa la matriz asociativa de tipo de datos abstractos . Como ellos dicen
el orden en que se devuelven los enlaces puede ser arbitrario
En otras palabras, un estudiante de ciencias de la computación no puede asumir que una matriz asociativa está ordenada. Lo mismo es cierto para los conjuntos en matemáticas
el orden en que se enumeran los elementos de un conjunto es irrelevante
un conjunto es un tipo de datos abstracto que puede almacenar ciertos valores, sin ningún orden en particular
La implementación de un diccionario utilizando una tabla hash es un detalle de implementación que es interesante porque tiene las mismas propiedades que los arrays asociativos en cuanto al orden.
Python utiliza la tabla hash para almacenar los diccionarios, por lo que no hay orden en los diccionarios u otros objetos iterables que utilizan la tabla hash.
Pero con respecto a los índices de elementos en un objeto hash, python calcula los índices basados en el siguiente código dentro de hashtable.c :
key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);
Por lo tanto, como el valor hash de enteros es el entero mismo * el índice se basa en el número ( ht->num_buckets - 1 es una constante) de modo que el índice calculado por Bitwise y entre (ht->num_buckets - 1) number mismo * (espera para -1 que es hash es -2), y para otros objetos con su valor hash.
considere el siguiente ejemplo con set que usan hash-table:
>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])
Para el número 33 tenemos:
33 & (ht->num_buckets - 1) = 1
Que en realidad es:
''0b100001'' & ''0b111''= ''0b1'' # 1 the index of 33
Nota en este caso (ht->num_buckets - 1) es 8-1=7 o 0b111 .
Y para 1919 :
''0b11101111111'' & ''0b111'' = ''0b111'' # 7 the index of 1919
Y para 333 :
''0b101001101'' & ''0b111'' = ''0b101'' # 5 the index of 333
Para obtener más detalles sobre la función de hash de Python es bueno leer las siguientes citas de código fuente de python :
Principales sutilezas por delante: La mayoría de los esquemas hash dependen de tener una función "hash" buena, en el sentido de simular aleatoriedad. Python no: sus funciones hash más importantes (para cadenas e ints) son muy regulares en casos comunes:
>>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462]Esto no es necesariamente malo! Por el contrario, en una tabla de tamaño 2 ** i, tomando los bits i de orden inferior como el índice de tabla inicial es extremadamente rápido, y no hay colisiones en absoluto para los dictados indexados por un intervalo contiguo de ints. Lo mismo es aproximadamente cierto cuando las claves son cadenas "consecutivas". Así que esto da mejor que el comportamiento al azar en los casos comunes, y eso es muy deseable.
OTOH, cuando se producen colisiones, la tendencia a rellenar trozos contiguos de la tabla hash hace que una buena estrategia de resolución de colisiones sea crucial. Tomar sólo los últimos i bits del código hash también es vulnerable: por ejemplo, considere la lista
[i << 16 for i in range(20000)]como un conjunto de claves. Dado que los ints son sus propios códigos de hash, y esto encaja en un dict de tamaño 2 ** 15, los últimos 15 bits de cada código de hash son todos 0: todos ellos se asignan al mismo índice de tabla.Pero el abastecimiento a los casos inusuales no debe retardar los habituales, así que apenas tomamos los últimos bits i de todos modos. Depende de la resolución de la colisión para hacer el resto. Si por lo general encontramos la clave que estamos buscando en el primer intento (y, resulta que normalmente lo hacemos - el factor de carga de la tabla se mantiene en 2/3, por lo que las probabilidades están sólidamente a nuestro favor), entonces tiene el mejor sentido de mantener la suciedad de computación de índice inicial barato.
* La función hash para clase int :
class int:
def __hash__(self):
value = self
if value == -1:
value = -2
return value
El orden no es arbitrario, sino que depende del historial de inserción y eliminación del diccionario o conjunto, así como de la implementación específica de Python. Para el resto de esta respuesta, para ''diccionario'', también puede leer ''set''; se implementan como diccionarios con sólo teclas y sin valores.
Las claves son hash y los valores hash se asignan a las ranuras de una tabla dinámica (puede crecer o reducirse según las necesidades). Y ese proceso de mapeo puede conducir a colisiones, lo que significa que una clave tendrá que ser ranurado en una próxima ranura basada en lo que ya está allí.
Listando los bucles de contenido sobre las ranuras, por lo que las claves aparecen en el orden en que residen actualmente en la tabla.
Tome las teclas ''foo'' y ''bar'' , por ejemplo, y permite suponer que el tamaño de la tabla es de 8 ranuras. En Python 2.7, hash(''foo'') es -4177197833195190597 , hash(''bar'') es 327024216814240868 . Modulo 8, que significa que estas dos claves están ranuradas en las ranuras 3 y 4 entonces:
>>> hash(''foo'')
-4177197833195190597
>>> hash(''foo'') % 8
3
>>> hash(''bar'')
327024216814240868
>>> hash(''bar'') % 8
4
Esto informa su orden de listado:
>>> {''bar'': None, ''foo'': None}
{''foo'': None, ''bar'': None}
Todas las ranuras excepto 3 y 4 están vacías, haciendo un bucle sobre la tabla primero enumera la ranura 3, luego la ranura 4, así que ''foo'' aparece antes de ''bar'' .
bar y baz , sin embargo, tienen valores de hash que son exactamente 8 aparte y por lo tanto mapa a la misma ranura exacta, 4 :
>>> hash(''bar'')
327024216814240868
>>> hash(''baz'')
327024216814240876
>>> hash(''bar'') % 8
4
>>> hash(''baz'') % 8
4
Su orden ahora depende de qué llave fue ranurada primero; la segunda tecla tendrá que ser movida a una ranura siguiente:
>>> {''baz'': None, ''bar'': None}
{''bar'': None, ''baz'': None}
>>> {''bar'': None, ''baz'': None}
{''baz'': None, ''bar'': None}
El orden de la tabla difiere aquí, porque una o la otra clave fue ranurada primero.
El nombre técnico de la estructura subyacente utilizada por CPython (la implementación de Python más comúnmente utilizada) es una tabla de hash , que utiliza el direccionamiento abierto. Si tiene curiosidad, y comprenda C lo suficientemente bien, eche un vistazo a la implementación de C para todos los detalles (bien documentados). También puedes ver esta presentación de Pycon 2010 de Brandon Rhodes acerca de cómo funciona CPython dict , o recoger una copia de Beautiful Code , que incluye un capítulo sobre la aplicación escrita por Andrew Kuchling.
Tenga en cuenta que a partir de Python 3.3, también se utiliza una semilla de hash aleatoria, lo que hace que las colisiones de hash sean impredecibles para evitar ciertos tipos de denegación de servicio (donde un atacante hace que un servidor Python no responda causando colisiones de hash de masa). Esto significa que el orden de un diccionario dado también depende de la semilla hash aleatoria para la invocación actual de Python.
Otras implementaciones son libres de usar una estructura diferente para los diccionarios, siempre y cuando satisfagan la interfaz Python documentada para ellos, pero creo que todas las implementaciones hasta el momento utilizan una variación de la tabla hash.
CPython 3.6 introduce una nueva implementación de dict que mantiene el orden de inserción, y es más rápido y más eficiente de la memoria para arrancar. En lugar de mantener una tabla dispersa grande en la que cada fila hace referencia al valor hash almacenado ya los objetos key y value, la nueva implementación agrega una matriz hash más pequeña que sólo hace referencia a índices en una tabla densa (una que sólo contiene tantas filas como hay reales pares clave-valor), y es la tabla densa que pasa a la lista de los elementos contenidos en el orden. Vea la propuesta a Python-Dev para más detalles . Tenga en cuenta que esto se considera un detalle de implementación , Python-the-language no especifica que otras implementaciones tienen que retener el orden.
Python 2.7 y OrderedDict posteriores también proporcionan una clase OrderedDict , una subclase de dict que añade una estructura de datos adicional para registrar el orden de las claves. Al precio de una cierta velocidad y memoria adicional, esta clase recuerda en qué orden usted insertó las llaves; las llaves, los valores o los artículos de la lista entonces lo harán en ese orden. Utiliza una lista doblemente vinculada almacenada en un diccionario adicional para mantener la orden actualizada de manera eficiente. Ver el post de Raymond Hettinger esbozando la idea . Tenga en cuenta que el tipo de set sigue sin ordenar.
Si desea un conjunto ordenado, puede instalar el paquete oset ; funciona en Python 2.5 y superior.
Esto es más una respuesta a Python 3.41 Un conjunto antes de que se cerró como un duplicado.
Los otros tienen razón: no confíe en la orden. Ni siquiera pretender que hay uno.
Dicho esto, hay una cosa en la que puede confiar:
list(myset) == list(myset)
Es decir, el orden es estable .
Comprender por qué hay un orden percibido requiere entender algunas cosas:
Que Python utiliza conjuntos de hash ,
Cómo el conjunto de hash de CPython se almacena en la memoria y
Cómo los números se arrastran
Desde la parte superior:
Un conjunto de hash es un método de almacenar datos aleatorios con tiempos de búsqueda realmente rápidos.
Tiene una matriz de apoyo:
# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6
Ignoraremos el objeto ficticio especial, el cual existe sólo para hacer más fácil el quitar, porque no nos quitaremos de estos conjuntos.
Con el fin de tener una búsqueda muy rápida, usted hace algo de magia para calcular un hash de un objeto. La única regla es que dos objetos que son iguales tienen el mismo hash. (Pero si dos objetos tienen el mismo hash pueden ser desiguales.)
A continuación, haga en índice tomando el módulo por la longitud del arreglo:
hash(4) % len(storage) = index 2
Esto hace que sea muy rápido acceder a los elementos.
Los hash son sólo la mayor parte de la historia, ya que hash(n) % len(storage) y hash(m) % len(storage) pueden dar como resultado el mismo número. En ese caso, varias estrategias diferentes pueden tratar de resolver el conflicto. CPython utiliza "sondaje lineal" 9 veces antes de hacer cosas complicadas, por lo que se verá a la izquierda de la ranura de hasta 9 lugares antes de buscar en otra parte.
Los conjuntos de hash de CPython se almacenan de la siguiente manera:
Un conjunto hash no puede ser más de 2/3 completo . Si hay 20 elementos y la matriz de respaldo tiene 30 elementos, el almacén de respaldo se redimensionará para ser más grande. Esto es porque usted consigue colisiones más a menudo con los almacenes pequeños del respaldo, y las colisiones paran todo abajo.
El almacén de respaldo se redimensiona en potencias de 4, comenzando en 8, excepto para conjuntos grandes (50k elementos) que redimensionan en potencias de dos: (8, 32, 128, ...).
Por lo tanto, cuando se crea una matriz el almacén de respaldo es la longitud 8. Cuando es 5 completo y agrega un elemento, contendrá brevemente 6 elementos. 6 > ²⁄₃·8 lo que desencadena un redimensionamiento, y el almacén de respaldo se cuadruplica hasta el tamaño 32.
Finalmente, hash(n) sólo devuelve n para números (excepto -1 que es especial).
Entonces, veamos la primera:
v_set = {88,11,1,33,21,3,7,55,37,8}
len(v_set) es 10, por lo que el almacén de respaldo es al menos 15 (+1) después de haber agregado todos los elementos . La potencia relevante de 2 es 32. Así que la tienda de respaldo es:
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
Tenemos
hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1) % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3) % 32 = 3
hash(7) % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8) % 32 = 8
por lo que se insertan como:
__ 1 __ 3 __ 37 __ 7 8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
33 ← Can''t also be where 1 is;
either 1 or 33 has to move
Así que esperamos una orden como
{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}
con el 1 o el 33 que no está al principio en otro lugar. Esto utilizará sondaje lineal, por lo que tendrá:
↓
__ 1 33 3 __ 37 __ 7 8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
o
↓
__ 33 1 3 __ 37 __ 7 8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
Podría esperarse que el 33 sea el que está desplazado porque el 1 ya estaba allí, pero debido al cambio de tamaño que sucede mientras se está construyendo el conjunto, este no es realmente el caso. Cada vez que el conjunto se reconstruye, los elementos ya agregados son efectivamente reordenados.
Ahora puedes ver por qué
{7,5,11,1,4,13,55,12,2,3,6,20,9,10}
podría estar en orden. Hay 14 elementos, por lo que la tienda de apoyo es al menos 21 + 1, lo que significa 32:
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
1 a 13 hash en las primeras 13 ranuras. 20 entra en la ranura 20.
__ 1 2 3 4 5 6 7 8 9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __
55 va en el hash(55) % 32 ranura hash(55) % 32 que es 23:
__ 1 2 3 4 5 6 7 8 9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __
Si elegimos 50 en su lugar, esperaríamos
__ 1 2 3 4 5 6 7 8 9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __
Y he aquí y he aquí:
{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}
pop se implementa simplemente por la apariencia de las cosas: atraviesa la lista y aparece la primera.