Estudante revoluciona "hash tables"
Um estudante universitário fez uma descoberta revolucionária que acelera as hash tables para valores superiores aos que se acreditava ser possível. As hash tables são uma estrutura de dados popular na computação, consistindo numa forma que permite guardar dados de forma a que seja facilmente e rapidamente acessíveis. Os problemas surgem quando se trata de guardar dados em tabelas já quase cheias, em que pode ser necessário procurar repetidamente por um espaço livre - tendo havido inúmeros estudos que avaliavam o seu desempenho para os piores casos possíveis, em que uma operação tivesse que procurar pelo máximo de tempo para encontrar o último espaço livre. Mas em 2021, Andrew Krapivin, ainda um estudante universitário, estava a tentar criar uma tabela que optimizasse o uso de memória após ter lido um artigo sobre "Tiny Pointers", e o resultado foi um novo tipo de tabela hash que supera os modelos anteriores. O seu método desafiou o pressupostos de que o tempo de pesquisa, no pior cenário, seria sempre proporcional à taxa ocupação da tabela. Em vez disso, ele demonstrou que a busca pode ser muito mais rápida, contrariando uma conjectura formulada em 1985 pelo conceituado cientista informático Andrew Yao. O inevitável cepticismo inicial rapidamente deu lugar a entusiasmo, à medida que mais especialistas analisavam as conclusões. Martín Farach-Colton, coautor do artigo original sobre "Tiny Pointers", e William Kuszmaul, da Carnegie Mellon University, confirmaram que a nova tabela hash não era apenas uma melhoria, mas marcava uma mudança fundamental na forma como se olham para estas estruturas. Adicionalmente, além de refutar a conjectura de Yao, a equipa de Krapivin descobriu que, em certos cenários, estas novas tabelas permitem que o tempo de pesquisa se mantenha constante independentemente da ocupação da tabela, algo que antes também se pensava ser impossível. O impacto destas alterações poderá demorar algum tempo até transitar para aplicações práticas, mas sabendo-se que as hash tables são usadas em inúmeras situações, espera-se que possa vir a contribuir para a optimização de todo o tipo de processos, das bases de dados aos sistemas operativos, das apps aos serviços de inteligência artificial.
As hash tables são uma estrutura de dados popular na computação, consistindo numa forma que permite guardar dados de forma a que seja facilmente e rapidamente acessíveis. Os problemas surgem quando se trata de guardar dados em tabelas já quase cheias, em que pode ser necessário procurar repetidamente por um espaço livre - tendo havido inúmeros estudos que avaliavam o seu desempenho para os piores casos possíveis, em que uma operação tivesse que procurar pelo máximo de tempo para encontrar o último espaço livre.
Mas em 2021, Andrew Krapivin, ainda um estudante universitário, estava a tentar criar uma tabela que optimizasse o uso de memória após ter lido um artigo sobre "Tiny Pointers", e o resultado foi um novo tipo de tabela hash que supera os modelos anteriores. O seu método desafiou o pressupostos de que o tempo de pesquisa, no pior cenário, seria sempre proporcional à taxa ocupação da tabela. Em vez disso, ele demonstrou que a busca pode ser muito mais rápida, contrariando uma conjectura formulada em 1985 pelo conceituado cientista informático Andrew Yao.
O impacto destas alterações poderá demorar algum tempo até transitar para aplicações práticas, mas sabendo-se que as hash tables são usadas em inúmeras situações, espera-se que possa vir a contribuir para a optimização de todo o tipo de processos, das bases de dados aos sistemas operativos, das apps aos serviços de inteligência artificial.
