Flashsort - Flashsort

Flashsort é um algoritmo de classificação de distribuição que mostra a complexidade computacional linear O ( n ) para conjuntos de dados uniformemente distribuídos e relativamente poucos requisitos de memória adicional. O trabalho original foi publicado em 1998 por Karl-Dietrich Neubert.

Conceito

Flashsort é uma implementação local eficiente de classificação de histograma , ela própria um tipo de classificação de bucket . Ele atribui cada um dos n elementos de entrada a um dos m baldes , reorganiza com eficiência a entrada para colocar os baldes na ordem correta e, a seguir, classifica cada balde. O algoritmo original classifica uma matriz de entrada A da seguinte maneira:

  1. Usando uma primeira passagem sobre a entrada ou conhecimento a priori , encontre as chaves de classificação mínima e máxima.
  2. Divida linearmente o intervalo [ A min , A max ] em m intervalos .
  3. Faça uma passagem sobre a entrada, contando o número de elementos A i que caem em cada segmento. (Neubert chama os buckets de "classes" e a atribuição de elementos a seus buckets de "classificação".)
  4. Converta as contagens de elementos em cada segmento em uma soma de prefixo , onde L b é o número de elementos A i no segmento b ou menos. ( L 0 = 0 e L m = n .)
  5. Reorganize a entrada para todos os elementos de cada intervalo b são armazenados nas posições A i onde L b −1 < i ≤ L b .
  6. Classifique cada intervalo usando a classificação por inserção .

As etapas 1–3 e 6 são comuns a qualquer classificação de bucket e podem ser aprimoradas usando técnicas genéricas para classificações de bucket. Em particular, o objetivo é que os intervalos sejam aproximadamente do mesmo tamanho ( n / m elementos cada), com o ideal sendo a divisão em m quantis . Embora o algoritmo básico seja uma classificação de interpolação linear , se a distribuição de entrada for conhecida como não uniforme, uma divisão não linear se aproximará mais desse ideal. Da mesma forma, a classificação final pode usar qualquer uma de várias técnicas, incluindo uma classificação flash recursiva.

O que distingue a classificação flash é a etapa 5: um algoritmo O ( n ) eficiente no local para coletar os elementos de cada balde juntos na ordem relativa correta usando apenas m palavras de memória adicional.

Implementação eficiente de memória

A fase de rearranjo Flashsort opera em ciclos . Os elementos começam como "não classificados", depois são movidos para o intervalo correto e considerados "classificados". O procedimento básico é escolher um elemento não classificado, encontrar seu intervalo correto, trocá-lo por um elemento não classificado lá (que deve existir, porque contamos o tamanho de cada intervalo com antecedência), marcá-lo como classificado e, em seguida, repetir com o elemento não classificado recém-trocado. Eventualmente, o elemento é trocado consigo mesmo e o ciclo termina.

Os detalhes são fáceis de entender usando duas variáveis ​​(do tamanho de uma palavra) por segmento. A parte inteligente é a eliminação de uma dessas variáveis, permitindo que o dobro de baldes sejam usados ​​e, portanto, metade do tempo gasto na classificação final de O ( n 2 ) .

Para entendê-lo com duas variáveis ​​por segmento, suponha que haja duas matrizes de m palavras adicionais: K b é o limite superior (fixo) do segmento b (e K 0 = 0 ), enquanto L b é um índice (móvel) no segmento b , então K b −1 ≤ L b ≤ K b .

Nós mantemos a invariante de loop de que cada segmento é dividido por L b em um prefixo não classificado ( A i para K b −1 < i ≤ L b ainda não foi movido para seus intervalos de destino) e um sufixo classificado ( A i para L b < i ≤ K b estão todos no intervalo correto e não serão movidos novamente). Inicialmente L b = K b e todos os elementos não são classificados. Conforme a classificação prossegue, os L b são decrementados até L b = K b −1 para todos b e todos os elementos são classificados no intervalo correto.

Cada rodada começa encontrando o primeiro segmento c classificado de forma incompleta (que tem K c −1 < L c ) e pegando o primeiro elemento não classificado nesse segmento A i, onde i = K c −1 + 1 . (Neubert chama isso de "líder do ciclo".) Copie A i para uma variável temporária t e repita:

  • Calcule o intervalo b ao qual t pertence.
  • Seja j = L b o local onde t será armazenado.
  • Troque t por A j , isto é, armazene t em A j enquanto busca o valor anterior A j deslocado.
  • Reduza L b para refletir o fato de que A j agora está classificado corretamente.
  • Se j ≠ i , reinicie este loop com o novo t .
  • Se j = i , esta rodada termina e encontre um novo primeiro elemento não classificado A i .
  • Quando não há mais elementos não classificados, a distribuição em intervalos é concluída.

Quando implementado com duas variáveis ​​por intervalo dessa maneira, a escolha do ponto de partida i de cada rodada é de fato arbitrária; qualquer elemento não classificado pode ser usado como um líder de ciclo. O único requisito é que os líderes de ciclo possam ser encontrados de forma eficiente.

Embora a descrição anterior use K para encontrar os líderes do ciclo, na verdade é possível fazer sem ele, permitindo que todo o array de palavras- m seja eliminado. (Depois que a distribuição for concluída, os limites do intervalo podem ser encontrados em L. )

Suponha que classificamos todos os elementos até i −1 e estamos considerando A i como um potencial novo líder de ciclo. É fácil calcular seu intervalo de destino b . Pela invariante do laço, é classificado se L b < i ≤ K b , e não classificado se i está fora dessa faixa. A primeira desigualdade é fácil de testar, mas a segunda parece exigir o valor K b .

Acontece que a hipótese de indução de que todos os elementos até i −1 são classificados implica que i ≤ K b , portanto, não é necessário testar a segunda desigualdade.

Considere o balde c em que a posição i cai. Ou seja, K c −1 < i ≤ K c . Pela hipótese de indução, todos os elementos abaixo de i , que inclui todos os intervalos até K c −1 < i , são completamente classificados. Ou seja, nenhum elemento que pertença a esses baldes permanece no resto da matriz. Portanto, não é possível que b < c .

O único caso restante é b ≥ c , o que implica K b ≥ K c ≥ i , QED

Incorporando isso, o algoritmo de distribuição flashsort começa com L conforme descrito acima ei = 1 . Em seguida, prossiga:

  • Se i > n , a distribuição está completa.
  • Dado A i , calcule o intervalo b ao qual ele pertence.
  • Se i ≤ L b , então A i não é classificado. Copie para uma variável temporária t e:
    • Seja j = L b o local onde t será armazenado.
    • Troque t por A j , isto é, armazene t em A j enquanto busca o valor anterior A j deslocado.
    • Reduza L b para refletir o fato de que A j agora está classificado corretamente.
    • Se j ≠ i , calcule o intervalo b ao qual t pertence e reinicie este loop (interno) com o novo t .
  • A i agora está classificado corretamente. Incremente ie reinicie o loop (externo).

Enquanto economiza memória, o Flashsort tem a desvantagem de recalcular o balde para muitos elementos já classificados. Isso já é feito duas vezes por elemento (uma vez durante a fase de contagem de intervalos e uma segunda vez ao mover cada elemento), mas a busca pelo primeiro elemento não classificado requer um terceiro cálculo para a maioria dos elementos. Isso pode ser caro se os intervalos forem atribuídos usando uma fórmula mais complexa do que a interpolação linear simples. Uma variante reduz o número de cálculos de quase 3 n para no máximo 2 n  +  m  - 1 , tomando o último elemento não classificado em um intervalo inacabado como líder do ciclo:

  • Mantenha uma variável c identificando o primeiro segmento classificado de forma incompleta. Deixe c = 1 para começar, e quando c > m , a distribuição está completa.
  • Seja i = L c . Se i = L c −1 , incremente c e reinicie este loop. ( L 0 = 0. )
  • Calcule o intervalo b ao qual A i pertence.
  • Se b < c , então L c = K c −1 e terminamos com o intervalo c . Incremente ce reinicie este loop.
  • Se b = c , a classificação é trivial. Decremente L c e reinicie este loop.
  • Se b > c , então A i não é classificado. Execute o mesmo loop de classificação do caso anterior e reinicie este loop.

A maioria dos elementos tem seus buckets computados apenas duas vezes, exceto para o elemento final em cada bucket, que é usado para detectar a conclusão do bucket seguinte. Uma pequena redução adicional pode ser alcançada mantendo uma contagem de elementos não classificados e parando quando chegar a zero.

Desempenho

Os únicos requisitos extras de memória são o vetor auxiliar L para armazenar os limites do balde e o número constante de outras variáveis ​​usadas. Além disso, cada elemento é movido (por meio de um buffer temporário, portanto, duas operações de movimentação) apenas uma vez. No entanto, essa eficiência de memória tem a desvantagem de que o array é acessado aleatoriamente, portanto, não se pode tirar proveito de um cache de dados menor do que o array inteiro.

Como acontece com todos os tipos de baldes, o desempenho depende criticamente do equilíbrio dos baldes. No caso ideal de um conjunto de dados balanceado, cada intervalo terá aproximadamente o mesmo tamanho. Se o número m de baldes for linear no tamanho de entrada n , cada balde tem um tamanho constante, portanto, classificar um único balde com um algoritmo O ( n 2 ) como classificação por inserção tem complexidade O (1 2 ) = O (1) . O tempo de execução das classificações de inserção finais é, portanto, m ⋅ O (1) = O ( m ) = O ( n ) .

Escolher um valor para m , o número de intervalos, troca o tempo gasto na classificação de elementos (alto m ) e o tempo gasto na etapa de classificação de inserção final (baixo m ). Por exemplo, se m é escolhido proporcional a √ n , então o tempo de execução das classificações de inserção final é, portanto, m ⋅ O ( √ n 2 ) = O ( n 3/2 ) .

Nos piores cenários, onde quase todos os elementos estão em alguns intervalos, a complexidade do algoritmo é limitada pelo desempenho do método de classificação de intervalo final, então degrada para O ( n 2 ) . As variações do algoritmo melhoram o desempenho do pior caso, usando classificações de melhor desempenho, como quicksort ou flashsort recursivo em intervalos que excedem um determinado limite de tamanho.

Para m = 0,1 n com dados aleatórios uniformemente distribuídos, o flashsort é mais rápido do que o heapsort para todos n e mais rápido do que o quicksort para n > 80 . Torna-se duas vezes mais rápido do que a classificação rápida em n = 10000 . Observe que essas medições foram feitas no final da década de 1990, quando as hierarquias de memória eram muito menos dependentes do cache.

Devido à permutação in situ que o flashsort realiza em seu processo de classificação, o flashsort não é estável . Se a estabilidade for necessária, é possível usar uma segunda matriz para que os elementos possam ser classificados sequencialmente. No entanto, neste caso, o algoritmo exigirá O ( n ) memória adicional.

Veja também

Referências

links externos