Classificação da biblioteca

Pegue uma matriz de ordem inversa e aplique a classificação a ela com inserções simples .



Veja com que rangido o próximo elemento é inserido no lugar certo. Para isso, é necessário liberar o local de inserção, pelo qual é necessário mudar todos os elementos inseridos anteriormente.

E como seria bom se houvesse espaços vazios entre os elementos que foram inseridos anteriormente! Então não seria necessário arrastar as linhas de elementos apenas para inserir um.

Em 2004, três especialistas em ciência da computação - Michael Bender, Martin Farah-Colton e Miguel Mostiro - decidiram modificar a classificação com inserções simples dessa maneira. Eles sugeriram formar uma parte ordenada da matriz, deixando espaços entre os elementos inseridos.

O bibliotecário precisa que os livros sejam organizados em ordem alfabética em uma estante comprida: começando à esquerda da letra "A", os livros ficam um ao lado do outro no próprio "eu". Se a biblioteca recebeu um novo livro relacionado à seção "B", para colocá-lo na prateleira no lugar certo, você deve mover cada livro, começando em algum lugar do meio da seção "B" até o último "I". Esta é a classificação por inserções simples. No entanto, se o bibliotecário reservasse o espaço livre em cada seção, bastava mover apenas alguns livros para abrir espaço para novidades. Este é o princípio básico da classificação de bibliotecas.

Algoritmo

• 1. Crie uma matriz auxiliar vazia, várias vezes maior que a matriz principal.
• 2. Para o próximo elemento, procuramos o local de inserção na matriz auxiliar.
  • 2.1 Se você encontrar um local para inserir, transfira o item e retorne à etapa 2.
  • 2.2 Se não houver lugar para inserção, reequilibre a matriz auxiliar e retorne ao ponto 2.
• 3. Após processar todos os elementos, transfira-os de volta para a matriz principal.

À primeira vista, parece que a classificação é fácil e simples. Para dissipar essa ilusão, consideramos os pontos principais do algoritmo em mais detalhes.

Tamanho da matriz auxiliar

Embora não exista uma opinião estabelecida, quantas vezes a matriz auxiliar deve ser maior que a matriz principal.

Se você demorar demais, haverá muito espaço entre os elementos; no entanto, a pesquisa pelo site de inserção e o reequilíbrio serão mais lentos, devido às grandes distâncias entre os elementos. O reequilíbrio acontecerá com menos frequência, mas eles terão que gastar mais recursos com eles. Se você tomar muito pouco, a pesquisa e o reequilíbrio serão mais baratos, mas você precisará reformatar a matriz com mais frequência. Em geral, ainda precisa ser testado com valores diferentes e o método de cutucada científica determina a melhor opção.

Se decidirmos quantas vezes a matriz auxiliar é maior que a matriz principal, a fórmula para determinar o número exato de elementos para ela é assim:

NewSize = ε × (tamanho + 1) - 1

NewSize - o número de elementos na matriz auxiliar
ε - quantas vezes a matriz auxiliar é maior que a principal
Tamanho - o número de elementos na matriz principal

Se simplesmente multiplicarmos o tamanho por um fator: NewSize = Size × ε , para uma distribuição uniforme, não teremos células suficientes na quantidade de ε - 1 peças. Ou seja, é possível organizá-los uniformemente, mas a primeira célula preenchida ou a última estará localizada perto da borda da matriz auxiliar. E precisamos que os lugares vazios nas células preenchidas sejam reservados de todos os lados - inclusive antes do primeiro elemento e depois do último.



Parece um pouco, mas, de fato, é importante para o reequilíbrio garantir locais livres para inserção em qualquer lugar, inclusive ao processar os últimos elementos da matriz principal.

Procure o local de inserção na matriz auxiliar

Claro, aqui você precisa de uma pesquisa binária. No entanto, a implementação clássica não funcionará para nós.

Em primeiro lugar, a matriz auxiliar consiste principalmente em vazio. Portanto, dicotomizando recursivamente a estrutura, encontraremos na maioria das vezes células não preenchidas. Nesses casos, você precisa ir um pouco para a esquerda ou direita, para a célula não vazia mais próxima. No final do segmento, haverá elementos significativos que permitem calcular a média aritmética e continuar a pesquisa binária em profundidade.

Em segundo lugar, não se esqueça das bordas. Se você precisar inserir um elemento mínimo ou máximo, uma pesquisa binária entre os inseridos anteriormente não resultará em nada. Portanto, vale a pena considerar casos de fronteira - primeiro verifique se é necessário colocar um elemento próximo à borda esquerda ou direita da matriz e, se não, use a pesquisa binária.

Em terceiro lugar, levando em consideração as especificidades do aplicativo, vale a pena fazer alterações adicionais para minimizar o número de reequilíbrios de matriz. Se o elemento inserido for igual ao valor em uma das extremidades do segmento, talvez você não deva inseri-lo no meio do segmento. É mais lógico colocar ao lado de um elemento igual em valor a ele. Isso preencherá com mais eficiência o espaço vazio da matriz auxiliar.

Quarto, quinto e assim por diante. A qualidade da pesquisa para o local de inserção afeta diretamente a velocidade da classificação, pois a seleção de locais sem êxito para inserção leva a um reequilíbrio desnecessário. Por exemplo, pode valer a pena dividir os segmentos não exatamente no meio, mas mais perto da borda esquerda ou direita do segmento, dependendo de qual borda o elemento de inserção está mais próximo em valor?

O próprio algoritmo de busca binária está repleto de armadilhas e, levando em consideração as nuances adicionais acima mencionadas, ele finalmente se torna de modo algum uma tarefa não trivial.

Reequilíbrio de matriz

A pesquisa binária não é a coisa mais difícil de implementar nessa classificação. Ainda há reequilíbrio.

Quando não há lugar para inserção (elementos semelhantes foram encontrados, mas não houve células livres entre eles), você precisa agitar a matriz auxiliar para que o local de inserção seja liberado. Essa agitação da matriz está se reequilibrando.

Além disso, o reequilíbrio é local ou completo .

Rebalanceamento local

Mudamos quantos elementos forem necessários para liberar o ponto de inserção. A implementação desse balanceamento é muito simples, basta encontrar a célula vazia mais próxima do ponto de inserção e usá-la para mover vários elementos.

Existem possíveis nuances. Por exemplo, que maneira de procurar o lugar vago mais próximo? Para evitar a situação em que uma mudança é impossível (ou seja, se de algum lado todas as células estiverem ocupadas até a borda da matriz), você poderá se concentrar na posição do ponto de inserção em relação ao meio da matriz. Se você precisar inserir no lado esquerdo da matriz, mude para a direita, se estiver do lado direito - para a esquerda. Se ε ≥ 2, essa abordagem elimina a situação em que uma mudança é impossível (porque na metade da matriz auxiliar há espaço mais que suficiente para todos os elementos).

Na interpretação do autor do algoritmo, o reequilíbrio local está implícito.

Rebalanceamento completo

Uma alternativa interessante ao local é o reequilíbrio completo. Ou seja, na matriz auxiliar, altere todos os elementos disponíveis para que haja (quase) os mesmos espaços entre eles.



Tentei as duas opções e até agora estou observando que, com o reequilíbrio local, o algoritmo funciona de 1,5 a 2 vezes mais rápido que o completo. No entanto, um reequilíbrio completo ainda pode ser útil. Por exemplo, se você precisar fazer o reequilíbrio local com muita frequência, isso significa que, em algumas áreas, muitos “coágulos sanguíneos” se acumularam que inibem todo o processo. Um reequilíbrio completo realizado uma vez permite eliminar todo o congestionamento local de uma só vez.

Vamos descobrir como reequilibrar completamente.

Primeiro, você precisa calcular quantas células máximas podemos alocar para cada elemento na matriz auxiliar. Deve-se lembrar que as células vazias devem estar antes da primeira e depois da última célula preenchida. A fórmula é:



M - o número de células que podem ser alocadas para cada elemento
NewSize - tamanho da matriz auxiliar
Contagem - o número atual de elementos não vazios na matriz auxiliar

Essa fração deve ser reduzida para um valor inteiro (ou seja, arredondado para baixo). É óbvio pela fórmula que quanto mais elementos já forem transferidos para a matriz auxiliar, menos células podemos selecionar para a vizinhança de cada elemento.

Conhecendo M , obtemos facilmente a posição exata para cada elemento não vazio na matriz auxiliar na qual ele deve estar localizado após a conclusão do reequilíbrio.

NewPos = Número × M

NewPos - nova posição do item após o reequilíbrio
Number - qual é o elemento não vazio na matriz auxiliar (1 ≤ Number ≤ Count)
M - o número de células que são alocadas para cada elemento

Novas posições são conhecidas; você pode simplesmente separar elementos não vazios na matriz auxiliar e transferi-los para outros lugares? Oh não, não se apresse. Não é apenas necessário transferir elementos, é importante manter a ordem deles. E, como resultado da pesquisa e inserção binárias, os elementos podem ficar muito à esquerda e muito à direita da posição em que deveriam estar após o reequilíbrio. E no local em que você deseja mover, pode haver outro elemento que também precisa ser anexado em algum lugar. Além disso, você não pode transferir um elemento se houver outros elementos entre suas posições antiga e nova na matriz auxiliar - caso contrário, os elementos serão confundidos e é extremamente importante para nós não confundir a ordem.

Portanto, para reequilibrar, não será suficiente passar pelo ciclo usual e simplesmente mudar cada elemento de um bolso para outro. Ainda é necessário usar recursão. Se um elemento não puder ser movido para um novo local (outros elementos apareceram entre suas posições antiga e nova), primeiro você precisará descobrir (recursivamente) esses convidados não convidados. E então tudo será organizado corretamente.

Caso degenerado

Para a maioria das ordenações por inserções, uma matriz de ordem inversa é a pior situação. E classificar um bibliotecário, infelizmente, não é uma exceção.



Os elementos tendem para a borda esquerda da matriz auxiliar, como resultado dos pontos vazios rapidamente se esgotam. Você precisa reequilibrar a matriz com muita frequência.

A propósito, se pegarmos uma matriz quase ordenada (o melhor caso para classificar por inserções simples), obteremos o mesmo problema. Os elementos que chegam recentemente não obstruem a esquerda, mas o lado direito da matriz auxiliar, o que também levará a um reequilíbrio muito frequente.

A classificação da biblioteca lida com conjuntos de dados aleatórios com eficiência. A encomenda parcial (direta e reversa) prejudica o desempenho da velocidade.

Complexidade Algorítmica

Em grandes conjuntos de dados aleatórios, o algoritmo fornece a complexidade de tempo O ( n log n ). Nada mal!

Em conjuntos de dados únicos aleatórios (ou principalmente únicos) com a seleção correta do coeficiente ε e a implementação bem-sucedida da pesquisa binária, o número de reequilíbrios pode ser minimizado ou mesmo evitado. Pode-se argumentar que o algoritmo possui a melhor complexidade de tempo O ( n ).

Uma grande porcentagem de dados repetidos em valor, bem como a presença na matriz de subsequências ordenadas (em ordem direta ou reversa), leva a um reequilíbrio frequente da matriz auxiliar e, como resultado, à degradação da complexidade do tempo para O (n ² ) nos casos mais desfavoráveis.

O ponto negativo do algoritmo, é claro, é que a matriz auxiliar requer O ( n ) memória adicional.

Possíveis maneiras de melhorar

Embora o próprio algoritmo seja instrutivo e eficiente em dados aleatórios, em uma década e meia, poucos demonstraram interesse nele.

Se você pesquisar na solicitação "classificação da biblioteca", encontrará um artigo superficial na Wikipedia em inglês, o PDF do autor (do qual pouco se sabe) e uma rara reedição dessas informações escassas. Além disso, há uma boa visualização no YouTube, onde as matrizes principal e auxiliar foram originalmente combinadas. Todos os links estão no final do artigo.

A busca por “classificação da biblioteca” é ainda mais divertida - no exemplo, você encontrará as diferentes classificações incluídas em diferentes bibliotecas, no entanto, esses algoritmos não estarão relacionados à classificação autêntica da biblioteca .

E há algo a melhorar:

1. Seleção empírica do coeficiente ótimo ε .
2. Modificação (levando em consideração as especificidades do algoritmo geral) da pesquisa binária para a determinação mais eficiente do ponto de inserção.
3. Minimizando os custos de reequilíbrio.

Se você polir esses lugares, talvez a classificação da biblioteca em velocidade seja igual à classificação rápida?

Código fonte

Não consegui preparar a implementação em Python, existe uma versão funcional em PHP.








Eu tive que codificar do zero, com base em uma descrição geral do método. Não vi uma velocidade próxima à classificação rápida; minha opção de classificação da biblioteca é 10 a 20 vezes mais lenta que a classificação rápida. Mas a razão, é claro, é que minha implementação é muito grosseira, muito não foi levado em consideração.

Eu gostaria de ver uma versão dos criadores do algoritmo. Escreverei hoje para os autores (e colocarei um link para este habrastatu), eles responderão repentinamente. Embora ... eu lembrei, tentei entrar em contato com Allen Beachich ( classificação ABC ) e Jason Morrison ( classificação J ), mas o resultado foi o mesmo que se eu escrevesse no Sportloto.

UPD Martin Farah-Colton me respondeu que eles nunca fizeram a implementação:

Receio que nunca implementemos esses algoritmos.

A principal coisa é a idéia :)

Características do algoritmo

Referências

Classificação da biblioteca

Visualização do algoritmo de classificação da biblioteca

A classificação de inserção é O (n log n)

Autores do algoritmo:

Michael A. Bender
Martin Farah-Colton
Miguel Mostiro

Artigos da série:

• Aplicativo Excel AlgoLab.xlsm
• Classificações de Câmbio
• Classificações de inserção
  • Bibliotecário
  • Paciência Sort
  • Classificar "Torre de Hanói"
  • Classificação de mesa jovem
  • Inverter classificação
  • Inserir comparação de classificação
• Classificar por seleção
• Mesclar classificações
• Classificar por distribuição
• Classificação híbrida

Classificação adicionada ao AlgoLab. Assim, você pode experimentar com pequenos conjuntos de dados.

Nesse caso, você pode decidir quantas vezes a matriz auxiliar é maior que a matriz principal. Para selecionar o coeficiente ε, clique com o botão direito do mouse na célula com "Classificação da biblioteca" e selecione "Alterar nota". E na nota, defina cuidadosamente o valor inteiro para e de 2 a 5. Se você digitar outra coisa em vez desses números, o valor padrão = 2 será usado.

Você também pode selecionar o tipo de reequilíbrio. Se você definir local = 1, o reequilíbrio local será usado. Se local = 0 - cheio.

E não esqueça de definir a escala ideal para a planilha de processo antes de iniciar a visualização, caso contrário, a matriz auxiliar não caberá na tela.