Classificação LSD bit a bit (classificação Radix)

Recentemente, publiquei muitos artigos sobre vários algoritmos de classificação e sua comparação. Decidi fazer meus próprios cinco centavos.

Quero falar sobre o meu algoritmo favorito para classificar o LSD bit a bit (dígito menos significativo - primeiro o bit menos significativo) com a contagem (Classificação Radix). O algoritmo clássico foi repensado pelo autor para algumas otimizações em favor da aceleração e simplicidade.

Portanto, a classificação proposta é sustentável. Classificaremos os números inteiros de 32 bits. Para funcionar, você precisa de ~ (n + 4KB) de memória adicional, o que é um pouco inútil, mas permite obter algum aumento no desempenho.

Nesse tipo de LSD, comparações e trocas não são usadas, o algoritmo é completamente linear. Complexidade computacional O (N).

A principal característica do algoritmo é a alta eficiência para conjuntos de dados altamente misturados ou aleatórios. Em conjuntos quase ordenados, faz sentido usar outros algoritmos, pois o ganho não será tão significativo. Funciona mal em pequenas matrizes, menos de algumas centenas de elementos.

A classificação ocorre localmente para economizar memória.

//================================================== // RADIX  (  by rebuilder) //   ,  . //   (n),   ~(n+4k) //================================================== procedure RSort(var m: array of Longword); //-------------------------------------------------- procedure Sort_step(var source, dest, offset: array of Longword; const num: Byte); var i,temp : Longword; k : Byte; begin for i := High(source) downto 0 do begin temp := source[i]; k := temp SHR num; dec(offset[k]); dest[offset[k]] := temp; end; end; //-------------------------------------------------- //    ,     var s : array[0..3] of array[0..255] of Longword; i,k : longword; //     k offset : array[0..3] of byte absolute k; m_temp : array of Longword; begin SetLength(m_temp, Length(m)); //    FillChar(s[0], 256 * 4 * SizeOf(Longword), 0); //   for i := 0 to High(m) do begin k := m[i]; Inc(s[0,offset[0]]); Inc(s[1,offset[1]]); Inc(s[2,offset[2]]); Inc(s[3,offset[3]]); end; //     for i := 1 to 255 do begin Inc(s[0,i], s[0,i-1]); Inc(s[1,i], s[1,i-1]); Inc(s[2,i], s[2,i-1]); Inc(s[3,i], s[3,i-1]); end; //         Sort_step(m, m_temp, s[0], 0); Sort_step(m_temp, m, s[1], 8); Sort_step(m, m_temp, s[2], 16); Sort_step(m_temp, m, s[3], 24); SetLength(m_temp, 0); end; //================================================== ... SetLength(m, n); for i := 0 to n - 1 do m[i] := Random(65536 * 65536); ... RSort(m); ... 

O código está escrito em Pascal, mas não será difícil portá-lo para qualquer idioma conveniente para você.

A sequência de execução consiste em dois estágios:

1. Para cada bloco (oito dígitos binários - 1 byte (valor ótimo)), contando, sua posição em uma nova matriz é calculada.
2. Sequencialmente para cada bloco (do menos significativo para o mais alto), ele se move para a posição calculada anteriormente.

Melhorias:

1. Para uma série de compensações, usamos o alinhamento na memória e, devido ao pequeno volume, é colocado em L1 - o cache do processador.
2. A matriz de deslocamento é preenchida imediatamente para todos os dígitos, o que permite percorrer a matriz para contar apenas uma vez.
3. O cálculo da posição não começa no cabeçalho da matriz, mas no final, isso resolve dois problemas:
   
   • o final da matriz na primeira passagem já está no cache "aquecido", que com matrizes grandes fornece uma ligeira aceleração;
   • segundo, o ciclo descendente para zero é mais curto por uma instrução montadora, em cada etapa do ciclo, em relação ao ciclo ascendente.
4. Para cada iteração (em quatro), um loop aninhado não é usado, embora menos bonito, mas várias outras instruções do processador são salvas.

Devido à sua simplicidade, o código é quase idêntico em velocidade às compilações de compilador de 32 e 64 bits. Se necessário, é fácil imaginar uma versão do algoritmo para números de 16 e 64 bits.

Comparação do algoritmo de amostragem aleatória com classificação rápida em uma plataforma de 64 bits (em média, dez passes cada).



Sugestões e comentários sobre otimizações são bem-vindos.

Obrigada