Realidade fantástica

Um ser humano adulto gasta algo como 100W apenas para manter-se dormindo (metabolismo basal). Esse número por si só já é impressionante, mas quando o comparamos ao sol é que algo surpreendente aparece.

O sol tem uma massa na ordem de 10³⁰kg e uma luminosidade na ordem de 10²⁶W. Isso significa que ele produz algo na redondeza de 10^-4W/kg, enquanto os seres humanos estão mais perto de 1W/Kg.

A conclusão simples é a de que um ser humano irradia cerca de 10 mil vezes mais calor que uma massa equivalente do sol irradia.

Para nos diferenciar dos outros seres vivos, criamos muitos objetos, utilizamos veículos, iluminamos as noites e aclimatamos nossas casas. De acordo com segunda lei da termodinâmica, os sistemas fechados tendem ao equilíbrio. Isto é, as diferenças de temperatura desaparecem e o sistema torna-se homogêneo com o tempo. A vida acelera esse processo e o ser humano o industrializa!

Para criar um pouco de ordem em nossos lares, exportamos muito caos para o meio-ambiente. E como há cada vez mais gente no planeta, há cada vez menos espaço para o caos que criamos. Se os pólos estão derretendo é porque o homem está cumprindo seu papel de quebrar os gradientes e homogeneizar a temperatura no sistema (mais ou menos) fechado que é a terra.

Só precisamos agora decidir se isso nos convém.

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.