sábado, 16 de abril de 2011

Power Sort em Java

Pesquisando uma maneira de ordenar números sem usar ifs, acabei tropeçando no Power Sort (e aqui e aqui).

Quando finalmente resolvi escrevê-lo em Java, percebi que era uma variação do Counting Sort. Com quase sete bilhões de pessoas na terra, é difícil ter uma idéia original. De qualquer forma, o Power Sort é um caso especial muito interessante do Counting Sort, porque:
  • Usa pouquíssima memória;
  • É ainda mais rápido e
  • Não precisa de ifs!
O Counting Sort usa um array enquanto o Power Sort usa uma ou duas variáveis numéricas. Por isso, o Power Sort fica restrito a conjuntos menores de dados (para não provocar um overflow).

O código abaixo é o de um Counting Sort muito simples. Ele não considera números negativos e faz a ordenação no mesmo array que recebe.


public class CountingSort {

  public static short[] sort(short[] in) {
    int[] order=new int[32768];
    for(int i=0;i<in.length;i++) {
      order[in[i]]++;
    }
    int index=0;
    int n=0;
    while(n<in.length) {
      while(order[index]==0) {
        index++;
      }
      for(int i=0; i<order[index]; i++) {
        in[n+i]=(short)index;
      }
      n+=order[index];
      index++;
    }
    return in;
  }

}

A idéia é simples. Os shorts positivos vão de 0 a 32767, então o array order representa quantas vezes cada número apareceu em in. Como o índice de order já representa a posição de cada número, só preciso copiar as casas maiores que zero de volta para o array original (as que tem zero representam números que não estão em in).

O interessante desse algorítmo é que ele só precisa olhar para os dados uma vez; ele não precisa de comparações; e tampouco faz trocas. O que ele produz é uma espécie de transformada dos dados.

E o desempenho é excelente. O gráfico abaixo mostra uma comparação com o Quick Sort (através do método Arrays.sort())



No eixo vertical estão os tempos em milissegundos e no eixo horizontal estão as quantidades de elementos ordenados. Testei de um em um milhão até quarenta milhões.

2 comentários:

Cassiano disse...

Mas que tal, bom esse algoritmo. Só queria saber porque este "ódio no coração" contra os ifs. Alguma coisa referente ao consumo do processador para resolver um if e, consequentemente, um programa com menos ifs é um programa mais verde? Me lembro que isso já vem desde época do Exit, resolvendo o cálculo de preços dos tipos de produto com o visitor pattern. Abraço

forinti disse...

Todos os bugs originam-se num if. Um if que falta ou um if errado. Logo, se eliminarmos os ifs, teremos menos bugs.

Além disso, ifs quebram os pipelines e, portanto, são menos eficientes e, consequentemente, menos verdes. Sim, progrmação ifless é programação sustentável!