Mostrando postagens com marcador Java. Mostrar todas as postagens
Mostrando postagens com marcador Java. Mostrar todas as postagens

quinta-feira, 4 de outubro de 2018

Extraindo a Versão de Vários Arquivos .class

Um erro "Bad version number in .class file" estava no meu caminho, então resolvi descobrir quais as diferentes versões de classes que estavam sendo usados.

A solução natural seria usar o executável javap, mas ele depende do classpath e aceita o nome de uma classe, não o nome de seu arquivo.

Felizmente, o Linux não nos deixa na mão em questão de manipulação de arquivos. O executável xxd permite extrair bytes quaisquer.

find /tmp -name *.class | xargs -I{} xxd -p -l4 -s4 {} | sort | uniq

Usei o find para encontrar todos os .class no diretório onde estavam. Depois o xargs usei para invocar o xxd com os seguintes parâmetros:
  • -p imprime o resultado de forma simplificada;
  • -l4 imprime quatro bytes;
  • -s4 inicia no byte 4 (quinto byte).
Finalmente, o sort | uniq elimina as repetições.
O resultado final foi:

00000031
00000032

E isso significa que há classes compiladas com java versão 5.0 e versão 6.0.

quinta-feira, 23 de outubro de 2014

Fatorial revisitado IV

Encontrei uma maneira ainda mais simples e rápida e de calcular um fatorial a partir dos primos que o compõem.

Para um fatorial n! é preciso
  1. Calcular, para cada primo p menor que n, a soma (s) das divisões de n pelas potências (q) de p menores que n;
  2. n! é a multiplicação de todos os ps.
Então, para 10!, teremos:
  • 2^(10/2 + 10/4 + 10/8) = 2^(5+2+1)=2^8
  • 3^(10/3 + 10/9) = 3^(3+1) = 3^4
  • 5^(10/5) = 5^2
  • 7^(10/7) = 7^1
Logo, n! = 2^8*3^4*5^2*7 = 3628800.

import java.math.BigInteger;

public class Factorial {

  public static BigInteger f(int n) {
    int m=n+1;
    int[] s=new int[m];
    for(int i=2; i<=m/2; i++) {
      if(s[i]!=-1) {
        //Marcar todos os múltiplos
        for(int p=i+i; p<m; p+=i) {
          s[p]=-1;
        }
        //Calcular soma de expoentes até a maior potência anterior a n
        for(int q=i; q<=n; q=q*i) {
          s[i]+=n/q;
        }
      }
    }
    BigInteger f=BigInteger.ONE;
    for(int k=2; k<m; k++) {
      int pk=s[k];
      if(pk>=0) {
        if(k>2) {
          System.out.print("*");
        }
        if(pk<2) {
          System.out.print(k);
          f=f.multiply(BigInteger.valueOf(k));
        } else {
          System.out.print(k+"^"+pk);
          f=f.multiply(BigInteger.valueOf(k).pow(pk));
        }
      }
    }
    return f;
  }
    
  public static void main(String... args) {
    for(int i=2; i<20; i++) {
      System.out.printf("%d! = ", i);
      BigInteger f1=f(i);
      System.out.printf(" = %d\n", f1);
    }
  }
 }
Se eu já tivesse uma lista de primos guardada, o código seria ainda mais simples.

quinta-feira, 29 de maio de 2014

Java e seus problemas

Os dois primeiros dos cinco objetivos iniciais da linguagem Java eram:
  1. Que a linguagem deve ser simples,orientada a objetos e familiar;
  2. Que seja robusta e segura.
A sintaxe inicial era, de fato, simples. Com o tempo foram adicionadas complicações, como os tipos genéricos. Por ser simples, robusta e segura, no entanto, a linguagem sempre foi prolixa.
Justamente pela quantidade de código necessária para executar as atividades mais simples, mesmo os mais ávidos programadores Java parecem não gostar de programar em Java. E então vemos uma grande quantidade de frameworks nos quais pode-se programar em XML e fazer muito pouco em Java. 
Então, jogam-se pela janela a robustez e a segurança para que se possa diminuir o número de linhas em Java. Aparentemente, o número de linhas em XML não tem relevância. Adoto a filosofia Lisp: não gosto de diferenciar configuração de programação. Se troco uma linha de código por dez de configuração, o sistema fica mais complexo.
As evoluções na sintaxe tratam de tornar a linguagem mais flexível, mas têm que conviver com o modelo antigo de execução. Java, entretanto, não foi criada para ser uma ferramenta de ponta. Ela foi criada para ser o novo COBOL. Por isso, ela deveria, creio eu, tentar manter a sintaxe simples, acessível, e legível. Surpreendentemente, coisas simples, como strings multilinhas e sintaxe para hashes, não foram adicionados à sintaxe ainda.
Parece-me que Java está tentando muito ser o que não é e está sofrendo por isso.

segunda-feira, 9 de dezembro de 2013

Fatorial revisitado III

Minhas tentativas anteriores de otimizar o cálculo dos fatoriais a partir de potências de números primos tinha evoluído até eu conseguir calcular o total dos expoentes de cada primo p entre potências consecutivas. Agora, consegui encontrar uma maneira de calcular todos os expoentes até uma potência qualquer.

Para um primo p, a soma dos expoentes de sua participação em cada múltiplo anterior ou igual a pn é

n+[(pn-p*n+n-1)/(p-1)]
= pn-1/p-1

Por exemplo, entre 2 e 8, temos os seguintes múltiplos de 2: 2, 4, 6, e 8. Anteriormente, teríamos que calcular os expoentes entre 2 e 4 e somá-los aos expoentes entre 4 e 8 e ainda somar os expoentes das potências (2, 4, e 8).

Agora, chegamos rapidamente ao resultado:

3+[(23-2*3+3-1)/(2-1)] = 3+[(8-6+3-1)/1] = 3+4 = 7
= 8-1/2-1
= 7

Conferindo os múltiplos de 2, confirmamos que
  • 2 = 21
  • 4 = 22
  • 6 = 21*3
  • 8 = 23
E assim, percebemos que a soma dos expoentes é, de fato, 7.

Alterei um pouco o código para exibir as respectivas fatorações.


import java.math.BigInteger;

public class Factorial {

  private static int in(int p, int i) {
    int n=0;
    while(i%p==0) {
      n++;
      i=i/p;
    }
    return n;
  }

  public static BigInteger f(int n) {
    int m=n+1;
    int[] p=new int[m];
    double logn=Math.log(n);
    for(int i=2; i<=m/2; i++) {
      if(p[i]!=-1) {
        //Marcar todos os múltiplos
        for(int j=i+i; j<m; j+=i) {
          p[j]=-1;
        }
        //Calcular soma de expoentes até a maior potência anterior a n
        int power=(int)(logn/Math.log(i));
        int k=(int)Math.pow(i, power);
        p[i]=(k-1)/(i-1);
        //Calcular os expoentes para os múltiplos que seguem a última potência
        for(int l=k+i; l<m; l+=i) {
          p[i]+=in(i, l);
        }
      }
    }
    BigInteger f=BigInteger.ONE;
    for(int k=2; k<m; k++) {
      int pk=p[k];
      if(pk>=0) {
        if(k>2) {
          System.out.print("*");
        }
        if(pk<2) {
          System.out.print(k);
          f=f.multiply(BigInteger.valueOf(k));
        } else {
          System.out.print(k+"^"+pk);
          f=f.multiply(BigInteger.valueOf(k).pow(pk));
        }
      }
    }
    return f;
  }
    
  public static void main(String... args) {
    for(int i=2; i<20; i++) {
      System.out.printf("%d! = ", i);
      BigInteger f1=f(i);
      System.out.printf(" = %d\n", f1);
    }
  }
 }

E isso produz o seguinte:

2! = 2 = 2
3! = 2*3 = 6
4! = 2^3*3 = 24
5! = 2^3*3*5 = 120
6! = 2^4*3^2*5 = 720
7! = 2^4*3^2*5*7 = 5040
8! = 2^7*3^2*5*7 = 40320
9! = 2^7*3^4*5*7 = 362880
10! = 2^8*3^4*5^2*7 = 3628800
11! = 2^8*3^4*5^2*7*11 = 39916800
12! = 2^10*3^5*5^2*7*11 = 479001600
13! = 2^10*3^5*5^2*7*11*13 = 6227020800
14! = 2^11*3^5*5^2*7^2*11*13 = 87178291200
15! = 2^11*3^6*5^3*7^2*11*13 = 1307674368000
16! = 2^15*3^6*5^3*7^2*11*13 = 20922789888000
17! = 2^15*3^6*5^3*7^2*11*13*17 = 355687428096000
18! = 2^16*3^8*5^3*7^2*11*13*17 = 6402373705728000
19! = 2^16*3^8*5^3*7^2*11*13*17*19 = 121645100408832000
É muito mais interessante que um fatorial recursivo simples, com if ou sem.

sexta-feira, 6 de dezembro de 2013

Fatorial revisitado II

Uma propriedade interessante dos números surgiu nas minhas investigações do fatorial. O número de vezes que um número divide seus múltiplos entre duas potências suas consecutivas é igual à primeira potência menos um mais o expoente dessa primeira potência. Bastante intuitivo, eu penso.

Entre 2n e 2n+1, por exemplo, temos os múltiplos 2n+2, 2n+4, 2n+6, e assim por diante. Cada um desses números pode ser dividido por uma potência de 2. E a soma dos expoentes é 2n-(1+n).

Tomemos outro exemplo com 5. Entre 51 e 52 temos os seguintes múltiplos de 5: 10 (2*5); 15 (3*5); e 20 (2*2*5). A soma dos expoentes de 5 é 3, que é igual a 5-2, ou, 5n-(1+n)=51-(1+1)=3.

Essa propriedade podemos usar para acelerar o cáculo do fatorial. Infelizmente, ainda precisamos manter o método anterior para calcular os expoentes de cada primo em cada múltiplo posterior à última potência anterior a n (quando estivermos calculando n!).

Então, o algoritmo ficou divido em 3 partes:
  1. Para cada primo, marcar seus múltiplos menores que n+1;
  2. Para cada potência de cada primo p, calcular pm-(1+m);
  3. Para os múltiplos de p superiores à última potência inferior a n, calcular os expoentes de p.
Em Java, montei o seguinte:

  private static int in(int p, int i) {
    int n=0;
    while(i%p==0) {
      n++;
      i=i/p;
    }
    return n;
  }

  public static BigInteger f(int n) {
    int m=n+1;
    int[] p=new int[m];
    for(int i=2; i<=m/2; i++) {
      if(p[i]!=-1) {
        //Marcar todos os múltiplos
        for(int j=i+i; j<m; j+=i) {
          p[j]=-1;
        }
        //Calcular os expoentes entre potências consecutivas
        int k=i;
        int power=1;
        for(; k*i<=m; k*=i) {
          p[i]+=k-power-1;
          p[i]+=power;
          power++;
        }
        //Calcular os expoentes para os múltiplos que seguem a última potência
        if(k<m) {
          p[i]+=power;
          for(int l=k+i; l<m; l+=i) {
            p[i]+=in(i, l);
          }
        }
      }
    }
    BigInteger f=BigInteger.ONE;
    for(int k=2; k<m; k++) {
      int pk=p[k];
      if(pk>=0) {
        if(pk==0) {
          f=f.multiply(BigInteger.valueOf(k));
        } else {
          f=f.multiply(BigInteger.valueOf(k).pow(pk));
        }
      }
    }
    return f;
  }
O mais surpreendente é que funciona.

quinta-feira, 5 de dezembro de 2013

Fatorial revisitado

Eu estava tendo dificuldades para criar um executável com um banco de dados embutido (com Tcl, SQLite e Freewrap), quando resolvi brincar um pouco com o Tcl. Escrevi uma pequena função para calcular fatoriais. Tcl permite gerar números bem grandes (como 1000!) com facilidade. Para tornar a coisa mais interessante, resolvi escrever uma versão sem if (abaixo).

proc fac {n} {
  set e 1;
  for {set x 2} {$x<=$n} {incr x} {
    append e "*$x"
  }
  puts $e
  return [expr $e]
}
A função simplesmente gera uma expressão (por exemplo, ela gera "2*3*4*5" para 5!) e depois calcula o resultado. Talvez inspirado pela recente releitura o livro Metamat! (de Gregory Chaitin), achei que seria interessante encontrar uma maneira de encolher essa expressão e assim tornar o programa mais curto e eficiente.

A solução mais próxima seria gerar um produto de primos, assim a multiplicação teria o menor número possível de multiplicandos. Não demorou muito para sair um algoritmo parecido com o Crivo de Eratóstenes. Se eu quiser calcular n!, faço o seguinte:
  1. Enumero todos os inteiros até n;
  2. Começando em 2, marco todos os múltiplos dos primos e anoto qual potência de cada primo divide cada múltiplo (e vou somando as potências);
  3. Ao fim, terei uma potência para cada primo e a multiplicação de cada um elevado à sua potência produzirá o fatorial.
Por exemplo, para 6!, os passos são:
  1. Começando em 2, descubro que 2=2^1, 4=2^2 e 6=2^1*3;
  2. Com 3, tenho 3=3^1 e 6=3^1*2;
  3. Quatro posso ignorar, porque já o visitei e anotei como inteiro composto;
  4. 5 não tem múltiplos menores ou iguais a 6, então anoto 5^1;
  5. Finalmente, 6 já sei que não é primo.
O resultado é 2^4*3^2*5 e isso produz 720, conforme esperado. Abaixo apresento uma solução em Java:

  private static int in(int p, int i) {
    int n=0;
    while(i%p==0) {
      n++;
      i=i/p;
    }
    return n;
  }

  public static BigInteger f(int n) {
    int m=n+1;
    int[] p=new int[m];
    for(int i=2; i<=m/2; i++) {
      if(p[i]!=-1) {
        p[i]=1;
        for(int j=i+i; j<m; j+=i) {
          if(j%i==0) {
            int v=in(i,j);
            p[i]+=v;
            p[j]=-1;
          }
        }
      }
    }
    BigInteger f=BigInteger.ONE;
    for(int k=2; k<m; k++) {
      int pk=p[k];
      if(pk>=0) {
        if(pk==0) {
          f=f.multiply(BigInteger.valueOf(k));
        } else {
          f=f.multiply(BigInteger.valueOf(k).pow(pk));
        }
      }
    }
    return f;
  }

Esse código tem uma pequena otimização. Ele percorre os primos apenas até n/2. Todos os primos acima disso só vão aparecer uma única vez no produto final (em 10!, por exemplo, 7 só aparece como 7^1). O array p começa com zeros. As posições ocupadas por primos vão recebendo as respectivas potências e as demais recebem -1. Ao fim, as posições de primos acima de n/2 vão continuar com 0 (porque não as visitamos), então a segunda parte da função (que faz as multiplicações para calcular o resultado final) ignora os valores menores que zero, troca os zeros por uns e usa os demais valores como os encontrar.

Comparando com uma função simples que multiplica instâncias de BigInteger de 2 até n, para valores pequenos, a diferença de tempo é insignificante. Em algum ponto entre 1000! e 2000!, a nova função passa a tomar um pouco mais que a metade do tempo. Ela é mais econômica em memória também.

O método f() retorna um BigInteger, mas imagino que em algumas situações possa ser mais útil guardar o produto de primos ou simplesmente imprimir a expressão.

sexta-feira, 1 de julho de 2011

Coundown Sort II

O Countdown Sort foi otimizado! Infelizmente, a melhoria custou um if adicional. Mesmo assim, como o algoritmo agora está quatro vezes mais rápido, acho que valeu a pena.

O algoritmo original percorria todo o array subtraindo 1 de cada elemento e anexando os que chegavam a 0 a um array ordenado. Evidentemente, não é preciso percorrer os elementos que já chegaram a 0, então resolvi tirá-los da jogada.


  public static short[] countdownSort(short in[]) {
    short[] order=new short[in.length];
    int index=0;
    short delta=0;
    int last=in.length-1;
    do {
      for(int i=last; i>=0; i--) {
        if(in[i]-delta==0) {
          order[index]=in[i];
          index++;
          if(i<last) {
            in[i]=in[last];
          }
          last--;
        }
      }
      delta++;
    } while(last>=0);
    return order;
  }

Agora, sempre que encontrar um 0, o algoritmo o troca pelo último elemento do array original e diminui em uma posição a abrangência da busca. Se justamente o último elemento é que chegou a 0, então basta subtrair 1 do índice que aponta para o fim do array (representado no código pela variável last).

Isso significa que o array original será destruído, mas, como o método retorna uma versão ordenada dos números, o problema não é grave.

Paira ainda no ar a dúvida sobre se algo realmente útil pode advir deste algoritmo.

segunda-feira, 20 de junho de 2011

Countdown Sort

Resolvi tentar melhorar o Sleep Sort contando alguma coisa diferente e mais rápida que o tempo. A minha primeira idéia foi contar números e usar os próprios elementos desordenados como medida. Então, cheguei ao Countdown Sort.

A idéia é muito simples: subtraio 1 de cada elemento e a ordenação ocorre naturalmente ao passo que os números forem alcançando o zero. O desempenho é terrível, mas o algoritmo é meu e está pago. Além disso, ele não faz nem comparações nem trocas de elementos e isso já é interessante por si só.

Eis o código em Java:

  public static short[] countdownSort(short in[]) {
    short[] order=new short[in.length];
    int index=0;
    short delta=0;
    do {
      for(int i=in.length-1; i>=0; i--) {
        if(in[i]-delta==0) {
          order[index]=in[i];
          index++;
        }
      }
      delta++;
    } while(index<in.length);
    return order;
  }
Um possibilidade interessante é a de implementá-lo em código de máquina, já que todas as CPUs têm instruções para subtrair 1 e comparar com 0. Parece-me que o código seria bem pequeno.

Um pequeno teste mostra que o algoritmo funciona mesmo com elementos repetidos:

  public static void main(String... args) {
    short[] ordered=countdownSort(new short[] {
       2, 40, 33, 1, 100, 4, 2, 0, 0, 1024
    });
    for(short v: ordered) {
      System.out.printf("%d,", v);
    }
  }

%java CountdownSort
0,0,1,2,2,4,33,40,100,1024,
Agora, tenho que achar uma maneira de acelerar a contagem.

quarta-feira, 18 de maio de 2011

Power Sort em Java II

Tendo percebido (e logo relevado) que Power Sort é um caso especial do Counting Sort, decidi continuar investindo neste ramo da tecnologia ifless.

Começando pelo caso mais simples (ordenar apenas números inteiros sem repetições), encontrei uma solução muito simples com a classe BigInteger.

public static void psort(int[] in) {
    BigInteger TWO=new BigInteger("2");
    BigInteger pp=BigInteger.ZERO;
    for(int i=0; i<in.length; i++) {
     pp=pp.add(TWO.pow(in[i]));
    }    
    
    for(int i=0; i<in.length; i++) {
     in[i]=pp.getLowestSetBit();
     pp=pp.flipBit(in[i]);
    }
}
O código funciona em duas etapas. Na primeira, o número pp recebe cada elemento do array in como uma potência de 2. Ou seja, pp+=2in[i]. Na segunda parte, a posição do i-ésimo bit indica o valor da i-ésima casa do array já ordenado. Como não há um método para percorrer os bits 1, uso o método flipBit() para negar o primeiro e fazer do próximo o primeiro.

O código abaixo mostra um teste com um pequeno array de 200 posições.

import java.math.BigInteger;

public class PowerSort {

  public static void psort(int[] in) {
    BigInteger TWO=new BigInteger("2");
    BigInteger pp=BigInteger.ZERO;
    for(int i=0; i<in.length; i++) {
     pp=pp.add(TWO.pow(in[i]));
    }    
    
    System.out.println(pp);
    
    for(int i=0; i<in.length; i++) {
     in[i]=pp.getLowestSetBit();
     pp=pp.flipBit(in[i]);
    }
  }
  
  public static void main(String... args) {
    int[] test=new int[200];
    for(int i=0;i<200;i++) {
      test[i]=200-i;
    }    
    psort(test);
    for(int i : test) {
      System.out.printf("%d ", i);
    }
    System.out.println();
  }

}
O array começa com os valores 200 a 1 e os ordena para a ordem crescente. O valor final de pp é o respeitável e impronunciável

3213876088517980551083924184682325205044405987565585670602750
Quanto maiores os números, tanto maior ficará pp e, portanto, mais memória será usada para executar a ordenação. Se os valores forem conhecidos de antemão, será muito mais econômico usar um mapa de bits.

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.

quarta-feira, 7 de julho de 2010

Zips exóticos em Java

A API do Java é enorme, mas ainda deixa alguns pontos importantes abertos. Apesar de ter facilidades para ler e escrever arquivos compactados, não suporta zips encriptados ou multi-volumes.

Por sorte, existe uma API para Java sobre o 7-zip. É preciso usar a API e as bibliotecas originais, então existe uma biblioteca para o Linux e outra para o Windows. Pode ser um pouco trabalhoso para quem desenvolve no Windows e usa o Linux para produção, como muitas vezes acontece.

Pois bem, a API é deveras estranha, então o melhor é conseguir um exemplo e reaproveitá-lo.

RandomAccessFile file=new RandomAccessFile(zip, "r");
ISevenZipInArchive zip=SevenZip.openInArchive(null,
new RandomAccessFileInStream(file));
ISimpleInArchive ui=zip.getSimpleInterface();
for(int i=0; i<zip.getNumberOfItems(); i++) {
final ByteArrayOutputStream stream=new ByteArrayOutputStream();
String nome=(String) zip.getProperty(i, PropID.PATH);
ISimpleInArchiveItem item=ui.getArchiveItem(i);
ExtractOperationResult result=item.extractSlow(new ISequentialOutStream() {
public int write(byte[] data) throws SevenZipException {
try {
stream.write(data);
} catch(Exception e) {

}
return data.length;
}
}, "senhasecreta");

O arquivo sendo analisado é o zip (uma referência do tipo File). Para cada arquivo dentro de zip, obtem-se um item (do tipo ISimpleInArchiveItem) e descompactam-se os dados originais usando o método extractSlow(). Esse método recebe uma instância de ISequentialOutStream que neste caso copia os dados para uma instância de ByteArrayOutputStream. O último parâmetro de extractSlow() é a senha, caso os dados estejam protegidos.

É muito útil, mas espero que a JDK logo ganhe novos métodos para suportar encriptação e multi-volumes. E com uma API mais elegante que esta!

terça-feira, 18 de maio de 2010

Formatação eficiente no Java

Uma das maiores fontes de erros e ineficiência que costumo encontrar em sistemas Web escritos em Java é o mau uso das classes de formatação da package java.text.

A documentação avisa que as classes não podem ser usadas concorrentemente. Mas quem lê a documentação? Outro problema é a instanciação excessiva. Tenho a impressão de que ela não ocorre por precaução, mas por indiferença.

Em sistemas Web, principalmente os de alto tráfego, alguns detalhes podem fazer muita diferença. Se instanciar um objeto não custa muito, removê-lo é muito demorado. Num teste simples, descobri que reutilizar uma instância é quatro vezes mais rápido que criar uma nova. E uma instância reutilizada não precisa ser recolhida pelo coletor de lixo.

A solução está na classe ThreadLocal do pacote java.lang. Nem é preciso importar a package! Para a formatação, costumo criar uma classe utilitária da seguinte forma:

import java.text.SimpleDateFormat;
import java.util.Date;

public class Formato {

private static final ThreadLocal formatoData =
new ThreadLocal() {
@Override
protected SimpleDateFormat initialValue() {
SimpleDateFormat df = new SimpleDateFormat("dd/MM/yyyy");
return df;
}
};

public static SimpleDateFormat getFormatoData() {
return formatoData.get();
}

public static Date data(String value) {
return getFormatoData().parse(value);
}

public static String data(Date value) {
return getFormatoData().format(value);
}

}

Uso nomes bem concisos para os métodos para tornar o código mais simples. O significado fica bastante claro pelo uso:

String hoje=Formato.data(new Date());

Assim, fica garantido que para cada linha de execução haverá apenas uma instância para cada formatação. E todas as operações são feitas usando essa mesma instância. Os servidores de aplicação costumam reaproveitar as threads e então, uma vez criado, cada objeto terá uma longa vida. Além disso, não tem sentido ter muitas linhas de execução por processador. Tipicamente, usam-se 4 ou 8. Se houver mais que isso, o processador vai ficar mais tempo trocando de contexto que fazendo algo útil.

Para executar outras transformações, basta adicionar subclasses de ThreadLocal e os respectivos métodos, conforme o exemplo. Será necessária uma instância para cada tipo de conversão.

quinta-feira, 13 de maio de 2010

Visitor sem accept()

O padrão Visitor é deveras útil, mas pode ser melhorado com um pouco de reflexão. O maior problema dele é que é preciso adicionar um método para cada classe a ser visitada. Geralmente o código não faz mais do que chamar o respectivo método visit() no Visitor. Com reflexão, pode-se eliminar esses métodos. Eliminar código é sempre bom!

Vamos começar pelas classes que serão visitadas.

class Circle { 
  public String toString() { 
    return "Circle"; 
  } 
}

class Square { 
  public String toString() { 
    return "Square"; 
  } 
}

class FunnySquare extends Square { 
  public String toString() { 
    return "FunnySquare"; 
  } 
}

class ReallyFunnySquare extends FunnySquare { 
  public String toString() { 
    return "ReallyFunnySquare"; 
  } 
}

Duas são subclasses de Square e para elas não vou criar métodos visit(). O Visitor com reflexão está no código abaixo.

class Visitor {
  
  private void visit(Circle c) { 
    System.out.printf( "I visited a Circle (%s)\n", c); 
  }
  
  private void visit(Square s) { 
    System.out.printf("I visited a Square (%s)\n", s);
  }

  public void visit(Object e) throws Exception {
    visit(e, e.getClass());
  }
   
  private void visit(Object e, Class c) throws Exception {
    try {
      Method m = getClass().getDeclaredMethod("visit", c);
      m.invoke(this, e);
    } catch(NoSuchMethodException nsme) {
      visit(e, c.getSuperclass());
    } catch(Exception ex) {
      throw ex;
    }
  }
}

O único método público é o visit(Object e). Ele usa uma versão privada que procura um método adequado para a classe do alvo e, se não achar, recursivamente procura métodos usando a superclasse do alvo.

O código abaixo executa um pequeno teste.

Circle c = new Circle();
Square s = new Square();
FunnySquare f = new FunnySquare();
ReallyFunnySquare r = new ReallyFunnySquare();

Visitor v=new Visitor();
for(Object o : new Object[] {
        new Circle(), new Square(), new FunnySquare(), new ReallyFunnySquare()
  }) {
    v.visit(o);
  }

E o resultado é:

I visited a Circle (Circle)
I visited a Square (Square)
I visited a Square (FunnySquare)
I visited a Square (ReallyFunnySquare)

Eu deixei apenas um método visit() público para evitar que o cliente use um método mais abrangente. Como o compilador escolhe o método conforme o tipo da referência e não o tipo do objeto, se for utilizada uma referência com tipo de uma superclasse da instância, perde-se a oportunidade de usar um método mais específico.

Um bônus nisso tudo é que não é preciso usar ifs.

quinta-feira, 21 de janeiro de 2010

Programação Incondicional V

Alguns ifs simples, como o exemplo abaixo, podem ser substituídos por expressões.

if(a<b){
x=c;
} else {
x=d;
}

Esse bloco pode ser trocado por ((((a-b) >> 31) & (c^d)) ^ d), que pressupõe que estejam sendo usados inteiros de 32 bits e que o shift seja com sinal (vale em Java e na maior parte dos Cs).

O que ele faz é relativamente simples:
  1. Subtrai b de a para produzir um número positivo se a for maior ou negativo se b for maior;
  2. Executa um shift de 31 posições para produzir 0 se o número for positivo ou -1 (0xFFFFFFFF) se for negativo;
  3. Executa um XOR de c com d e um AND do resultado com o valor do passo 2;
  4. O AND do último passo vai produzir 0 ou c XOR d;
  5. Se o valor do passo 4 for 0, o resultado final será d, porque 0 XOR d = d;
  6. Se o valor do passo 4 for c XOR d, o resultado final será c, porque c XOR d XOR d = c.

Isso pode ser usado para tirar ifs de recursões. As recursões sempre têm um if para determinar quando parar, como no exemplo abaixo:

public int fact(int n) {
if(n=1) {
return 1;
} else {
return n * fact(n-1);
}
}

O que se pode fazer nesse caso é escrever duas funções: uma sem recursão e uma com recursão. No exemplo abaixo, uso uma lista de funções e escolho qual usar conforme o valor de x.

public abstract class Factorial {

protected abstract int fact(int x);

private static class Factorial0 extends Factorial {
@Override
protected int fact(int x) {
return 1;
}
}

private static class FactorialN extends Factorial {
@Override
protected int fact(int x) {
return x*getFunc(x-1).fact(x-1);
}
}


private static Factorial[] funcs=new Factorial[] {
new Factorial0(), new FactorialN()
};

protected static Factorial getFunc(int x) {
return funcs[-1*(((1-x)>>31))];
}

public static int factorial(int x) {
return getFunc(x).fact(x);
}

public static void main(String... args) {
System.out.println(Factorial.factorial(Integer.parseInt(args[0])));
}

}

A expressão -1*(((1-x)>>31)) é uma versão simplificada da expressão original, porque só é preciso retornar 1 quando x>1 ou 0 se x<=1. A expressão (1-x)>>31 sempre retorna 0 ou -1, então a multiplicação por -1 transforma isso em 0 ou 1, que podemos usar para indexar a lista de funções.

É mais complicado, mas não tem ifs!

sexta-feira, 15 de janeiro de 2010

Programador tem que ser preguiçoso

Um bom programador tem que ser preguiçoso. A idéia não é minha, é do Larry Wall.

Eu concluo que a maior parte dos programadores de Java são péssimos. Eles adoram empilhar frameworks sobre frameworks e configurar tudo com milhares de linhas de XML.

Até os anúncios para Java são umas monstruosidades: é imprescindível conhecimento de JDK1.6, JPA, EJB3, RMI, Spring, Struts2, Eclipse, JUnit, Hibernate, OC4J, Groovy, Swing, Comet, XML, XSLT, XSD; desejável conhecimento de RUP, UML, CMM, ITIL; bônus para quem souber inglês.

E o que é pior: tem muitos que conhecem tudo isso e não hesitam em usar tudo em todos os projetos. Tem sistemas com mais frameworks que telas. E mais XML que Java.

Nunca teria surgido no mundo Java o que surgiu no Reino do Camelo: Perl Golf. O objetivo desse novo esporte é o de resolver um problema com o menor número de caracteres. A disputa começa com uma solução qualquer e a cada iteração uma solução menor tem que ser apresentada. A última e menor solução é a ganhadora.

Eu decidi praticar um pouco de Java Golf num projeto que herdei. Era uma monstruosidade com 700KB de Java e XML. Outros 700KB estavam na camada de apresentação. Era escrito com ADF (Oracle Application Development Foundation).

O resultado final foi 95KB de Java e XML, 228KB de apresentação e 20KB de PL/SQL. Não recorri a truques ou a frameworks mágicos. Só escrevi o que precisava ser escrito. Nem mais, nem menos.

Troquei tudo por Struts2 e Tiles, mesmo correndo o risco de ser acusado de falsa preguiça. Mas como eu vou ter que continuar mantendo o sistema, acho que garanti um futuro mais tranqüilo.

segunda-feira, 21 de dezembro de 2009

Programação Incondicional III

As linguagens orientadas a objetos trouxeram à programação uma forma muito eficiente de eliminar ifs: o polimorfismo.

A habilidade de tratar homogeneamente objetos de classes diferentes ajuda a eliminar código como este:

if(shape instanceof Circle) {
 drawCircle();
} else if(shape instanceof Square) {
 drawSquare();
}

A solução, evidentemente, é criar uma superclasse e colocar nela um método que as subclasses possam sobrescrever, sem que os clientes dessas classes tenham que se preocupar com qual método estão chamando. No seguinte exemplo, eu crio uma instância de Circle, mas uso uma referência a Shape (sua superclasse). Eu invoco draw() (que deve estar definido em Shape) e o método que vai ser invocado é o que está definido em Circle.

Shape s=new Circle();
s.draw();

Se eu tiver um array de Shape, posso invocar draw() em cada elemento, sem considerar qual método estou realmente invocando.

for(int i=0; i<shapes.length; i++) {
 shapes[i].draw();
}


No entanto, ainda há espaço para eliminar mais ifs! Uma característica da maior parte das linguagens orientadas a objetos é que o método invocado depende do tipo da referência usada, não do tipo do objeto. O seguinte exemplo ilustra bem o que quero dizer. Eu não tento invocar diretamente draw() em cada Shape, mas tento fazê-lo através de outro método draw() da própria classe Shape; eu poderia querer contar os tipos das instâncias ou tomar alguma outra ação.

import static java.lang.System.out;

public class Shape {

 private static int circles, squares;

 public void draw() {
  //
 }

 public static void draw(Shape s) {
  out.println("I drew a shape");
 }

 public static void draw(Circle s) {
  out.println("I drew a circle");
  circles++
 }

 public static void draw(Square s) {
  out.println("I drew a square");
  squares++;
 }

 public static void main(String... args) {
  Shape[] shapes=new Shape[] { new Circle(), new Square() };

  for(int i=0; i<shapes.length; i++) {
   draw(shapes[i]);
  }
 }

}

class Circle extends Shape {

 public void draw() {
  //
 }

}

class Square extends Shape {

 public void draw() {
  //
 }

}


No método main(), eu percorro um array do tipo Shape[] e invoco um método draw() para cada referência. Na classe Shape, há três métodos draw(); cada um recebe um tipo diferente de Shape. No entanto, como eu estou usando referências a Shape no laço, somente o método draw(Shape) é invocado.

Em algumas situações eu posso realmente desejar tomar uma ação diferente, conforme o tipo do objeto, não da referência. Nesse caso, eu estaria de volta a usar ifs e o operador instanceof.

Algumas poucas linguagens usam um tipo de invocação chamado double-dispatch. Nele, o tipo da referência não importa, mas sim o tipo do objeto. Em Java ou C#, não existe esse mecanismo, mas é possível emulá-lo com o padrão Visitor.

Então, vamos reescrever o exemplo acima. Vou criar um PaintVisitor e adicionar um método a Shape.

public class Shape {

 public void accept(PaintVisitor v) {
  visit(this);
 }

}

class Circle extends Shape {

 public void accept(PaintVisitor v) {
  v.visit(this);
 }

}

class Square extends Shape {

 public void accept(PaintVisitor v) {
  v.visit(this);
 }

}

class PaintVisitor {
 public void visit(Shape s) {
  out.println("I drew a shape");
 }

 public void visit(Circle c) {
  out.println("I drew a circle");
 }

 public void visit(Square s) {
  out.println("I drew a square");
 }

 public void draw(Shape s) {
  s.accept(this);
 }

}

Finalmente, eu posso reescrever aquele laço da seguinte maneira:

PaintVisitor visitor=new PaintVisitor();
for(int i=0; i<shapes.length; i++) {
 visitor.draw(shapes[i]);
}

E sem um if sequer!

Em algumas situações, o padrão Visitor pode ser realmente útil. Ao construir um editor de textos, eu descobri que era muito melhor separar o código de desenho dos objetos, porque era difícil dar o contexto necessário para cada objeto desenhar a si próprio. Um parágrafo, por exemplo, pode conter imagens e textos de diferentes tamanhos. Fazer cada elemento calcular sua posição e depois desenhar a si próprio, recursivamente, torna o código deveras complicado e extenso. A solução de criar um Visitor para calcular as posições e outro para desenhar o texto tornou o código muito menor e mais simples.

Quando for preciso percorrer uma estrutura de dados, vale a pena considerar o padrão Visitor.

quinta-feira, 17 de dezembro de 2009

Programação Incondicional

Não faltam metodologias, plataformas e tecnologias, mas resolvi criar mais uma filosofia de programação mesmo assim. A programação incondicional (ifless programming ou unconditional programming) não é um novo radicalismo. É apenas uma tentativa de reduzir bugs através do seu maior vetor: o if.

Todas as linguagens de programação possuem ifs (exceto Prolog). Parecem inevitáveis, mas, na maior parte dos casos, é possível eliminar muitos ifs sem dificuldades. Vou mostrar como.

Uma técnica muito simples (e talvez a mais antiga encarnação da programação incondicional) é o array de ponteiros para funções. É tão simples, que pode ser usada em Assembly, como um array de endereços.

Em C, posso declarar um array de funções que recebem dois ints e retornam int assim:

int (*p[4])(int x, int y);

Posso invocar qualquer uma das funções assim:

resultado=(*p[op]) (i, j);

E com isso evito a seguinte seqüência particulamente perniciosa de ifs:

if(op==0) {
resultado=somar(i, j);
} else if(op==1) {
resultado=subtrair(i, j);
} else if(op==2) {
resultado=dividir(i, j);
} else ...

Perl oferece uma das sintaxes mais simples para declarar estruturas de dados; posso declarar o array e as funções de uma só vez de maneira bastante compacta.

my @ops = (
sub { $_[0]+$_[1] },
sub { $_[0]-$_[1] },
sub { $_[0]/$_[1] },
sub { $_[0]*$_[1] },
);
my $resultado=$ops[2]->(3,2);

Java, infelizmente, não possui funções, mas elas podem ser simuladas com subclasses. Como no Perl, é possível criar as subclasses e o array ao mesmo tempo, mas a sintaxe é muito mais complicada.

Operador[] ops=new Operador[] {
new Operador() {
public int eval(int i, int j) {
return i+j;
}
},
new Operador() {
public int eval(int i, int j) {
return i-j;
}
},
//etc, etc, etc...
};
int resultado=ops[2].eval(3,2);

Usar um hash (array associativo) é só um caso especial dessa técnica. Nenhuma linguagem permite um exemplo tão compacto como Perl:

my %ops = (
'+' => sub { $_[0]+$_[1] },
'-' => sub { $_[0]-$_[1] },
'/' => sub { $_[0]/$_[1] },
'*' => sub { $_[0]*$_[1] },
);
my $resultado=$ops{'+'}->(3,2);

E esta foi a introdução à programação incondicional!

terça-feira, 15 de dezembro de 2009

Perlismos em Java II

No primeiro "Perlismos" eu criei uma classe para emular a função grep do Perl. Eu devia ter seguido melhor a sabedoria do camelo e usado a mesma ordem dos parâmetros, porque logo percebi que com varargs seria possível fazer algo ainda mais prático.

import java.util.*;

public class Grep {

  public static <T> List<T> grep(Grepping<T> mapping, List<T> in) {
    List<T> out=new ArrayList<T>();
    for(T t : in) {
      if(mapping.map(t)) {
       out.add(t);
      }
    }
    return out;
   }

  public static <T> List<T> grep(Grepping<T> mapping, T... in) {
    List<T> out=new ArrayList<T>();
    if(in!=null) {
      for(int i=0; i<in.length; i++) {
        if(mapping.map(in[i])) {
          out.add(in[i]);
        }
      }
    }
    return out;
  }
}

Com isso, posso fazer chamadas mesmo quando não tiver uma lista. Não gosto de arbitrariamente criar estruturas só para poder usar um método. Com vargars, a segunda versão de grep() pode receber uma seqüência qualquer de elementos, como no exemplo abaixo:

  mulheres=Grep.grep(PessoaGrepping.MULHERES,
              fulano, ciclana, beltrano, arlinda);

segunda-feira, 14 de dezembro de 2009

Perlismos em Java

Linguagens dinâmicas como Perl costumam ter algumas pequenas facilidades que reduzem significativamente a quantidade de código necessária para executar operações com strings, listas e hashes. É difícil ou impossível recriá-las em linguagens mais rígidas, como Java ou C.

Mesmo assim, acho que vale a pena investigar o que pode ser reaproveitado. Vou começar com grep e map, que são funções que processam listas. Grep é usado para selecionar itens de uma lista e map para mapear uma lista para outra.

Em Perl, grep recebe dois parâmetros: um bloco de código (ou uma expressão) e uma lista. Para cada elemento da lista, grep executa o bloco ou avalia a expressão. Se o resultado for verdadeiro, o elemento é adicionado à lista de saída. O exemplo abaixo é do manual do ActivePerl:

@foo=grep(!/^#/,@bar);# weed out comments

Este código mostra uma chamada a grep com uma expressão regular (seleciona linhas que não começam com #) e uma lista @bar.

Java, infelizmente, não tem funções propriamente ditas, então vai ser preciso escrever grep como um método estático:

import java.util.*;

public class Grep {

  public static <T> List<T> grep(List<T> in, Grepping<T> mapping) {
    List<T> out=new ArrayList<T>();
    for(T t : in) {
      if(mapping.map(t)) {
        out.add(t);
      }
    }
    return out;
  }
}

O código usa generics, então parece mais complicado do que é. Em poucas palavras, ela recebe uma lista de elementos do tipo T e um mapeamento para elementos desse mesmo tipo; ela retorna uma lista do mesmo tipo T.

A classe Grepping é bastante simples e já fornece um comportamento default (sempre retorna true):

public class Grepping<T> {

  public boolean map(T t) {
    return true;
  }
}

Suponha que seja preciso selecionar um grupo de pessoas, conforme a idade. Precisamos de uma classe para pessoas e outra para lista de pessoas.

public class Pessoa {

  private String nome;
  private int idade;
  private char sexo;

  public Pessoa(String nome, int idade, char sexo) {
    this.nome=nome;
    this.idade=idade;
    this.sexo;
  }

  public String nome() {
    return nome;
  }

  public int idade() {
    return idade;
  }

  public char getSexo() {
    return sexo;
  }

}

public class PessoaList extends ArrayList<Pessoa> {

}

Com isso, posso escrever um mapeamento por idade.

public class PessoaPorIdade extends Grepping<Pessoa> {

  private int limiar;

  public PessoaPorIdade(int limiar) {
    this.limiar=limiar;
  }

  public boolean map(Pessoa p) {
    return p.getIdade()>=limiar;
  }

}

Então, seu eu quiser selecionar todos os maiores de 18 anos, posso fazer o seguinte:

  maiores=Grep.grep(pessoas, new PessoasPorIdade(18));

Nas situações em que o mapeamento não precisa ser parametrizado, gosto de criar um membro estático assim:

public class PessoaGrepping {

  public static final Grepping<Pessoa> MULHERES=
    new Grepping<Pessoa>() {
      public boolean map(Pessoa p) {
        return p.getSexo()='F';
      }
    }

  public static final Grepping<Pessoa> HOMENS=
    new Grepping<Pessoa>() {
      public boolean map(Pessoa p) {
        return p.getSexo()='M';
      }
    }
}

Usar os mapeamentos é simples:

  mulheres=Grep.grep(pessoas, PessoaGrepping.MULHERES);

Para simular a função map, basta criar uma classe Mapping, que retorne uma instância de T no lugar de um booleano:

import java.util.*;

public class Map{

  public static <T> List<T> map(List<T> in, Mapping<T> mapping) {
    List<T> out=new ArrayList<T>();
    for(T t : in) {
      T r=mapping.map(t);
      if(r!=null) {
        out.add(r);
      }
    }
    return out;
  }
}

public class Mapping<T> {

  public T map(T t) {
    return t;
  }
}

O resultado não é tão simples como o que se pode escrever em Perl, mas já é um avanço. Quando Java tiver closures, certamente será possível escrever código ainda mais compacto para executar essas funções.

quarta-feira, 9 de dezembro de 2009

Invocando procedures com Java

Há uma tendência no mundo Java de exagerar no uso de frameworks. Não raramente, encontro sistemas que têm mais frameworks que telas, ou mais XML que Java. O Hibernate é dos piores infratores.

O problema de ter tanta configuração em XML é que ele sequer costuma diminuir a quantidade de código. Costuma haver, isso sim, uma troca. Troca-se Java por XML. Ou SQL por XML. Qual será a vantagem de trocar uma linguagem com tantos controles por algo que só é verificado em tempo de execução?

Pois, eu argumento que as consultas são melhor escritas em SQL e colocadas em procedures. E meu argumento principal é o de que isso torna muito mais fácil a vida do DBA. Estando as consultas em procedures e functions, ele pode facilmente encontrar e corrigir problemas de desempenho. Além disso, as consultas podem ser compartilhadas por diferentes sistemas; dados costumam viver mais que os sistemas que os utilizam (e raramente um banco de dados é usado por apenas uma aplicação).

Tendo tudo isso em mente, fiquei muito feliz quando Java finalmente adotou métodos com número variável de parâmetros (varargs) e autoboxing. Com a JDK 1.5, finalmente foi possível escrever uma interface realmente simples e direta para invocar procedures e functions. Para resolver um problema, é muito melhor criar uma boa abstração do que iludir-se com XML.

Considere as duas classes abstratas abaixo:

public abstract class Procedure {

public abstract void call(Object... args)
throws SQLException, IOException;
public abstract void close();

public String getString(int columnIndex) throws SQLException {
return getCallable().getString(columnIndex);
}

public String getString(String columnName) throws SQLException {
return getCallable().getString(columnName);
}

//demais gets omitidos
}

public abstract class Function {

public abstract Object call(Object... args) throws SQLException;
public abstract void close();

//gets omitidos
}

Eu não usei interfaces, porque os gets não dependem da implementação específica e, portanto, podem ser codificados na superclasse e aproveitadas na implementação para cada banco de dados.

O que eu almejei foi poder escrever algo como:

Procedure p=null;
try {
//BUSCAR_PESSOA_PROC(
// P_CODIGO IN NUMBER,
// P_CURSOR OUT SYS_REFCURSOR
//);
p=new OracleProcedure("java:comp/env/jdbc/data",
"PESSOAS_PKG.BUSCAR_PESSOA_PROC");
p.call(123, null);
ResultSet rs=p.getCursor(1);
while(rs.next()) {
//percorrer cursor
}
} catch(Exception e) {
e.printStackTrace();
} finally {
p.close();
}

O construtor de OracleProcedure recebe dois parâmetros:

  1. O nome de uma datasource;
  2. O nome de uma procedure (com ou sem package);

Para o método call(), passo os parâmetros exigidos pela procedure. Como o segundo parâmetro é de saída (OUT), uso null naquela posição. As instâncias de Procedure e Function têm todos os gets de java.sql.CallableStatement, de tal sorte que é possível pegar os parâmetros de saída sem dificuldades.

Na primeira vez que uma procedure é invocada, OracleProcedure (OracleFunction faz o mesmo) recupera os metadados (tipos dos parâmetros) e os guarda num Map, para não ter que repetir esse passo. Em seguida, o código monta a consulta (neste caso, "{call PESSOAS_PKG.BUSCAR_PESSOA_PROC(?,?)}") e também a guarda. Um CallableStatement é criado, os parâmetros são atribuídos (é fácil escolher o setXXX() adequado com base no tipo do parâmetro) e a consulta, finalmente, é executada.

Nas primeiras versões dessas classes, eu também guardava a referência à datasource, para evitar ter que fazer outra pesquisa JNDI. Desisti de fazer isso porque as implementações do JNDI já são rápidas o suficiente para tornar a economia de tempo desprezível. Além disso, era impossível alterar ou reiniciar a datasource sem reiniciar a aplicação.

Com isso, tenho uma maneira simples de invocar procedures e functions. As camadas em Java ficam bastante mais simples e livres de XML. O código de acesso a dados fica restrito ao banco e pode ser compartilhado com outras aplicações.