Pesquisa de graduação comprova melhoria na velocidade de busca em tabelas hash

Introdução

• No outono de 2021, Andrew Krapivin, estudante de graduação da Rutgers University, se deparou com um artigo que mudaria sua vida.
• O artigo tratava de "ponteiros pequenos" usados para apontar informações na memória do computador.
• Krapivin concebeu uma forma de reduzir o tamanho dos ponteiros para diminuir o consumo de memória.

Descoberta de uma nova tabela hash

• Krapivin conduziu experimentos usando tabelas hash, um método comum de armazenar dados.
• Durante os experimentos, Krapivin acabou inventando um novo tipo de tabela hash que opera mais rápido do que as existentes.
• A descoberta levou a um resultado que derruba uma conjectura de 40 anos na ciência de dados.

A importância das tabelas hash

• As tabelas hash são uma das estruturas de dados mais antigas da ciência da computação e oferecem eficiência no armazenamento de dados.
• Elas são projetadas para executar três funções: buscar, remover e inserir elementos.

A conjectura de Yao e sua refutação

• Em 1985, o cientista da computação Andrew Yao apresentou uma conjectura sobre como encontrar elementos no pior caso em tabelas hash com certas propriedades.
• A nova tabela hash de Krapivin refuta a conjectura de Yao ao provar que, no pior caso, o tempo necessário para consultas e inserções é proporcional a (log x)².

Nova descoberta sobre o tempo médio de consulta

• Krapivin e sua equipe mostraram que, em tabelas hash não gananciosas, o tempo médio de consulta não depende de x.
• Isso significa que é possível atingir um tempo médio de consulta constante independentemente do grau de preenchimento da tabela hash.

Conclusão

• Este estudo aprofunda a compreensão sobre tabelas hash e pode levar a aplicações práticas.
• Esse entendimento sobre estruturas de dados pode servir de base para melhorias práticas no futuro.

[GN⁺]

Comentários no Hacker News

• Krapivin conseguiu um avanço sem conhecer a conjectura de Yao

  • O desenvolvedor de Balatro criou um jogo deck builder premiado sem conhecer os deck builders existentes
  • A melhor forma de abordar um problema pode ser desconhecer ou ignorar esforços anteriores semelhantes
  • O mundo atual é interconectado demais, então é fácil cair em estruturas de pensamento anteriores
  • A internet é excelente, mas tende a homogeneizar o mundo das ideias

• Ótimo resultado, mas parece que isso deveria ser chamado de conjectura da ciência da computação

• Fico curioso se alguém conhece um repositório no GitHub com essa implementação

• É legal, mas esse estilo de "culto à personalidade" do artigo me incomoda um pouco

  • Fico me perguntando se era mesmo necessário ver várias fotos de um jovem fazendo poses diferentes em ambiente universitário
  • Parece que precisamos de uma versão de La La Land para glorificar sobreviventes do sucesso na computação e assim incentivar mais participação

• Na nova tabela hash, o tempo necessário para consultas e inserções no pior caso é proporcional a (log x)²

  • O resultado da equipe pode não levar a aplicações imediatas
  • Não entendo por que isso não levaria a aplicações imediatas
  • Fico curioso se a análise de casos de uso reais é uma situação em que ela consegue ajustar implementações de hash melhor do que uma abordagem puramente matemática

• Ler este artigo é como ler a explicação do problema de Monty Hall

  • A conclusão parece contrariar o senso comum, mas pode ser provada
  • Até os próprios autores não esperavam que fosse possível alcançar um tempo médio constante de consulta independentemente da taxa de ocupação da tabela hash

• Um bom teste recente

  • Vamos ver se uma pesquisa profunda consegue chegar a esse resultado sem copiá-lo
  • gpt4, Gemini 2 e Claude não tiveram sorte
  • A ciência da computação conduzida por humanos ainda está segura

• Fico curioso se alguém tem uma implementação simples de 'Tiny pointers'

  • Minha mente vai primeiro para código/pseudocódigo, antes da prova

• Como o vilão de <i>Scooby Doo</i> sempre dizia:

  • <i>"E eu teria conseguido, se não fosse por essas crianças irritantes!"</i>

• Dei uma folheada no artigo, e a principal diferença que eles usam parece ser que o algoritmo de inserção da tabela hash procura mais longe em vez de preencher de forma gulosa o primeiro slot vazio

  • Eles combinam isso com uma ordem de sondagem comprovadamente eficiente para encontrar slots vazios mesmo quando a tabela está muito cheia
  • A inserção fica mais lenta quando a tabela hash está menos cheia, mas isso evita o pior cenário de não conseguir encontrar o último slot vazio restante

• Resultado teórico interessante, mas na prática o "truque" atual de alocar uma tabela maior do que o necessário provavelmente parece uma solução melhor

  • Por exemplo, o hashbrown do Rust deixa 1/8 da tabela (12,5%) vazia, usando um pouco mais de memória, mas tornando inserção/consulta muito rápidas