Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Hash tables como funcionam dicts e sets

Hash tables como funcionam dicts e sets

Palestra apresentada na Python Brasil 2023 em Caxias do Sul

Atributos de classes e de instâncias, espaços de nomes de módulos e argumentos nomeados de funções são alguns dos elementos fundamentais do Python representados na memória por dicionários. Até mesmo os tipos, funções e objetos embutidos são acessados através de um dicionário chamado __builtins__ .__dict__.

Esta palestra explica:

Nesta palestra veremos:

* O algoritmo e as estruturas de dados de tabelas de hash começando por seu uso em set, que é mais simples de entender.

* A otimização de memória que preserva a ordem de inserção de chaves em instâncias de dict (desde o Python 3.6) .

Luciano Ramalho

November 03, 2023
Tweet

More Decks by Luciano Ramalho

Other Decks in Programming

Transcript

  1. Testes de desempenho • haystack (palheiro): um array com 10_000_000

    de floats distintos • needles (agulhas): 1_000 floats, sendo 500 presentes em haystack, 500 ausentes • tarefa: procurar cada uma das 1_000 agulhas no palheiro e contar as ocorrências – a contagem será sempre 500
  2. Código da tarefa found = 0 for n in needles:

    if n in haystack: found += 1
  3. Resultados com listas de 5 tamanhos len(haysack) fator tempo* fator

    1_000 1× 9.12ms 1.00× 10_000 10× 78.22ms 8.58× 100_000 100× 767.98ms 84.25× 1_000_000 1_000× 8_020.31ms 879.90× 10_000_000 10_000× 78_558.78ms 8_618.63× * Tempos para buscar 1_000 floats em um laptop Core i7 2.2GHz rodando Python 3.8.
  4. Análise dos resultados com listas • Buscar 1_000 agulhas em

    uma lista de 1_000 itens levou 9ms; na lista de 10_000_000 itens levou 78s • Com o palheiro 10_000 maior, o tempo cresceu 8_619×
  5. Resultados com dicts de 5 tamanhos len(haysack) fator tempo* fator

    1_000 1× 0.10ms 1.00× 10_000 10× 0.11ms 1.10× 100_000 100× 0.16ms 1.58× 1_000_000 1_000× 0.37ms 3.76× 10_000_000 10_000× 0.52ms 5.17× * Tempos para buscar 1_000 floats em um laptop Core i7 2.2GHz rodando Python 3.8.
  6. Análise dos resultados com dicts • Buscar 1_000 agulhas em

    um dict de 1_000 itens levou 100µs; no dict de 10_000_000 itens levou 512µs (meio microssegundo por agulha) • Com o palheiro 10_000 maior, o tempo cresceu pouco mais que 5×
  7. Código da tarefa com & (sets ou dicts) found =

    0 for n in needles: if n in haystack: found += 1 found = len(needles & haystack) produz o mesmo resultado que
  8. Resultados com sets de 5 tamanhos len(haysack) fator tempo* fator

    1_000 1× 0.08ms 1.00× 10_000 10× 0.09ms 1.13× 100_000 100× 0.12ms 1.47× 1_000_000 1_000× 0.24ms 2.89× 10_000_000 10_000× 0.30ms 3.59× found = len(needles & haystack)
  9. Análise dos resultados com set & • Intersecção de set

    de 1_000 agulhas com set de 1_000 itens levou 83µs; no set com 10_000_000 de itens levou 298µs (298 nanossegundos por agulha) • Com o palheiro 10_000 maior, o tempo cresceu ≈ 3.6×
  10. Funções de hash • Um função de hash processa uma

    quantidade arbitrária de dados e devolve uma sequência de bits de tamanho fixo: o código hash ou simplesmente hash >>> bin(hash('A')) '0b10010101011000011000101001110011100101011000110011011000100010' >>> bin(hash('O tempo é o tecido da vida.-Antonio Candido')) '0b10111100100011100101100110110100000101000111011101111100100100'
  11. Funções de hash (2) • Uma boa função de hash

    usa um algoritmo de dispersão para que o hash de dois objetos parecidos sejam bastante diferentes, otimizando o espalhamento dos resultados >>> bin(hash('O tempo é o tecido da vida.-Antonio Candido')) '0b10111100100011100101100110110100000101000111011101111100100100' >>> bin(hash('O tempo é o tecido da vida. -Antonio Candido')) '0b11011000001001011110010101011011100101000111010110111111010011'
  12. Funções de hash em Python • A função hash() embutida

    no Python usa diferentes algoritmos para diferentes tipos. • Para str e bytes, usa o algoritmo criptográfico SipHash e um salt (constante aleatória) por processo • Para int até a largura da palavra*, usa o próprio int, exceto que hash(-1) é -2, porque o código -1 é reservado (como veremos logo mais)
  13. Hashes e igualdade • Para instâncias de classes de usuário,

    hash() invoca o método __hash__ na instância • Se dois objetos tem hashes diferentes, seus valores certamente são diferentes – Você precisa garantir isso implementando __hash__ e __eq__ se quiser criar objetos hasheable (hasheáveis)
  14. Colisão de hash • Por definição, podem existir objetos diferentes

    com o mesmo hash – Por exemplo: considere que há muito mais strings possíveis do que hashes de 64 bits • Se dois objetos de valores diferentes tem o mesmo hash, isso é uma colisão de hash – É esperado que isso aconteça às vezes, mas é difícil encontrar um exemplo real
  15. Hashes e igualdade (2) • Se dois objetos de valores

    iguais tem hashes diferentes, isso é um bug sério – Dicionários e sets em Python não funcionam se isso acontecer – Já que 1 == 1.0, então hash(1) == hash(1.0)
  16. Exemplos em CPython de 32 bits Valor Código hash 1

    00000000000000000000000000000001 != 0 1.0 00000000000000000000000000000001 ------------------------------------------------ 1.0 00000000000000000000000000000001 ! !!! ! !! ! ! ! ! !! !!! != 16 1.0001 00101110101101010000101011011101 ------------------------------------------------ 1.0001 00101110101101010000101011011101 !!! !!!! !!!!! !!!!! !! ! != 20 1.0002 01011101011010100001010110111001 ------------------------------------------------ 1.0002 01011101011010100001010110111001 ! ! ! !!! ! ! !! ! ! ! !!!! != 17 1.0003 00001100000111110010000010010110
  17. Como é armazenado um set Considere um set com 5

    elementos: Note: a ordem dos elementos não é preservada. >>> workdays = {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'} >>> workdays {'Tue', 'Mon', 'Wed', 'Fri', 'Thu'}
  18. Um set e sua hash table >>> workdays = {'Mon',

    'Tue', 'Wed', 'Thu', 'Fri'} hash table com 8 baldes (buckets) ocupação máxima: ⅔
  19. Consulta: 'Mon' in weekdays >>> day = 'Mon' >>> h

    = hash(day) >>> h 4199492796428269555
  20. Consulta: 'Mon' in weekdays >>> day = 'Mon' >>> h

    = hash(day) >>> h 4199492796428269555 >>> offset = h % len(htable) >>> offset 3
  21. Consulta: 'Mon' in weekdays >>> day = 'Mon' >>> h

    = hash(day) >>> h 4199492796428269555 >>> offset = h % len(htable) >>> offset 3 >>> htable[offset].code == h True ✔
  22. Consulta: 'Mon' in weekdays >>> day = 'Mon' >>> h

    = hash(day) >>> h 4199492796428269555 >>> offset = h % len(htable) >>> offset 3 >>> htable[offset].code == h True >>> htable[offset].value == day True ✔ ✔ resultado: True
  23. Consulta 2: 'Fri' in weekdays >>> day = 'Fri' >>>

    h = hash(day) >>> h 7021641685991143771
  24. Consulta 2: 'Fri' in weekdays >>> day = 'Fri' >>>

    h = hash(day) >>> h 7021641685991143771 >>> offset = h % len(htable) >>> offset 3
  25. Consulta 2: 'Fri' in weekdays >>> day = 'Fri' >>>

    h = hash(day) >>> h 7021641685991143771 >>> offset = h % len(htable) >>> offset 3 >>> htable[offset].code == h False ✖ colisão de índice (index collision)
  26. Consulta 2: 'Fri' in weekdays >>> day = 'Fri' >>>

    h = hash(day) >>> h 7021641685991143771 >>> offset = h % len(htable) >>> offset 3 >>> htable[offset].code == h False >>> offset += 1 >>> offset 4 >>> htable[offset].code == h False ✖ ✖ 2ª colisão de índice
  27. Consulta 2: 'Fri' in weekdays ... >>> # continuando... >>>

    offset += 1 >>> offset 5 >>> htable[offset].code == h True ✖ ✖ ✔ ✔
  28. Consulta 2: 'Fri' in weekdays ✖ ✖ ✔ ✔ ✔

    ... >>> # continuando... >>> offset += 1 >>> offset 5 >>> htable[offset].code == h True >>> htable[offset].value == day True resultado: True
  29. Consulta 3: 'Sat' in weekdays >>> day = 'Sat' >>>

    h = hash(day) >>> h 6624772952138908622 >>> offset = h % len(htable) >>> offset 6 >>> htable[offset].code = -1 True balde vazio, resultado: False ⭕
  30. Exemplos de inserção de elemento >>> s = {1.0, 2.0,

    3.0} >>> s.add(4) >>> s {1.0, 2.0, 3.0, 4} >>> s.add(1) >>> s ???
  31. Exemplos de inserção de elemento >>> s = {1.0, 2.0,

    3.0} >>> s.add(4) >>> s {1.0, 2.0, 3.0, 4} >>> s.add(1) >>> s {1.0, 2.0, 3.0, 4}
  32. Consequências da implementação • Elementos tem que ser hasheable –

    obrigatório implementar __hash__ e __eq__ • Pesquisar é calcular hash, offset, e comparar – tempo quase não depende do tamanho do set • A ordem não é preservada e pode mudar – quando o set cresce, a hash table é refeita • Mínimo de ⅓ de espaço ocioso na hash table
  33. Como era armazenado um dict Considere um dict com 4

    itens: A ordem dos itens não era preservada. students = {'Mon': 14, 'Tue': 12, 'Wed': 14, 'Thu': 11}
  34. Um dict antigo e sua hash table students = {'Mon':

    14, 'Tue': 12, 'Wed': 14, 'Thu': 11}
  35. Tabela de índices otimiza o espaço a tabela de índices

    usa inteiros de 8 bits para dicts com até 127 elementos, 16 bits até 32_767, etc.
  36. Tabela de entradas é compacta a tabela de entradas não

    tem baldes vazios, e preserva a ordem de inserção dos itens!
  37. Inserção de elementos Calcula hash e offset (3); se índice

    é -1, adiciona entrada e coloca índice 0 no offset 3
  38. Inserção de elementos Calcula hash e offset (2); se índice

    é -1, adiciona entrada e coloca índice 1 no offset 2
  39. Inserção de elementos Calcula hash e offset (4); se índice

    é -1, adiciona entrada e coloca índice 2 no offset 4
  40. Inserção de elementos Calcula hash e offset (7); se índice

    é -1, adiciona entrada e coloca índice 3 no offset 7
  41. Consequências da implementação • Chaves tem que ser hasheable •

    Pesquisar é calcular hash, offset, e comparar – tempo quase não depende do tamanho do dict • A ordem de inserção é preservada – quando o dict cresce, cada novo item é salvo no final da tabela de entradas • Só há espaço ocioso na tabela de índices
  42. PEP 412: Key-sharing dictionary • Uma otimização de espaço adicional

    usada somente nos __dict__ de classes e instâncias, onde Python armazena os atributos • Só funciona para os atributos criados no __init__ • Detalhes no PEP 412 e neste texto: https://bit.ly/flupy-pep412
  43. Uma invenção de Hans Peter Luhn • Imigrou da Alemanha

    para os EUA antes dos nazistas tomarem o poder • Trabalhou na IBM • Inventor prolífico (KWIC etc.) • Ótimo artigo de história na revista IEEE Spectrum https://bit.ly/ieee-hans-luhn