Décadas depois, a computação está cada vez mais perto de chegar ao número “perfeito” da organização de informação sequencialmente (em computação ou, para ser mais simples, numa biblioteca).
O “problema da ordenação de bibliotecas” (“Book-Sorting Algorithm”) ou, mais formalmente, o problema de “etiquetagem de listas”, foi apresentado pela primeira vez num artigo em 1981.
Tem a ver, precisamente, com organização. Imagine que tem todos os seus livros seguidos, na prateleira, organizados por autor, com um espaço no final. Se quiser introduzir um novo livro de Isabel Allende, não o vai colocar no final da prateleira, mas sim junto dos livros da autora.
Terá, então, de reorganizar a prateleira, abrindo um lugar para o novo livro no meio da fila, o que pode dar algum trabalho. Não seria preferível ter já os espaços em falta abertos? E como faria isso?
“É um problema muito importante”, não apenas para o bibliotecários, mas para a computação, garante Seth Pettie, cientista informático da Universidade de Michigan, porque muitas das estruturas de dados em que confiamos atualmente armazenam informação sequencialmente.
Uma forma comum de resolver este problema é perceber quanto tempo se demora a inserir um item individualmente, explica a Quanta Magazine. Naturalmente, isso depende do número de itens que existem, um valor tipicamente denotado por n. No exemplo de Isabel Allende, quando todos os livros têm de se mover para acomodar um novo, o tempo que demora é proporcional a n.
Os investigadores procuram saber se é possível conceber um algoritmo com um tempo médio de inserção muito inferior a n. Durante mais de quatro décadas, ninguém o conseguiu fazer. Em 2004, uma equipa descobriu que, para qualquer algoritmo suave ou determinístico, não é possível obter um tempo médio de inserção melhor do que (log n)2.
Mas, em 2022, Bender, Kuszmaul e quatro co-autores criaram um algoritmo “independente da história”, não-suave e aleatório — que finalmente reduziu o limite superior, baixando o tempo médio de inserção para (log n)1,5.
“É como se utilizasse a criptografia para tornar o seu algoritmo mais rápido”, disse Kuszmaul. “O que parece um pouco estranho”.
Bender, Kuszmaul e outros fizeram uma melhoria ainda maior com o trabalho do ano passado. Voltaram a bater o recorde, baixando o limite superior para (log n) vezes (log log n)3 – equivalente a (log n)1.000…1. Aproximaram-se, portanto, muito do limite teórico, o limite inferior último de log n.
“A forma de o tornarmos numa coisa boa foi sermos estrategicamente aleatórios quanto à quantidade de história a ter em conta quando tomamos as nossas decisões”, explicou Bender.
Agora, há novos desafios. “Sabemos que quase podemos fazer log n“, disse Bender, “mas ainda há uma pequena lacuna” – o diminuto termo log log n que se interpõe no caminho de uma solução completa. “Não sabemos se a coisa certa a fazer é baixar o limite superior ou aumentar o limite inferior”.
Segundo os investigadores, é muito mais provável que quaisquer melhorias futuras digam respeito ao limite superior, garnate Pettie, fazendo-o descer até log n. “Mas o mundo está cheio de surpresas estranhas.”
Em breve vamos ter um super-computador que em sete ai’s irá resolver isso