python - ejemplos - django
''orden'' de conjuntos de Python desordenados (5)
Deberías ver este video (aunque es específico de CPython 1 y sobre diccionarios, pero supongo que también se aplica a los conjuntos).
Básicamente, python evalúa los elementos y toma los últimos N bits (donde N se determina por el tamaño del conjunto) y utiliza esos bits como índices de matriz para colocar el objeto en la memoria. Los objetos son cedidos en el orden en que existen en la memoria. Por supuesto, la imagen se vuelve un poco más complicada cuando necesitas resolver colisiones entre hashes, pero esa es la esencia de esto.
También tenga en cuenta que el orden en que se imprimen está determinado por el orden en que los coloca (debido a colisiones). Por lo tanto, si reordena la lista que pasa al set_2 , es posible que obtenga un pedido diferente si hay colisiones de claves.
Por ejemplo:
list1 = [8,16,24]
set(list1) #set([8, 16, 24])
list2 = [24,16,8]
set(list2) #set([24, 16, 8])
Tenga en cuenta que el hecho de que la orden se conserve en estos conjuntos es "coincidencia" y tiene que ver con la resolución de colisión (de la que no sé nada). El punto es que los últimos 3 bits de hash(8) , hash(16) y hash(24) son los mismos. Debido a que son iguales, la resolución de colisión toma el control y coloca los elementos en ubicaciones de memoria de "respaldo" en lugar de la primera (mejor) opción y si 8 ocupa una ubicación o 16 se determina por cuál llegó primero a la fiesta y tomó el "mejor asiento".
Si repetimos el ejemplo con 1 , 2 y 3 , obtendrá un orden consistente independientemente del orden que tengan en la lista de entrada:
list1 = [1,2,3]
set(list1) # set([1, 2, 3])
list2 = [3,2,1]
set(list2) # set([1, 2, 3])
ya que los últimos 3 bits de hash(1) , hash(2) y hash(3) son únicos.
1 Nota La implementación descrita aquí se aplica a CPython dict y set . Creo que la descripción general es válida para todas las versiones modernas de CPython hasta 3.6. Sin embargo, comenzando con CPython3.6, hay un detalle de implementación adicional que realmente conserva el orden de inserción para la iteración de dict . Parece que el set todavía no tiene esta propiedad. La estructura de datos se describe en esta publicación de blog por los amigos de Pypy (que comenzaron a usar esto antes de la gente de CPython). La idea original (al menos para el ecosistema python) está archivada en la lista de correo de python-dev .
Pregunta de un novato (yo):
Entiendo que los conjuntos en Python están desordenados, pero tengo curiosidad sobre el ''orden'' en el que se muestran, ya que parece ser consistente. Parecen estar fuera de servicio de la misma manera todas las veces:
>>> set_1 = set([5, 2, 7, 2, 1, 88])
>>> set_2 = set([5, 2, 7, 2, 1, 88])
>>> set_1
set([88, 1, 2, 5, 7])
>>> set_2
set([88, 1, 2, 5, 7])
... y otro ejemplo:
>>> set_3 = set(''abracadabra'')
>>> set_4 = set(''abracadabra'')
>>> set_3
set([''a'', ''r'', ''b'', ''c'', ''d''])
>>>> set_4
set([''a'', ''r'', ''b'', ''c'', ''d''])
Solo tengo curiosidad de por qué sería esto. ¿Alguna ayuda?
La razón de tal comportamiento es que Python usa tablas hash para la implementación del diccionario: https://en.wikipedia.org/wiki/Hash_table#Open_addressing
La posición de la tecla se define por su dirección de memoria. Si conoce la memoria de reutilización de Python para algunos objetos:
>>> a = ''Hello world''
>>> id(a)
140058096568768
>>> a = ''Hello world''
>>> id(a)
140058096568480
Puedes ver que el objeto tiene una dirección diferente cada vez que es init.
Pero para enteros pequeños no es cambio:
>>> a = 1
>>> id(a)
40060856
>>> a = 1
>>> id(a)
40060856
Incluso si creamos un segundo objeto con un nombre diferente, sería el mismo:
>>> b = 1
>>> id(b)
40060856
Este enfoque permite ahorrar memoria que el intérprete de Python consume.
Los conjuntos de AFAIK Python se implementan usando una tabla hash . El orden en que aparecen los elementos depende de la función hash utilizada. Dentro de la misma ejecución del programa, la función hash probablemente no cambia, por lo tanto, obtienes el mismo orden.
Pero no hay garantías de que siempre use la misma función, y el orden cambiará entre ejecuciones, o dentro de la misma ejecución si inserta muchos elementos y la tabla hash tiene que cambiar el tamaño.
Los conjuntos se basan en una tabla hash. El hash de un valor debe ser coherente, por lo que el orden también lo será, a menos que haya dos elementos hash para el mismo código, en cuyo caso el orden de inserción cambiará el orden de salida.
Una cosa clave que se insinuó en la gran respuesta de mgilson , pero no se menciona explícitamente en ninguna de las respuestas existentes:
Pequeños enteros hash para ellos mismos:
>>> [hash(x) for x in (1, 2, 3, 88)]
[1, 2, 3, 88]
Strings hash a valores que son impredecibles. De hecho, a partir de 3.3 en adelante, de forma predeterminada, están construidos a partir de una semilla que se aleatoriza al inicio . Por lo tanto, obtendrás resultados diferentes para cada nueva sesión de intérprete de Python, pero:
>>> [hash(x) for x in ''abcz'']
[6014072853767888837,
8680706751544317651,
-7529624133683586553,
-1982255696180680242]
Por lo tanto, considere la implementación de tabla hash más simple posible: solo una matriz de N elementos, donde insertar un valor significa ponerlo en hash(value) % N (suponiendo que no haya colisiones). Y puede adivinar qué tan grande será N será un poco más grande que la cantidad de elementos que contiene. Al crear un conjunto a partir de una secuencia de 6 elementos, N podría ser fácilmente, digamos, 8.
¿Qué sucede cuando almacena esos 5 números con N = 8? Bueno, hash(1) % 8 , hash(2) % 8 , etc. son solo los números, pero hash(88) % 8 es 0. Entonces, la matriz de la tabla hash termina sosteniendo 88, 1, 2, NULL, NULL, 5, NULL, 7 . Por lo tanto, debería ser fácil descubrir por qué iterar en el conjunto podría darle 88, 1, 2, 5, 7 .
Por supuesto, Python no garantiza que obtendrá este pedido en todo momento. Un pequeño cambio en la forma en que adivina el valor correcto para N podría significar que 88 termina en algún lugar diferente (o termina colisionando con uno de los otros valores). Y, de hecho, al ejecutar CPython 3.7 en mi Mac, obtengo 1, 2, 5, 7, 88 .0
Mientras tanto, cuando construyes un hash a partir de una secuencia de tamaño 11 e insertas hashes aleatorizados, ¿qué ocurre? Incluso asumiendo la implementación más simple, y suponiendo que no hay colisiones, aún no tienes idea de qué orden obtendrás. Será coherente en una sola ejecución del intérprete de Python, pero diferente la próxima vez que lo inicie. (A menos que configure PYTHONHASHSEED en 0 , o en algún otro valor int.) Que es exactamente lo que ve.
Por supuesto, vale la pena mirar la forma en que los conjuntos se implementan realmente en lugar de adivinar. Pero lo que supondría basado en la suposición de que la implementación de la tabla hash más simple es (salvo las colisiones y la expansión de la tabla hash) exactamente lo que sucede.