Novo algoritmo de ordenação de livros alcança desempenho quase perfeito
(quantamagazine.org)- O problema da ordenação em bibliotecas influencia não só a organização de estantes, mas também o custo de armazenamento sequencial em discos rígidos e bancos de dados, e um novo estudo reduz o tempo médio de inserção para muito perto do limite teórico
- Um algoritmo de 1981 garantia tempo médio de inserção de ((log n)^2) de forma determinística e suave (smooth), mas por mais de 40 anos não surgiu um limite superior menor
- Estudos posteriores de limite inferior mostraram que o melhor possível para algoritmos gerais é (log n), enquanto o limite para algoritmos suaves e determinísticos é ((log n)^2), tornando necessária uma abordagem aleatória e não suave
- Em 2022, Bender, Kuszmaul e outros reduziram o limite superior para ((log n)^{1.5}) com um algoritmo aleatório independente do histórico (history independent), e o estudo mais recente alcança ((log n)(log log n)^3) ao usar também informações limitadas do passado
- A diferença restante está no termo (log log n), e esse avanço pode levar a melhorias de velocidade em aplicações como armazenamento e processamento de grafos dinâmicos baseados em rotulagem de listas
O que pergunta o problema da ordenação em bibliotecas
- O problema da ordenação em bibliotecas busca minimizar o tempo de movimentação necessário para inserir novos itens mantendo a ordem classificada
- Se os livros ficam concentrados em um lado, inserir um novo livro no meio pode exigir mover muitos outros livros
- Ao adicionar um livro de Isabel Allende, pode ser necessário deslocar toda a coleção
- Depois, ao adicionar um livro de Douglas Adams, o mesmo trabalho pode se repetir
- Distribuir espaços vazios de forma adequada por toda a estante reduz o custo de inserção, mas o ponto central é decidir onde e quanto espaço deixar
- Em termos mais formais, isso é chamado de problema de rotulagem de listas (list labeling), introduzido em um artigo de 1981
- O campo de aplicação vai além das estantes e se estende ao posicionamento de arquivos e itens em discos rígidos e bancos de dados
- O número de itens pode chegar a dezenas de bilhões
- Um arranjo ineficiente pode causar longos tempos de espera e alto custo computacional
Desempenho visto por limites superiores e inferiores
- O desempenho de uma disposição ordenada costuma ser avaliado pelo tempo necessário para inserir um novo item
- Se há (n) itens, e todos os livros precisam ser movidos, então o tempo de inserção é proporcional a (n)
- Isso pode ser visto como um limite superior para o tempo necessário para adicionar um novo item
- O artigo de 1981 perguntou se seria possível reduzir esse tempo médio de inserção para muito abaixo de (n) e apresentou um algoritmo que garante ((log n)^2)
- É um algoritmo determinístico que não depende de aleatoriedade
- Ele tem a propriedade suave (smooth), em que os itens precisam permanecer distribuídos uniformemente dentro do intervalo onde ocorrem inserções ou remoções
- Pesquisadores tentam reduzir a distância entre limite superior e limite inferior; quando os dois coincidem, o algoritmo é considerado ótimo
As restrições impostas pelos limites inferiores anteriores
- Um estudo de 2004 mostrou um limite inferior final: na versão mais geral do problema da ordenação em bibliotecas, nenhum algoritmo pode ser melhor que (log n)
- Em 1990, foi confirmado que o limite inferior para algoritmos suaves é ((log n)^2)
- Em 2012, surgiu um resultado mostrando que algoritmos determinísticos, sem uso de aleatoriedade, também têm o mesmo limite inferior ((log n)^2)
- Esses resultados significam que é difícil melhorar o limite superior de ((log n)^2) de 1981 usando apenas algoritmos suaves ou determinísticos
- Michael Bender concluiu que, para obter resultado melhor, seria necessário um algoritmo aleatório e não suave
- Uma abordagem não suave parecia intuitivamente arriscada, por não manter os itens espaçados de maneira uniforme
- Também não estava claro por que escolhas aleatórias ajudariam
2022: reduzindo o limite superior com independência do histórico
- Em 2022, Bender, William Kuszmaul e outros seis pesquisadores criaram um algoritmo independente do histórico, não suave e aleatório
- Um algoritmo independente do histórico não revela estados passados da estante
- Kuszmaul deu o exemplo de alguém retirar um livro da estante sem que outra pessoa consiga perceber que isso aconteceu
- Essa propriedade pode ser útil por razões de privacidade ou segurança
- Esse algoritmo reduziu pela primeira vez o limite superior de 1981, baixando o tempo médio de inserção para ((log n)^{1.5})
- Kuszmaul considerou surpreendente que uma ferramenta normalmente usada para privacidade pudesse tornar um algoritmo mais rápido
- Helen Xu, do Georgia Institute of Technology, avaliou que a ideia de usar independência do histórico por motivos além de segurança pode influenciar outros problemas
Pesquisa mais recente: combinando informação limitada do passado com aleatoriedade
- Em um artigo mais recente, Bender, Kuszmaul e outros voltaram a reduzir o limite superior e chegaram a ((log n)(log log n)^3)
- Esse valor corresponde a ((log n)^{1.000…1}), muito próximo do limite inferior final (log n)
- A nova abordagem também é não suave e aleatória, mas desta vez usa dependência limitada do histórico (history dependence)
- O algoritmo observa parcialmente tendências passadas para se preparar para inserções futuras
- Se entraram muitos livros de autores com sobrenome começando com N, como Nabokov, Neruda e Ng, ele deixa um pouco mais de espaço livre na região do N
- Mas reservar espaço demais pode causar problemas se começarem a entrar muitos livros de autores com sobrenome iniciado por A
- Bender explicou que tornou essa abordagem útil ao aleatorizar estrategicamente quanta informação do passado observar ao tomar decisões
- Seth Pettie avaliou que este estudo usa a aleatoriedade de uma forma completamente diferente da do artigo de 2022
A lacuna restante e as possibilidades de aplicação
- A lacuna restante está em um pequeno termo (log log n)
- Bender disse que ainda não sabe se o próximo passo é reduzir mais o limite superior ou elevar o limite inferior
- Pettie acredita que, quando a lacuna fica tão estreita e um dos limites parece natural enquanto o outro parece artificial, normalmente o lado natural acaba sendo a resposta certa
- Ele considera mais provável que futuras melhorias reduzam o limite superior até (log n)
- Ainda assim, acrescentou que “o mundo está cheio de surpresas estranhas”
- Brian Wheatman, da University of Chicago, vê esses artigos como um melhoramento considerável em termos teóricos, com grande potencial também nas aplicações
- Helen Xu disse que vinha se interessando recentemente por estruturas de dados baseadas em rotulagem de listas para armazenar e processar grafos dinâmicos, e que este avanço quase certamente os tornará mais rápidos
1 comentários
Opiniões do Hacker News
Também me surpreendeu a ideia de que “uma ferramenta usada para proteção de privacidade pode trazer outros benefícios”
Pensando bem, grande parte do desempenho não é literalmente uma questão de “executar mais instruções por hora”, mas sim de escolher um método que faça menos trabalho
Aqui, a propriedade de segurança chamada independência de histórico também significa “não é preciso rastrear o histórico e, literalmente, nem é possível fazê-lo”, então parece uma abordagem de desempenho interessante: usar a criptografia como restrição para impedir trabalho desnecessário
Pelo que entendi, é um modelo em que se pode gastar tempo de computação infinito
Por exemplo, se sabemos que uma lista está ordenada, podemos usar busca binária. Mas talvez escolher quanta informação omitir também possa ser essencial. Só que esses casos parecem menos frequentes, e não me vem à cabeça um exemplo simples de imediato
Fico me perguntando se fui o único a tentar encontrar os principais artigos explicados na matéria, ou seja, o artigo do problema original e o artigo do algoritmo quase ótimo [1], [2]
Ambos parecem estar linkados em algum ponto bem escondido do artigo, mas acho que seria muito útil para os leitores se a Quanta fosse obrigada a reunir todas as referências no fim da matéria
[1] Nearly Optimal List Labeling:
https://arxiv.org/abs/2405.00807
[2] A sparse table implementation of priority queues:
https://link.springer.com/chapter/10.1007/3-540-10843-2_34
Em “This problem was introduced in a 1981 paper”, “1981 paper” aponta para https://link.springer.com/chapter/10.1007/3-540-10843-2_34, e no parágrafo seguinte, em “Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers”, “a study” aponta para https://arxiv.org/abs/2405.00807
Os dois estão no terceiro e no quarto parágrafos da introdução, antes de entrar em detalhes, história e contexto. Se isso conta como “bem escondido no artigo”, então os critérios para bem escondido devem ser bem diferentes
Na semana passada eu estava justamente olhando para esse problema. Eu queria colocar itens de uma tabela de banco de dados em posições arbitrárias, mas, se possível, sem mexer no restante da lista
Por exemplo, se o usuário adiciona um novo elemento depois do item 5, esse elemento vira o 6, mas os itens que já estavam depois do 5 não são atualizados. De fato existem algoritmos muito sofisticados para gerenciar esse problema e minimizar os limites teóricos
Só que, nessa versão específica, parecia que a solução mais simples era usar índices fracionários e, de vez em quando, pagar o custo de reorganizar a lista
Basicamente, ele funciona bem quando o espaço de rótulos é grande em comparação com o número de itens. Quando não é, são necessários métodos mais sofisticados. Por exemplo, se você só tem 4 bytes para o rótulo e 1 bilhão de itens, isso vira um problema
Pelo que me lembro, a solução real era deixar espaços entre os elementos. Por exemplo, usar 0, 100, 200 em vez de 0, 1, 2, e reindexar quando necessário. Parece que funcionaria bem o suficiente
O que eu pensei foi indexação fracionária, como você disse, mas, para evitar o incômodo de lidar com decimais, dá para representar como um vetor e então expressar isso como uma string numérica ordenada lexicograficamente
Um elemento inserido entre 1 e 2 ganha o índice 11. Qualquer coisa entre 11 e 19 serviria. Entre 1 e 11 seria 101; entre 11 e 2 seria 12, e assim por diante. Mas esses índices não são números, são strings comparadas em ordem lexicográfica
Imagino que também haja desvantagens claras. Por exemplo, ordenar esses índices usaria muito mais memória, já que strings são bem maiores que números. Também parece inteligente demais para não ter algum problema inesperado
Na prática, essa limitação é bem restrita, mas, se você não está apenas atribuindo rótulos de ordem a uma coleção e sim tentando usar esses rótulos diretamente como índices de array para armazenar os elementos, a diferença realmente vira um problema. Esse é um modelo mais literal do problema de ordenação de biblioteca
Lembro que, alguns anos atrás, apresentei aos alunos um problema baseado no algoritmo Library Sort
O título do artigo original ainda está bem nítido para mim: “Insertion Sort is O(n log n)”
O título tem uma pegada bem caça-cliques
Fico curioso se há algum motivo para esse algoritmo ser realmente mais rápido do que os métodos usados hoje na prática
O lugar onde mais encontrei esse problema foi em arrays de nós de B-tree, e ali desconfio que seja mais rápido do que simplesmente usar
memmove(); se for um array realmente grande, parece mais fácil usar uma B-treeSendo assim, esse algoritmo também entra na categoria dos que são assintoticamente mais rápidos, mas, paradoxalmente, mais lentos do que os algoritmos usados na prática. Um exemplo são os algoritmos rápidos de multiplicação de matrizes, que são mais lentos do que uma boa implementação do algoritmo didático O(n^3) (GEMM)
O primeiro exemplo da página traz uma citação que explica bem sua utilidade
“Como exemplo de galactic algorithm, o método mais rápido conhecido para multiplicar dois números se baseia em uma transformada de Fourier em 1729 dimensões. Ele precisa apenas de O(n log n) operações de bits, mas, por causa da constante grande escondida na notação Big O, não é usado na prática. Ainda assim, isso mostra por que esses algoritmos podem ser úteis. Os autores dizem que ‘esperam que, com melhorias adicionais, ele se torne prático mesmo para números com bilhões ou trilhões de dígitos’”
A afirmação de que
reduz o limite superior para (log n) × (log log n)^3 — equivalente a (log n)^(1.000...1)é verdadeiraUma das coisas legais ao olhar para a complexidade Big O em famílias baseadas em critérios polinomiais é que logaritmos fornecem valores infinitesimais. É uma bela resposta para quem diz que “infinitesimais não existem de verdade”
Fiquei surpreso ao saber como a British Library gerencia milhões de livros e inúmeras novidades toda semana
O primeiro livro que chegou no começo deste ano foi colocado na posição 2025.0000001 da estante, e o seguinte foi colocado logo ao lado, em 2025.0000002. O restante fica por conta do catálogo eletrônico
Não é preciso reorganizar os livros, mas é uma solução que não combina com procurar livros olhando as prateleiras
Na verdade, eles evitam semelhanças de propósito para que o separador não pegue um item parecido, mas errado
Em casa, também esqueço com frequência onde guardei coisas que uso só de vez em quando. Tipo em qual armário e em qual caixa coloquei refis de lâminas de estilete x-acto. Como tento agrupar coisas parecidas, uma caixa acaba transbordando e outra fica meio vazia
Às vezes imagino que, se eu rastreasse todos os meus pertences em uma planilha e registrasse em qual caixa cada coisa está, eu não perderia nada e ainda usaria o espaço de armazenamento com máxima eficiência. Mas é óbvio que eu esqueceria de atualizar ao guardar algo novo, e isso parece um jeito estranhamente desumano, mais coisa de robô do que de gente
A animação no topo do artigo me deu vontade de criar um protetor de tela com ela
Estou tentando entender a restrição central. A definição do problema pressupõe um array pré-alocado de tamanho fixo?
insert(X),delete(X),label(X)labelretorna o rótulo do elemento X que foi inserido anteriormente e ainda não foi removido. O rótulo é um número de 0 a n-1, em que n é a quantidade de elementos armazenados no momento