Novo algoritmo de ordenação de livros alcança desempenho quase perfeito

Introdução

• Um novo algoritmo propõe uma forma de resolver o problema de ordenação em bibliotecas.
• Esse problema se aplica não apenas à organização de livros, mas também à disposição de arquivos em discos rígidos e bancos de dados.
• A nova abordagem combina o conteúdo anterior da estante com aleatoriedade para produzir resultados próximos do ideal teórico.

Reduzindo os limites

• Uma forma comum de medir uma estante bem organizada é observar quanto tempo leva para inserir itens individuais.
• Um artigo de 1981 levantou a questão de se seria possível projetar um algoritmo com tempo médio de inserção muito menor que n.
• Um estudo de 2004 descobriu que o melhor limite inferior para o problema de ordenação em bibliotecas é log n.
• Também mostrou que algoritmos suaves ou determinísticos não conseguem alcançar um tempo médio de inserção melhor que (log n)².

A história secreta

• Em 2022, Bender e seus colegas tentaram um algoritmo aleatório e não suave, reduzindo o tempo médio de inserção para (log n)¹.⁵.
• Esse algoritmo não depende do histórico anterior da estante, o que pode ser útil por razões de segurança.

Fechando a lacuna

• Bender e Kuszmaul reduziram o limite superior para (log n) × (log log n)³, chegando muito perto do limite inferior teórico.
• O algoritmo usa um grau limitado de dependência do histórico para planejar eventos futuros.
• O resultado se baseia em trabalhos anteriores, mas usa a aleatoriedade de uma maneira completamente diferente.

Conclusão

• O estudo representa uma melhoria importante do ponto de vista teórico e também pode ter grande potencial de melhoria em aplicações.
• Ainda assim, o termo log log n continua impedindo uma solução completa, e a resposta pode estar em reduzir o limite superior ou elevar o limite inferior.

[GN⁺]

Comentários do Hacker News

• É interessante que técnicas de criptografia possam ser usadas para melhorar o desempenho. Desempenho não é apenas executar mais instruções, mas escolher como fazer menos trabalho. A propriedade de segurança chamada "independência de histórico" significa não fazer o trabalho de rastrear o passado

• Foi difícil encontrar os principais artigos citados na matéria. Seria útil para os leitores se a Quanta listasse todas as referências no fim do artigo

  • [1] Nearly Optimal List Labeling: link
  • [2] A sparse table implementation of priority queues: link

• Existem algoritmos complexos para resolver o problema de posicionar itens arbitrariamente em uma tabela de banco de dados. Mas uma solução simples para esse problema é usar valores fracionários e, ocasionalmente, reorganizar a lista

• Lembro de ter proposto esse problema a alunos com base no algoritmo 'Library Sort'. O título do artigo original é 'Insertion Sort is O(n log n)'

• Fico em dúvida se há motivo para isso ser realmente mais rápido do que os algoritmos usados atualmente. Em arranjos de nós de B-tree, usar memmove() pode ser mais rápido. Para arranjos grandes, usar uma B-tree pode ser mais fácil

• Fico me perguntando se a formulação do problema pressupõe um arranjo pré-alocado de tamanho fixo

• Impressionante a forma como a Biblioteca Britânica gerencia livros. Quando um livro chega, o catálogo eletrônico cuida do restante, então não há necessidade de reorganizar os livros

• Quero transformar a animação no topo da matéria em um protetor de tela

• Links limpos para usuários de celular

  • Jogo: link
  • Código: link
  • Recurso sobre geometria de subpixel: link

• É verdade que o limite superior cai para (log n) vezes (log log n)^3. É interessante como logs fornecem valores infinitesimais na complexidade big-O ao usar classes de referência polinomiais