Geekly articles weekly

Implementação de dicionário em Python

Olá pessoal, em 30 de abril, o curso Algoritmos para desenvolvedores começa na OTUS, e a publicação do material de hoje é dedicada a isso. Vamos começar.



Neste artigo, você aprenderá como os dicionários são implementados no Python.
Os dicionários são indexados usando chaves e podem ser considerados como matrizes associadas. Vamos adicionar 3 pares de chave / valor ao dicionário:

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

Os valores podem ser acessados ​​da seguinte maneira:

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

A chave “d” não existe, portanto ocorrerá um erro de KeyError.

Tabelas de hash

Os dicionários em Python são implementados usando tabelas de hash. São matrizes cujos índices são calculados usando funções de hash. O objetivo da função hash é distribuir uniformemente as chaves na matriz. Uma boa função de hash minimiza o número de colisões, ou seja, a probabilidade de que chaves diferentes tenham o mesmo hash. Não existem funções de hash no Python. Suas funções hash mais importantes (para cadeias e valores inteiros) produzem valores semelhantes em casos gerais:

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

Assumiremos que até o final deste artigo, usaremos cadeias de caracteres como chaves. A função hash no Python para strings é definida da seguinte maneira:

 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

Se você executar o hash('a') no Python, ele 12416037344 string_hash() e retornará 12416037344 . Aqui, usamos a máquina de 64 bits por padrão.

Se uma matriz de tamanho usada para armazenar os pares valor / chave, uma máscara será usada para calcular o índice da célula da célula na matriz, que é calculada como -1 . Essa abordagem facilita o cálculo dos índices de células. A probabilidade de encontrar uma célula vazia é bastante alta devido ao mecanismo de redimensionamento, descrito abaixo. Isso significa que um cálculo simples faz sentido na maioria dos casos. O tamanho da matriz é 8, o índice para 'a' será: hash('a') & 7 = 0 . O índice para 'b' é 2, o índice para 'c' é 3, o índice para 'z' é 3, assim como para 'b' , e é aqui que temos uma colisão.



Como podemos ver, uma função de hash no Python faz seu trabalho de maneira qualitativa quando as chaves são seqüenciais, o que é bom, pois muitas vezes você precisa trabalhar com esses dados. No entanto, assim que adicionamos a chave 'z' , ocorre uma colisão porque não é consistente com as anteriores.

Poderíamos usar uma lista vinculada para armazenar pares, mantendo o mesmo hash, mas isso aumentaria o tempo de pesquisa e não seria igual a O (1) em média. A seção a seguir descreve o método de resolução de colisão usado para dicionários em Python.

Endereçamento aberto

O endereçamento aberto é uma técnica de resolução de colisão que usa a sondagem. No caso de 'z' , o índice da célula 3 já está sendo usado na matriz, portanto, precisamos procurar outro índice que ainda não foi usado. A operação de adição de um par de chave / valor leva em média O (1), bem como a operação de pesquisa.

Para procurar células livres, é usada uma sequência de sondagem quadrática. É implementado da seguinte maneira:

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

A recursão em (5 * j) +1 aumenta rapidamente grandes diferenças em bits que não afetam o índice original. A variável "perturb" , neste caso, recebe os outros bits do código hash.

Vamos olhar por curiosidade o que acontece se tivermos uma sequência de amostra com o tamanho da tabela 32 ej = 3.

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

Você pode aprender mais sobre essa sequência de análise consultando o código-fonte dictobject.c . Uma explicação detalhada do mecanismo de detecção pode ser encontrada na parte superior do arquivo.



Vamos dar uma olhada no código fonte do Python com este exemplo.

Estruturas de dicionário C

A seguinte estrutura C é usada para armazenar a entrada no dicionário: par chave / valor. O hash, chave e valor são armazenados. PyObject é a classe base para objetos em Python.

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

A estrutura a seguir é um dicionário. ma_fill é o número total de células usadas e inativas. Uma célula é considerada inativa quando um par de chaves é excluído. ma_used é o número de células usadas (ativas). ma_mask é igual ao tamanho da matriz -1 e é usado para calcular o índice de células. ma_table é uma matriz e ma_smalltable é a matriz original de tamanho 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]; };

Inicialização de vocabulário

Quando você cria um dicionário, a função PyDict_New() é PyDict_New() . Eu apaguei algumas linhas e converti o código C em pseudo-código para focar nos conceitos-chave.

PyDict_New() :

  • Retorna um objeto de dicionário;
  • Aloca um novo objeto de dicionário;
  • Limpa a tabela do dicionário;
  • Define o número de células de dicionário usadas e células não utilizadas ( ma_fill ) como 0;
  • Define o número de células ativas ( ma_used ) como 0;
  • Define a máscara do dicionário ( ma_value ) para um valor igual ao tamanho do dicionário - 1 = 7;
  • Define a função de pesquisa de dicionário lookdict_string ;
  • Retorna o objeto de dicionário alocado.

Adicionar item

Quando um novo par de chave / valor é adicionado, PyDict_SetItem() chamado. Esta função aceita um ponteiro para um objeto de dicionário e um par de chave / valor como entrada. Ele verifica se a chave é uma sequência e avalia o hash ou reutiliza o cache, se houver. insertdict() é chamado para adicionar um novo par de chave / valor e o tamanho do dicionário muda se o número de células usadas e não utilizadas tiver mais de 2/3 do tamanho da matriz.

Por que exatamente 2/3? Isso é necessário para garantir que a sequência da sonda possa encontrar células livres com rapidez suficiente. Mais tarde, consideraremos a função para redimensionar.

 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 a função de pesquisa lookdict_string() para encontrar uma célula livre. A mesma função é usada para procurar uma chave.

lookdict_string() calcula o índice da célula usando valores de hash e máscara. Se ela não conseguir encontrar a chave pelo valor da célula index = hash & mask (slot index = hash & mask), ela começará a pesquisar usando o ciclo descrito acima até encontrar uma célula livre. Na primeira tentativa de investigação, se a chave for null , ela retornará uma célula não utilizada se for encontrada durante a primeira pesquisa. Isso garante prioridade para reutilizar células excluídas anteriormente.
Queremos adicionar os seguintes pares de chave / valor: {'a': 1, 'b': 2′, 'z': 26, 'y': 25, 'c': 5, 'x': 24} . Aqui está o que vai acontecer:

A estrutura do dicionário é alocada com um tamanho de tabela 8.

  • PyDict_SetItem: chave = 'a', valor = 1
    • hash = hash ('a') = 12416037344
    • insertdict
      • lookdict_string
        • slot index = hash e máscara = 12416037344 & 7 = 0
        • slot 0 não for usado, retorne esta célula
      • inicialização da entrada no índice 0 com chave, valor e hash
      • ma_used = 1, ma_fill = 1
  • PyDict_SetItem: chave = 'b', valor = 2
    • hash = hash ('b') = 12544037731
    • insertdict
      • lookdict_string
        • índice de slot = hash e máscara = 12544037731 & 7 = 3
        • slot 3 não for usado, retorne esta célula
      • inicialização da entrada no índice 3 com chave, valor e hash
      • ma_used = 2, ma_fill = 2
  • PyDict_SetItem: chave = 'z', valor = 26
    • hash = hash ('z') = 15616046971
    • insertdict
      • lookdict_string
        • slot index = hash e máscara = 15616046971 & 7 = 3
        • usado o slot 3, tente outra célula: 5 é gratuito

        inicialização da entrada no índice 5 com chave, valor e hash
        ma_used = 3, ma_fill = 3
  • PyDict_SetItem: chave = 'y', valor = 25
    • hash = hash ('y') = 15488046584
    • insertdict
      • lookdict_string
        • slot index = hash e máscara = 15488046584 & 7 = 0
        • slot 0 for usado, tente outra célula: 1 é grátis
      • inicialização da entrada no índice 1 com chave, valor e hash
      • ma_used = 4, ma_fill = 4

PyDict_SetItem: chave = 'c', valor = 3
  • hash = hash ('c') = 12672038114
  • insertdict
    • lookdict_string
      • slot index = hash e máscara = 12672038114 & 7 = 2
      • slot 2 não for usado, retorne esta célula
    • inicialização da entrada no índice 2 com chave, valor e hash
    • ma_used = 5, ma_fill = 5

PyDict_SetItem: chave = 'x', valor = 24
  • hash = hash ('x') = 15360046201
  • insertdict
    • lookdict_string
      • índice de slot = hash e máscara = 15360046201 & 7 = 1
      • slot 1 usado, tente outra célula: 7 é gratuito
    • inicialização da entrada no índice 7 com chave, valor e hash
    • ma_used = 6, ma_fill = 6

Aqui está o que temos:



Agora, 6 em 8 células são usadas, mais de 2/3 da capacidade da matriz está ocupada. dictresize() é chamado para alocar uma matriz maior. Essa função também copia registros da tabela antiga para a nova.

dictresize () é chamado com minused = 24 no nosso caso, onde 4 * ma_used . 2 * ma_used usado quando o número de células usadas é muito grande (mais de 50.000). Por que é 4 vezes mais células? Isso reduz o número de etapas para implementar o redimensionamento e aumenta a escassez.

O novo tamanho da tabela deve ser maior que 24, é calculado deslocando o tamanho atual em 1 bit para a esquerda até que o tamanho da tabela se torne mais de 24. Como resultado, serão 32, por exemplo, 8 -> 16 -> 32.

Aqui está o que acontece com a nossa tabela durante o redimensionamento: uma nova tabela de tamanho 32 é destacada.Entradas antigas da tabela são inseridas na nova tabela usando o novo valor de máscara 31. O resultado é o seguinte:



Excluir itens

PyDict_DelItem() é chamado para excluir registros. O hash é calculado para a chave do registro e a função de pesquisa é chamada para retornar o registro. Agora a célula está vazia.

Queremos remover a chave c do nosso dicionário. Como resultado, obtemos a seguinte matriz:



Observe que a operação de exclusão de um elemento não altera o tamanho da matriz se o número de células usadas for muito menor que o número total. No entanto, quando um par de chave / valor é adicionado, a necessidade de redimensionar depende do número de células usadas e inativas; portanto, a operação de adição também pode reduzir a matriz.

Esta publicação chegou ao fim e, tradicionalmente, aguardamos seus comentários e convidamos todos a uma aula aberta , que será realizada em 18 de abril.

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

More articles:


All Articles