Geekly articles weekly

Implementación del diccionario en Python

Hola a todos, el 30 de abril, el curso Algorithms for Developers comienza en OTUS, y la publicación del material de hoy está dedicada a esto. Empecemos



En este artículo, aprenderá cómo se implementan los diccionarios en Python.
Los diccionarios se indexan con claves y se pueden considerar como matrices asociadas. Agreguemos 3 pares clave / valor al diccionario:

>>> d = {'a': 1, 'b': 2} >>> d['c'] = 3 >>> d {'a': 1, 'b': 2, 'c': 3}

Se puede acceder a los valores de la siguiente manera:

 >>> d['a'] 1 >>> d['b'] 2 >>> d['c'] 3 >>> d['d'] Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 'd'

La clave “d” no existe, por lo que se producirá un error KeyError.

Tablas hash

Los diccionarios en Python se implementan utilizando tablas hash. Son matrices cuyos índices se calculan utilizando funciones hash. El objetivo de la función hash es distribuir uniformemente las claves en la matriz. Una buena función hash minimiza el número de colisiones, es decir la probabilidad de que diferentes claves tengan el mismo hash. No hay tales funciones hash en Python. Sus funciones hash más importantes (para cadenas y valores enteros) producen valores similares en casos generales:

 >>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462]

Asumiremos que hasta el final de este artículo usaremos cadenas como claves. La función hash en Python para cadenas se define de la siguiente manera:

 arguments: string object returns: hash function string_hash: if hash cached: return it set len to string's length initialize var p pointing to 1st char of string object set x to value pointed by p left shifted by 7 bits while len >= 0: set var x to (1000003 * x) xor value pointed by p increment pointer p set x to x xor length of string object cache x as the hash so we don't need to calculate it again return x as the hash

Si ejecuta hash('a') en Python, 12416037344 string_hash() y devolverá 12416037344 . Aquí usamos la máquina de 64 bits por defecto.

Si usa una matriz de tamaño para almacenar los pares valor / clave, se usará una máscara para calcular el índice de la celda de la celda en la matriz, que se calcula como -1 . Este enfoque hace que el cálculo de índices de celda sea rápido. La probabilidad de encontrar una celda vacía es bastante alta debido al mecanismo de cambio de tamaño, que se describe a continuación. Esto significa que un cálculo simple tiene sentido en la mayoría de los casos. El tamaño de la matriz es 8, el índice para 'a' será: hash('a') & 7 = 0 . El índice para 'b' es 2, el índice para 'c' es 3, el índice para 'z' es 3, al igual que para 'b' , y aquí es donde tenemos una colisión.



Como podemos ver, una función hash en Python hace su trabajo de manera de calidad cuando las teclas son secuenciales, lo cual es bueno, ya que a menudo tiene que trabajar con dichos datos. Sin embargo, tan pronto como agreguemos la tecla 'z' , se produce una colisión porque no es consistente con las anteriores.

Podríamos usar una lista vinculada para almacenar pares, que tienen el mismo hash, pero esto aumentaría el tiempo de búsqueda y no sería igual a O (1) en promedio. La siguiente sección describe el método de resolución de colisión utilizado para los diccionarios en Python.

Direccionamiento abierto

El direccionamiento abierto es una técnica de resolución de colisiones que utiliza sondeo. En el caso de 'z' , el índice de la celda 3 ya se utiliza en la matriz, por lo que debemos buscar otro índice que aún no se haya utilizado. La operación de agregar un par clave / valor toma en promedio O (1), así como la operación de búsqueda.

Para buscar células libres, se utiliza una secuencia de sondeo cuadrática. Se implementa de la siguiente manera:

 j = (5*j) + 1 + perturb; perturb >>= PERTURB_SHIFT; use j % 2**i as the next table index;

La recursividad en (5 * j) +1 aumenta rápidamente grandes diferencias en bits que no afectaron el índice original. La variable "perturb" en este caso toma los otros bits del código hash.

Veamos por curiosidad qué sucede si tenemos una secuencia de muestra con un tamaño de tabla 32 y j = 3.

3 -> 11 -> 19 -> 29 -> 5 -> 6 -> 16 -> 31 -> 28 -> 13 -> 2 ...

Puede obtener más información sobre esta secuencia de sondeo consultando el código fuente dictobject.c . Puede encontrar una explicación detallada del mecanismo de sondeo en la parte superior del archivo.



Veamos el código fuente de Python con este ejemplo.

C estructuras de diccionario

La siguiente estructura C se utiliza para almacenar la entrada en el diccionario: par clave / valor. El hash, la clave y el valor se almacenan. PyObject es la clase base para objetos en Python.

 typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; } PyDictEntry;

La siguiente estructura es un diccionario. ma_fill es el número total de celdas usadas e inactivas. Una celda se considera inactiva cuando se elimina un par de claves. ma_used es el número de celdas usadas (activas). ma_mask es igual al tamaño de la matriz -1 y se usa para calcular el índice de la celda. ma_table es una matriz, y ma_smalltable es la matriz original de tamaño 8.

 typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; Py_ssize_t ma_used; Py_ssize_t ma_mask; PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; };

Inicialización de vocabulario

Cuando solo crea un diccionario, se PyDict_New() función PyDict_New() . Eliminé algunas líneas y convertí el código C en pseudocódigo para enfocarme en conceptos clave.

PyDict_New() :

  • Devuelve un objeto de diccionario;
  • Asigna un nuevo objeto de diccionario;
  • Borra la tabla del diccionario;
  • Establece el número de celdas de diccionario y celdas no utilizadas ( ma_fill ) en 0;
  • Establece el número de celdas activas ( ma_used ) en 0;
  • Establece la máscara del diccionario ( ma_value ) en un valor igual al tamaño del diccionario: 1 = 7;
  • Establece la función de búsqueda del diccionario lookdict_string ;
  • Devuelve el objeto del diccionario asignado.

Agregar elemento

Cuando se agrega un nuevo par clave / valor, PyDict_SetItem() llama a PyDict_SetItem() . Esta función acepta un puntero a un objeto de diccionario y un par clave / valor como entrada. Comprueba si la clave es una cadena y evalúa el hash o reutiliza el almacenamiento en caché si existe. Se llama a insertdict() para agregar un nuevo par clave / valor y el tamaño del diccionario cambia si el número de celdas usadas y no usadas es más de 2/3 del tamaño de la matriz.

¿Por qué exactamente 2/3? Esto es necesario para garantizar que la secuencia de la sonda pueda encontrar células libres lo suficientemente rápido. Más adelante consideraremos la función para cambiar el tamaño.

 arguments: dictionary, key, value returns: 0 if OK or -1 function PyDict_SetItem: if key's hash cached: use hash else: calculate hash call insertdict with dictionary object, key, hash and value if key/value pair added successfully and capacity over 2/3: call dictresize to resize dictionary's table

inserdict() usa la función de búsqueda lookdict_string() para encontrar una celda libre. La misma función se usa para buscar una clave.

lookdict_string() calcula el índice de la celda utilizando valores hash y de máscara. Si no puede encontrar la clave por el valor de índice de celda = hash y máscara (índice de ranura = hash y máscara), comienza a sondear utilizando el ciclo descrito anteriormente hasta que encuentra una celda libre. En el primer intento de sondeo, si la clave es null , devuelve una celda no utilizada si se encontró durante la primera búsqueda. Esto garantiza la prioridad para reutilizar celdas eliminadas previamente.
Queremos agregar los siguientes pares clave / valor: {'a': 1, 'b': 2′, 'z': 26, 'y': 25, 'c': 5, 'x': 24} . Esto es lo que sucederá:

La estructura del diccionario se asigna con un tamaño de tabla de 8.

  • PyDict_SetItem: clave = 'a', valor = 1
    • hash = hash ('a') = 12416037344
    • Insertar
      • lookdict_string
        • índice de ranura = hash y máscara = 12416037344 y 7 = 0
        • la ranura 0 no se usa, devuelve esta celda
      • inicialización de entrada en el índice 0 con clave, valor y hash
      • ma_used = 1, ma_fill = 1
  • PyDict_SetItem: clave = 'b', valor = 2
    • hash = hash ('b') = 12544037731
    • Insertar
      • lookdict_string
        • índice de ranura = hash y máscara = 12544037731 y 7 = 3
        • la ranura 3 no se usa, devuelva esta celda
      • Inicialización de la entrada en el índice 3 con clave, valor y hash
      • ma_used = 2, ma_fill = 2
  • PyDict_SetItem: clave = 'z', valor = 26
    • hash = hash ('z') = 15616046971
    • Insertar
      • lookdict_string
        • índice de ranura = hash y máscara = 15616046971 y 7 = 3
        • se usa la ranura 3, pruebe con otra celda: 5 es gratis

        inicialización de entrada en el índice 5 con clave, valor y hash
        ma_used = 3, ma_fill = 3
  • PyDict_SetItem: clave = 'y', valor = 25
    • hash = hash ('y') = 15488046584
    • Insertar
      • lookdict_string
        • índice de ranura = hash y máscara = 15488046584 y 7 = 0
        • se usa la ranura 0, pruebe con otra celda: 1 es libre
      • Inicialización de la entrada en el índice 1 con clave, valor y hash
      • ma_used = 4, ma_fill = 4

PyDict_SetItem: clave = 'c', valor = 3
  • hash = hash ('c') = 12672038114
  • Insertar
    • lookdict_string
      • índice de ranura = hash y máscara = 12672038114 y 7 = 2
      • la ranura 2 no se usa, devuelva esta celda
    • Inicialización de la entrada en el índice 2 con clave, valor y hash
    • ma_used = 5, ma_fill = 5

PyDict_SetItem: clave = 'x', valor = 24
  • hash = hash ('x') = 15360046201
  • Insertar
    • lookdict_string
      • índice de ranura = hash y máscara = 15360046201 y 7 = 1
      • se usa la ranura 1, pruebe con otra celda: 7 es gratis
    • Inicialización de la entrada en el índice 7 con clave, valor y hash
    • ma_used = 6, ma_fill = 6

Esto es lo que obtenemos:



Ahora se utilizan 6 de las 8 celdas, más de 2/3 de la capacidad de la matriz está ocupada. Se llama a dictresize() para asignar una matriz más grande. Esta función también copia registros de la tabla anterior a la nueva.

dictresize () se llama con minused = 24 en nuestro caso, donde 4 * ma_used . 2 * ma_used usa cuando el número de celdas utilizadas es muy grande (más de 50,000). ¿Por qué es 4 veces más células? Esto reduce el número de pasos para implementar el cambio de tamaño y aumenta la escasez.

El nuevo tamaño de la tabla debe ser mayor que 24, se calcula desplazando el tamaño actual en 1 bit hacia la izquierda hasta que el tamaño de la tabla sea superior a 24. Como resultado, será 32, por ejemplo, 8 -> 16 -> 32.

Esto es lo que le sucede a nuestra tabla durante el cambio de tamaño: se resalta una nueva tabla de tamaño 32. Las entradas de la tabla anterior se insertan en la nueva tabla utilizando un nuevo valor de máscara de 31. El resultado es el siguiente:



Eliminar elementos

Se llama a PyDict_DelItem() para eliminar registros. El hash se calcula para la clave de registro, luego se llama a la función de búsqueda para devolver el registro. Ahora la celda está vacía.

Queremos eliminar la tecla c de nuestro diccionario. Como resultado, obtenemos la siguiente matriz:



Tenga en cuenta que la operación de eliminar un elemento no cambia el tamaño de la matriz si el número de celdas utilizadas es mucho menor que su número total. Sin embargo, cuando se agrega un par clave / valor, la necesidad de cambiar el tamaño depende del número de celdas usadas e inactivas, por lo que la operación de adición también puede reducir la matriz.

Esta publicación ha llegado a su fin, y tradicionalmente esperamos sus comentarios e invitamos a todos a una lección abierta , que se llevará a cabo el 18 de abril.

Source: https://habr.com/ru/post/448350/

More articles:


All Articles