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.
Enjambrado por forinti às 14:09 3 comentários
Marcadores:

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.
Enjambrado por forinti às 07:04 0 comentários
Marcadores:

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.
Enjambrado por forinti às 09:56 0 comentários
Marcadores:

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.
Enjambrado por forinti às 14:55 1 comentários
Marcadores:
Assinar: Postagens (Atom)