segunda-feira, 27 de junho de 2011

Chocolate e Jurupiga

O chocolate é a bebida sagrada do Novo Mundo, enquanto a Jurupiga é o vinho vira-latas da Europa. São opostos que combinam muito bem. O álcool traz o otimismo para a criação e o amargo do chocolate ajuda na concetração. A combinação é divina. Com a ajuda deles, escrevi um pouco de Javascript para juntar dois mapas antípodas do Google Maps numa só tela. Quando se muda a posição ou a ampliação do mapa da esquerda, o da direita ajusta-se automaticamente para que seu centro seja o antípoda do centro do outro.


Infelizmente, o antípoda do Rio Grande do Sul está no meio do mar entre o Japão e a China. Por outro lado, esta deve ser a única região da Ásia tão despovoada quanto o Pampa.


<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="initial-scale=1.0, user-scalable=no" />
<style type="text/css">
  html { height: 100% }
  body { height: 100%; margin: 0px; padding: 0px }
  div { float: left }
</style>
<script type="text/javascript"
    src="http://maps.google.com/maps/api/js?sensor=true">
</script>
<script type="text/javascript">
  function init() {
    var lat=-29.683889;
    var lng=-53.806944;

    var here = new google.maps.Map(document.getElementById("here"),  { 
      zoom: 8, 
      center: new google.maps.LatLng(lat, lng),
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });

    var there = new google.maps.Map(document.getElementById("there"), { 
      zoom: 8, 
      center: new google.maps.LatLng(-lat, 180-Math.abs(lng)),
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });
    
    google.maps.event.addListener(here, 'zoom_changed', function() {
      there.setZoom(here.getZoom());
    });
    
    google.maps.event.addListener(here, 'center_changed', function() {
      var point=here.getCenter();
      var sign=point.lng()<0?1:-1;
      there.setCenter(new google.maps.LatLng(-point.lat(), 
        sign*(180-(Math.abs(point.lng())))));
    });
  }

</script>
</head>
<body onload="init()">
  <div id="here" style="width:400px; height:400px"></div>
  <div id="there" style="width:400px; height:400px"></div>
</body>
</html>

O código foi testado no Chrome, no Firefox e no IE. Em todos funciona, mas é no Chrome que ele roda mais rápido.

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.

quinta-feira, 16 de junho de 2011

Sleep Sort

Alguns algoritmos têm pouco valor prático, mas grande valor didático. Há poucas horas foi criado mais um destes (vale ouro presenciar o nascimento de um novo algoritmo de ordenação!): o Sleep Sort. Ele é tão novo, que não tem página na Wikipédia ainda.

O algoritmo é simples: para cada número x, deixam-se passar x unidades de tempo para adicioná-lo à lista ordenada. Quanto maior o valor de x, mais tempo ele precisará esperar e, portanto, mais para o fim da lista ficará posicionado.

Minha solução em Javascript é esta:

function sleepSort(n,callback) {
  var out=new Array();
  for(i in n) {
    var x=n[i];
    var pusher=function(x) {
      return function() { 
        out.push(x); 
        if(out.length==n.length) {
          callback(out);
        }
      };
    }(x);
    setTimeout(pusher, x*100);
  }
}
Como o método setTimeout() usa milissegundos como unidade, multiplico o valor de cada elemento por 100, para ter certeza que haverá tempo suficiente entre eles para não haver confusão.

Quando o último elemento for adicionado, a nova lista estará tão grande quanto a original e a função de callback será chamada. Dada a natureza do algoritmo, não é possível retornar imediatamente o resultado a partir de sleepSort().

O lado didático desse exercício é que ele ajuda a esclarecer como funcionam as closures do Javascript. Eu uso uma função que cria outra função, porque as closures têm referências às variáveis do contexto que as circunda. Logo, sem a função anônima intermediária, todas as chamadas usariam o último valor atribuído a x. Como a função intermediária recebe o x como parâmetro e os parâmetros são passados por cópia, o x da função mais aninhada é cópia e não referência do x original. Logo antes da chamada a setTimeout() está a chamada à função intermediária.

Segue um teste simples:

sleepSort([19,48,61,3,10,20,45,33],
  function(result) { 
    alert(result.join(",")); 
  }
);

Só falta nessa função uma maneira de tirar aquele if intrometido.

P.S. No dia 17/06/2011 surgiu uma entrada na Wikipédia sobre o Sleep Sort.

quarta-feira, 8 de junho de 2011

Transformando colunas em linhas

Um problema que de tempos em tempos surge é o de transformar colunas em linhas no SQL. Os bancos que têm facilidades de XML, como o DB2 e o Oracle, oferecem a possibilidade de resolver isso através do SQL/XML, que é uma extensão padronizada do SQL.

A consulta abaixo mostra como é simples usar essa extensão:


SELECT *
FROM XMLTABLE ('ROWSET/ROW/*' PASSING
     DBMS_XMLGEN.GETXMLTYPE('select 17,25,39 from dual') 
     COLUMNS val VARCHAR2(8) PATH '.'
) X

 17 
 25 
 39 

A rotina DBMS_XMLGEN.GETXMLTYPE recebe uma consulta e retorna um XML com a seguinte forma:


<ROWSET>
 <ROW>
  <_x0031_7>17</_x0031_7>
  <_x0032_5>25</_x0032_5>
  <_x0033_9>39</_x0033_9>
 </ROW>
</ROWSET>

Com XMLTABLE, realiza-se o caminho inverso. A expressão 'ROWSET/ROW/*' nos indica que queremos todos os nodos filhos de nodos do tipo ROW. Depois da chamada a DBMS_XMLGEN.GETXMLTYPE há uma descrição dos tipos para os quais as colunas devem ser convertidas.

O primeiro select retornava linhas de apenas uma coluna. Para extrair o nome de cada coluna, é preciso fazer o seguinte:


SELECT x.column_value.getrootelement(), x.column_value.extract('//./text()')
FROM XMLTABLE ('ROWSET/ROW/*' PASSING
     DBMS_XMLGEN.GETXMLTYPE('select 17 as A,25 as B,39 as C from dual')
) X

 A  17 
 B  25 
 C  39 

Essa consulta funciona no Oracle 10g. O DB2 e o Oracle 11g tem suporte melhor para o XPath e, portanto, permitem maiores estrepolias.

terça-feira, 31 de maio de 2011

A língua sabe de si

A língua está na boca dos gaúchos. Antes de discutirmos as dificuldades de viver sem estrangeirismos, havíamos sido atormentados pela polêmica dos livros escolares que ensinam que não é errado falar mal o português.

Nossa mídia nos confunde. Ora é ridículo traduzir estrangeirismos, ora é importante apontar o erro na língua alheia. Mas a confusão é mais antiga que essas duas discussões, alimentadas, sem dúvida, com o objetivo de vender mais escândalos.

Há décadas os jornais ignoram a ortografia. Os erros, há inúmeros deles todos os dias em todos os jornais (poucos jornalistas parecem saber que o verbo implicar é transitivo direto, por exemplo), mas o que realmente salta aos olhos são os nomes.

Segundo Marcos de Castro (no livro A Imprensa e o Caos na Ortografia), até o fim dos anos 1970, os jornais brasileiros respeitavam a língua portuguesa. Os nomes eram escritos como manda a regra. Ulisses e não Ulysses; Luís e não Luiz; Ademar e não Adhemar. Então, o general Golberi, afeito apenas a suas próprias regras, cismou que seu nome tinha que ser grafado conforme o equivocado progenitor o havia rabiscado: Golbery.

Desde então, a criatividade na grafia dos nomes próprios só tem aumentado. A cidade de Parati agora é Paraty e o Itamarati virou Itamaraty. Por sorte, o limite parece ser o teclado do escrivão; sem esse entrave, logo estaríamos sujeitos a símbolos, caracteres estrangeiros e logogramas asiáticos. Ai se descobrem o mapa de caracteres do Windows!

Há o seguinte parágrafo no polêmico livro "Por uma vida  melhor", do MEC:

'Os livro ilustrado mais interessante estão emprestado'. Você pode estar se perguntando: 'Mas eu posso falar ‘os livro?’.’ Claro que pode. Mas fique atento porque, dependendo da situação, você corre o risco de ser vítima de preconceito linguístico. Muita gente diz o que se deve e o que não se deve falar e escrever, tomando as regras estabelecidas para a norma culta como padrão de correção de todas as formas linguísticas. O falante, portanto, tem de ser capaz de usar a variante adequada da língua para cada ocasião

É prova inconteste da infiltração esquerdista no governo, porque, todos sabemos, não existe preconceito no Brasil. A imprensa, provado está, toma de braços abertos todas as formas de grafia. Com erros de concordância, não sei bem dizer o motivo, ela não tem tanta compreensão. Arrisco-me a conjecturar que a gravidade dos erros seja proporcional ao nivel sócio-econômico do errado. Eu devo ser comunista enrustido.

Antes mesmo dos jornais esquecerem essa história toda, um deputado comunista (a que ponto chegamos!) propõe que sejam traduzidos os estrangeirismos. A mídia regozijou-se. Um jornalista (provavelmente muito ocupado transcrevendo os textos da Reuters para procurar um dicionário) lançou uma lista de palavras únicas que, por sorte, seus leitores ajudaram a traduzir. O coitado não sabia como traduzir tsunami, mas logo apontaram para maremoto e vagalhão. Agora ele tem até escolha (parece que seu patrão não tinha muitas ao contratá-lo).

Então, vou propor umas adições ao livro do MEC. Sugiro o seguinte parágrafo:

Nos jornais, frequentemente encontramos erros como 'Ulysses Guimarães não estava presente no impeachment de Fernando Collor de Mello, porque havia morrido poucas semanas antes'. O correto seria 'Ulisses Guimarães não estava presente ao impedimento de Fernando Collor de Melo, porque havia morrido poucas semanas antes'. No entanto, não devemos mostrar preconceito contra trabalhadores que, tendo pouco tempo para preparar a edição do dia seguinte, não corrigem seus textos, mesmo com todas as facilidades oferecidas pelos computadores modernos.

Os erros do texto são meus e não da língua. Ela sabe de si e eu cuido de mim. Fernando Pessoa, que disso tudo entende muito mais que eu, mas que, tristeza nossa, está morto há muito tempo, escreveu e basta para terminar meu argumento:

Obedeça à gramática quem sabe pensar o que sente. Sirva-se dela quem sabe mandar nas suas expressões. Conta-se de Sigismundo, Rei de Roma, que tendo, num discurso público, cometido um erro de gramática, respondeu a quem dele lhe falou, "Sou Rei de Roma, e acima da gramática". E a história narra que ficou sendo conhecido nela como Sigismundo "super-grammaticam". Maravilhoso símbolo! Cada homem que sabe dizer o que diz é, em seu modo, Rei de Roma. O título não é mau, e a alma é ser-se.

sexta-feira, 20 de maio de 2011

Pérolas dos usuários IV

Os usuários são surpreendentemente criativos, não há dúvida. Com todos os anos de enfrentamento, eles ainda produzem feitos embasbacantes. A última, eu nunca esperaria acontecer.

Um usuário, quando deveria preencher o formulário e premir o botão "Enviar", imprimou-o vazio e o completou à mão. Creio que seja uma manifestação pós-moderna contra a intrusão das máquinhas nas relações interpessoais.

Por sorte, o CSS está aí para nos salvar. Com uma pequena adição à página, estão impedidos os usuários de imprimir o formulário.


@media print { body { display: none;} }

Fico em dúvida se não vou receber reclamações de que a impressão não está funcionando. Então, penso em adicionar algo como:


Calma! Nada deu errado. 
No entanto, o sistema detectou que tu não leste o manual.
Para podermos prosseguir, é necessário que leias as instruções cuidadosamente.

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.