tuple structures print dictionaries create python data-structures dictionary

structures - ¿Cómo se implementan los diccionarios incorporados de Python?



python structures (3)

¿Cómo se implementan los diccionarios incorporados de Python?

Aquí está el curso corto:

  • Son tablas hash.
  • Un nuevo procedimiento / algoritmo, a partir de Python 3.6, los hace
    • ordenado por inserción de llave, y
    • ocupar menos espacio,
    • prácticamente sin costo en el rendimiento.
  • Otra optimización ahorra espacio cuando los dicts comparten claves (en casos especiales).

El aspecto ordenado no es oficial a partir de Python 3.6, pero es oficial en Python 3.7 .

Los diccionarios de Python son tablas hash

Durante mucho tiempo, funcionó exactamente así. Python preasignaría 8 filas vacías y usaría el hash para determinar dónde pegar el par clave-valor. Por ejemplo, si el hash para la clave finalizó en 001, lo pegaría en el índice 1 (como en el ejemplo a continuación).

hash key value null null null ...010001 ffeb678c 633241c4 # addresses of the keys and values null null null ... ... ...

Cada fila ocupa 24 bytes en una arquitectura de 64 bits, 12 en 32 bits. (Tenga en cuenta que los encabezados de las columnas son solo etiquetas, en realidad no existen en la memoria).

Si el hash terminó igual que el hash de una clave preexistente, esto es una colisión, y luego se pegaría el par clave-valor en una ubicación diferente.

Después de almacenar 5 valores-clave, al agregar otro par de valores-clave, la probabilidad de colisiones hash es demasiado grande, por lo que el diccionario se duplica en tamaño. En un proceso de 64 bits, antes del cambio de tamaño, tenemos 72 bytes vacíos, y después, estamos perdiendo 240 bytes debido a las 10 filas vacías.

Esto toma mucho espacio, pero el tiempo de búsqueda es bastante constante. El algoritmo de comparación de claves es calcular el hash, ir a la ubicación esperada, comparar la identificación de la clave: si son el mismo objeto, son iguales. Si no, entonces compara los valores de hash, si no son los mismos, no son iguales. De lo contrario, finalmente comparamos las claves de igualdad, y si son iguales, devolvemos el valor. La comparación final para la igualdad puede ser bastante lenta, pero las comprobaciones anteriores suelen abreviar la comparación final, lo que hace que las búsquedas sean muy rápidas.

(Las colisiones ralentizan las cosas, y un atacante podría, en teoría, utilizar colisiones de hash para realizar un ataque de denegación de servicio, por lo que aleatorizamos la función de hash de manera que calcule un hash diferente para cada nuevo proceso de Python).

El espacio desperdiciado descrito anteriormente nos ha llevado a modificar la implementación de los diccionarios, con una nueva y emocionante característica (aunque no oficial) de que los diccionarios ahora están ordenados (por inserción).

Las nuevas tablas compactas de hash

Comenzamos, en cambio, preasignando una matriz para el índice de la inserción.

Dado que nuestro primer par clave-valor va en la segunda ranura, indexamos así:

[null, 0, null, null, null, null, null, null]

Y nuestra tabla se rellena por orden de inserción:

hash key value ...010001 ffeb678c 633241c4 ... ... ...

Entonces, cuando hacemos una búsqueda de una clave, usamos el hash para verificar la posición que esperamos (en este caso, vamos directamente al índice 1 de la matriz), luego vamos a ese índice en la tabla hash (por ejemplo, el índice 0 ), verifique que las teclas sean iguales (utilizando el mismo algoritmo descrito anteriormente) y, de ser así, devuelva el valor.

Retenemos el tiempo de búsqueda constante, con pérdidas menores de velocidad en algunos casos y ganancias en otros, con la ventaja de que ahorramos bastante espacio sobre la implementación preexistente. El único espacio desperdiciado son los bytes nulos en la matriz de índice.

Raymond Hettinger introdujo esto en python-dev en diciembre de 2012. Finalmente llegó a CPython en Python 3.6 . Ordenar por inserción aún se considera un detalle de implementación para permitir que otras implementaciones de Python tengan la oportunidad de ponerse al día.

Claves compartidas

Otra optimización para ahorrar espacio es una implementación que comparte claves. Por lo tanto, en lugar de tener diccionarios redundantes que ocupan todo ese espacio, tenemos diccionarios que reutilizan las claves compartidas y los hashes de las claves. Puedes pensarlo así:

hash key dict_0 dict_1 dict_2... ...010001 ffeb678c 633241c4 fffad420 ... ... ... ... ... ...

Para una máquina de 64 bits, esto podría ahorrar hasta 16 bytes por clave por diccionario adicional.

Claves compartidas para objetos personalizados y alternativas

Estos dicts de clave compartida están destinados a ser utilizados para los objetos personalizados __dict__ . Para obtener este comportamiento, creo que necesitas terminar de __dict__ tu __dict__ antes de crear una instancia de tu próximo objeto ( ver PEP 412 ). Esto significa que debe asignar todos sus atributos en __init__ o __new__ , de lo contrario, es posible que no obtenga sus ahorros de espacio.

Sin embargo, si conoce todos sus atributos en el momento en que se ejecuta su __init__ , también puede proporcionar __slots__ para su objeto, y garantizar que __dict__ no se crea en absoluto (si no está disponible en los padres), o incluso permitir __dict__ pero garantizar que Sus atributos previstos se almacenan en las ranuras de todos modos. Para más información sobre __slots__ , vea mi respuesta aquí .

Ver también:

¿Alguien sabe cómo se implementa el tipo de diccionario incorporado para python? Entiendo que es una especie de tabla hash, pero no he podido encontrar ningún tipo de respuesta definitiva.

Aquí está todo sobre los dictados de Python que pude juntar (probablemente más de lo que a todos les gustaría saber; pero la respuesta es completa).

  • Los diccionarios de Python se implementan como tablas hash .
  • Las tablas hash deben permitir colisiones hash, es decir, incluso si dos claves distintas tienen el mismo valor hash, la implementación de la tabla debe tener una estrategia para insertar y recuperar los pares clave y valor de forma inequívoca.
  • Python dict utiliza direccionamiento abierto para resolver colisiones de hash (se explica a continuación) (ver dictobject.c:296-297 ).
  • La tabla hash de Python es solo un bloque de memoria contiguo (algo así como una matriz, por lo que puede hacer una búsqueda O(1) por índice).
  • Cada ranura de la tabla puede almacenar una y solo una entrada. Esto es importante.
  • Cada entrada en la tabla en realidad es una combinación de los tres valores: <hash, clave, valor> . Esto se implementa como una estructura en C (ver dictobject.h:51-56 ).

  • La siguiente figura es una representación lógica de una tabla hash de Python. En la siguiente figura, 0, 1, ..., i, ... a la izquierda están los índices de las ranuras en la tabla hash (¡son solo para fines ilustrativos y no se almacenan junto con la tabla obviamente!).

    # Logical model of Python Hash table -+-----------------+ 0| <hash|key|value>| -+-----------------+ 1| ... | -+-----------------+ .| ... | -+-----------------+ i| ... | -+-----------------+ .| ... | -+-----------------+ n| ... | -+-----------------+

  • Cuando se inicializa un nuevo dictado, comienza con 8 ranuras . (ver dictobject.h:49 )

  • Al agregar entradas a la tabla, comenzamos con alguna ranura, i , que se basa en el hash de la clave. CPython inicialmente usa i = hash(key) & mask (donde mask = PyDictMINSIZE - 1 , pero eso no es realmente importante). Solo tenga en cuenta que la ranura inicial, i , que se comprueba depende del hash de la clave.
  • Si esa ranura está vacía, la entrada se agrega a la ranura (por entrada, quiero decir, <hash|key|value> ). Pero, ¿y si esa ranura está ocupada? Probablemente porque otra entrada tiene el mismo hash (colisión de hash!)
  • Si la ranura está ocupada, CPython (e incluso PyPy) compara el hash Y la clave (por comparación quiero decir == comparación no is comparación) de la entrada en la ranura con el hash y la clave de la entrada actual que se insertará ( dictobject.c:337,344-345 ) respectivamente. Si ambos coinciden, cree que la entrada ya existe, se da por vencida y pasa a la siguiente entrada que se insertará. Si el hash o la clave no coinciden, se inicia el sondeo .
  • Sondeo simplemente significa que busca las ranuras por ranura para encontrar una ranura vacía. Técnicamente podríamos ir uno por uno, i+1, i+2, ... y usar el primero disponible (es decir, sondeo lineal). Pero por razones explicadas a la dictobject.c:33-126 en los comentarios (ver dictobject.c:33-126 ), CPython usa sondeo aleatorio . En el sondeo aleatorio, la siguiente ranura se selecciona en un orden pseudoaleatorio. La entrada se agrega a la primera ranura vacía. Para esta discusión, el algoritmo real utilizado para elegir la siguiente ranura no es realmente importante (vea dictobject.c:33-126 para el algoritmo de sondeo). Lo que es importante es que las ranuras sondadas hasta que se encuentre la primera ranura vacía.
  • Lo mismo sucede con las búsquedas, solo comienza con la ranura inicial i (donde depende del hash de la clave). Si el hash y la clave no coinciden con la entrada en la ranura, comienza a sondear, hasta que encuentra una ranura con una coincidencia. Si todas las ranuras están agotadas, informa un error.
  • Por cierto, el dict cambiará de tamaño si está lleno a dos tercios. Esto evita ralentizar las búsquedas. (ver dictobject.h:64-65 )

NOTA: Hice la investigación sobre la implementación de Python Dict en respuesta a mi propia question sobre cómo múltiples entradas en un dict pueden tener los mismos valores hash. Publiqué una versión ligeramente editada de la respuesta aquí porque toda la investigación es muy relevante también para esta pregunta.

Los diccionarios de Python utilizan direccionamiento abierto ( referencia dentro del código Beautiful )

¡NÓTESE BIEN! El direccionamiento abierto , también conocido como hashing cerrado , no debe confundirse con su hashing abierto opuesto, como se señala en Wikipedia .

El direccionamiento abierto significa que el dict utiliza ranuras de matriz, y cuando se toma la posición principal de un objeto en el dict, se busca el lugar del objeto en un índice diferente en la misma matriz, utilizando un esquema de "perturbación", donde el valor de hash del objeto juega parte .