Apresentando dados de experimentos com algoritmos

Novembro 26, 2010

Recentemente li os artigos de Peter Sanders [1] e David Johnson [2] sobre como apresentar dados de trabalhos experimentais. Mais especificamente, como escolher as medidas adequadas e como mostrar uma grande quantidade de dados de maneira compacta.

Selecionei algumas das dicas que achei mais interessantes e vou descrevê-las brevemente. Para uma lista completa, consulte [1, 2].

Tabelas

Tabelas são uma forma detalhada de apresentar dados, mas não são compactas. Por isso, uma regra de outro mencionada no artigo é de “Usar tabelas somente se o número de instâncias menor do que 20”.

Uma outra razão usar tabelas em detrimento de gráficos é quando não é possível organizar as instâncias ao longo de um eixo, como por exemplo em um experimento onde se quer exibir o tempo de execução de instâncias, mas não é possível apontar uma característica delas que influencie essa medida.

No caso em que é possível usar gráficos mas o número de instâncias é demasiado grande, é sugerida uma abordagem híbrida: tabelas para os dados mais importantes e gráficos para resultados mais gerais. Além do mais, tabelas completas podem ser colocadas no apêndice ou ainda em uma página web, para os interessados.

Gráficos

Em geral a largura do gráfico é limitada por causa da página, mas há certa liberdade na escolha da altura. Com isso, é possível escolher a proporção altura vs. largura. Isso influencia a inclinação das curvas. Uma regra é que a média das inclinações seja 45 graus.

Uma opção mais simples e comumente adotada é fazer largura/altura igual à razão áurea.

Escolher a escala dos eixos também é importante para aumentar a legibilidade. Em [2], é apresentada a seguinte tabela de tempos de execução para vários algoritmos contra diversas instâncias:


Tabela com dados artificiais, extraída de [2] (clique para ampliar)

Cada linha representa um algoritmo e as colunas representam as instâncias, organizadas por tamanho. São apresentados 4 possíveis gráficos para exibir esses dados:


Gráficos de dados artificiais, extraída de [2] (clique para ampliar)

No gráfico do topo à esquerda, os dados são plotados em escala linear. É ruim pois o intervalo entre 0 e 10.000, que compreende 5 colunas da tabela, está visualmente condensado na primeira divisão do eixo x.

No gráfico do topo à direita, usa-se uma escala logarítmica para distribuir melhor as colunas da tabela, porém ainda há o problema de que as três curvas de baixo estão praticamente coincidentes

No gráfico de baixo à esquerda, tenta-se contornar esse problema usando escala logarítmica no eixo y também. Agora os dados ficaram bem melhor distribuidos pela área do gráfico, mas parecem linhas paralelas, ficando difícil distinguir valores.

A sacada fica por conta do último gráfico: percebeu-se que o comportamento das curvas que ficaram quase coincidentes nos gráficos do topo, têm comportamento próximo a ‘n log(n)’. Portanto, dividiu-se todas as curvas por esse valor. O gráfico obtido ficou bem mais informativo no sentido de comparar os tempos de execução de cada algoritmo, além de ficar visualmente claro que os três algoritmo mais eficientes têm comportamento O(n log n).

Múltiplas curvas no mesmo gráfico

Quando as curvas são bem comportadas, tendo poucos pontos de interseção entre si, é possível plotar até 7 curvas no mesmo gráfico. A partir disso, tende a ficar poluído. Por outro lado, se houver um grande número de interseções, esse máximo fica limitado a 3 curvas.

Para colocar a legenda das curvas, use a mesma ordem em que aparecem na vertical, por exemplo para um valor de x alto, conforme a figura abaixo.


Comparação entre três diferentes algoritmos de fila de prioridade. Extraído de [1].

A figura anterior exemplifica outra boa prática: conectar pontos da mesma curva com retas. Além disso cada ponto deve ser um símbolo diferente, assim como cada linha. Se for possível, usar cores diferentes.

Organizando instâncias

Se o gráfico é sobre o tempo de execução para algumas instâncias, pode ser interessante usar um gráfico de barras. Esse exemplo foi usado na tese do Marcelo, sobre a qual falei em outro post, e que copio abaixo.

Tempos de execução do algoritmo de branch-and-bound com diferentes estratégias, trabalho do Marcelo Couto [3]

Quando houver um número maior de intâncias, um gráfico de barras ficará muito espaçoso. Uma alternativa é utilizar um gráfico de dispersão, plotando cada instância como se fosse um ponto. Nesse caso, o eixo x poderia ser uma característica numérica dessa instância, como por exemplo o tamanho, enquanto y exibe a grandeza medida.

Referência

[1] Peter Sanders – Presenting Data From Experiments in Algorithms
[2] David S. Johnson – A Theoretician’s Guide to the Experimental Analysis of Algorithms
[3] M. C. Couto, P. J. de Rezende e C. C. de Souza – An Exact Algorithm for an Art Gallery Problem

Anúncios

Ponto dentro de polígono

Novembro 19, 2010

Recentemente precisei implementar um algoritmo que detecta se um dado ponto está dentro ou fora de um polígono simples.

Para o caso especial em que o polígono é convexo, existe um algoritmo que faz a consulta em . Uma descrição do algoritmo e um exemplo de execução podem ser encontrados na minha página pessoal.

Para o caso geral, existe um algoritmo O(n) que é bem diferente daquele do caso convexo, mas igualmente simples e engenhoso.

Problema: Decidir se o ponto está dentro ou fora do polígono.

A ideia é a seguinte: traçamos uma semi-reta a partir do ponto de consulta até o infinito, em uma direção arbitrária, e contamos quantas vezes ela cruzou a borda do polígono. Desconsiderando casos especiais, o polígono estará dentro se e somente se, o número de cruzamentos for ímpar.

O algoritmo é simples de descrever, mas como boa parte de algoritmos geométricos, a parte difícil está em implementar. Para contar o número de cruzamentos, processamos cada segmento do polígono. Supondo que o polígono P é dado por uma lista de pontos em sentido horário (se estiver em sentido anti-horário basta inverter a lista). Assim, um segmento é dado por um par de pontos , incluindo o par . Vamos supor também que um dado ponto p possui coordenadas . Sem perda de generalidade, também consideramos que a semi-reta está na direção horizontal e se estende para a direita (tal qual a Figura 1).

Uma condição necessária para que a semi-reta do ponto p intercepte um segmento qualquer (a, b), é de que p esteja verticalmente entre a e b, ou seja, supondo que , então

(1) .

Figura 1: Para a semi-reta cruzar o segmento, o ponto deve estar verticalmente entre seus extremos.

Porém, como se trata de uma semi-reta com sentido para a direita, queremos considerar apenas os segmentos “à direita” do ponto. Vemos pela Figura 2, que não basta verificar se o ponto p está à esquerda do ponto mais a esquerda do segmento. Para decidir de qual “lado” do segmento está um ponto, podemos usar produto vetorial.

Figura 2: Não basta verificar se o ponto p está à esquerda do ponto mais a esquerda do segmento

Dados dois vetores e , podemos decidir a orientação entre eles através de um produto vetorial . Dependendo do sentido do vetor resultante, é possível dizer se possui orientação horária ou anti-horária em relação a .

Com os três pontos p, a e b, podemos obter os vetores e e usar a ideia do produto vetorial para decidir a orientação de p em relação ao segmento ab. Mais especificamente, podemos usar a seguinte equação [1]:

Se , então o vetor está orientado em sentido anti-horário em relação ao vetor . Se a orientação é horária e se , os vetores são paralelos.

Figura 3: Valor de r e a correspondência geométrica.

Casos especiais

Há dois casos especiais que devemos tratar: o caso em que está na borda do polígono e o caso em que o raio cruza um segmento no seu extremo. Vamos analisar o segundo caso. A figura abaixo elenca todos os possíveis casos.

Figura 4: Casos especiais.

A presença dos casos (a), (b), (d) e (e), não muda de que “lado” do polígono o ponto está, ao contrário dos casos (c) e (f). Assim, as interseções do raio com (a), (b), (d) e (e), não devem mudar a paridade do número de cruzamentos, enquanto as interseções com (c) e (f) sim. Note porém, que no algoritmo apresentado, (d) e (e) aumentarão o número de cruzamentos em 3 (mudando a paridade dos cruzamentos) e (c) aumentará em 2 (mantendo a paridade dos cruzamentos).

Uma maneira bem elegante de se tratar tais casos, é considerar que o raio só intercepta segmentos cujo extremo inferior esteja estritamente abaixo de p e com extremo superior acima ou na mesma altura de p. Ou seja, a equação (1) fica,

(2) .

Agora, o número de cruzamentos com os casos (a) e (d) é 0; com (b) e (e) é 2; e com (c) e (f) é 1, preservando a paridade como gostaríamos.

Finalmente, vamos tratar o caso em que o ponto esteja na borda do polígono. Uma condição necessária, mas não suficiente, é que o ponto p seja colinear a algum dos segmentos do polígono. Além disso, é preciso que p esteja entre os pontos de tal segmento.

Uma vez que sabemos que p é colinear ao segmento , podemos determinar se ele está no meio de a e b através de um produto escalar!

Lembre que o produto escalar entre dois vetores e é equivalente a:

onde é o ângulo entre e .

Podemos definir os vetores e e calcular o produto escalar entre eles. Por hipótese, esses vetores são paralelos. Se p estiver entre a e b, e têm sentido oposto, o ângulo entre eles é . Caso contrário, têm mesmo sentido e o ângulo é 0.

Figura 5: Possíveis orientações entre a, b e p colineares.

Observando que o módulo é sempre positivo e e , concluimos que p está entre a e b se e somente se . Há o caso em que p é coincidente com a ou b. Nesse caso o produto escalar é 0. Resumindo, p está na borda do polígono se existe segmento tal que

Pseudo-código

O pseudo-código abaixo recebe como parâmetros um ponto p e um polígono P, conforme especificado anteriormente, e decide se o ponto está dentro, fora ou na borda do polígono.

Aplicação

Estou desenvolvendo um aplicativo web usando Google Maps onde o usuário define um polígono simples e apenas cidades dentro da região delimitada são consideradas. O algoritmo verifica, para cada cidade, se o ponto correspondente ao centro dela está dentro do polígono definido.

Figura 6: Interface do aplicativo

São necessárias algumas projeções, pois as coordenadas estão em latitude-longitude e o polígono é construído com coordenadas cartesianas,  mas essencialmente o algoritmo usado é o de detecção de ponto
dentro de polígono.

Referências

[1] Wikipedia – Cross Product


Hooligan

Novembro 12, 2010

Na final brasileira da maratona de programação de 2009, caiu um problema relacionado a futebol, chamado Hooligan, cujo enunciado pode ser acessado aqui.

Vou tentar resumi-lo. Temos um campeonato onde todos os times se enfrentam exatamente k vezes. Em um campeonato por pontos corridos, como o Brasileirão, temos k=2. Porém, diferentemente de um campeonato normal, vitória vale 2 pontos (e não 3), empate 1 e derrota 0. Imagine agora que estamos a certa altura do campeonato e algumas partidas já foram jogadas. A pergunta é: existe uma combinação dos resultados dos jogos restantes que fará com que o time para o qual estamos torcendo, seja não somente o campeão, mas que também tenha mais pontos que o segundo colocado?

Esse problema pode ser modelado como fluxo em redes e resolvido com um algoritmo de fluxo máximo. No dia da prova pensamos em modelá-lo dessa forma, mas não conseguimos chegar a um modelo correto.

Fluxo em redes

A primeira coisa a se fazer, é processar as partidas já realizadas, computando os pontos de cada time de acordo com a regra. Depois, observamos que, sem perda de generalidade, podemos fazer o nosso time predileto ganhar todas as partidas que lhe restam.

Seja o número total de pontos que nosso time tem após todas essas considerações. Observe que é a melhor pontuação que o nosso time pode obter. Porém, para que ele ganhe o campeonato, dependemos da pontuação dos outros times. Queremos uma combinação de jogos em que nenhum dos times restantes tenha mais do que pontos.

Se, mesmo antes de considerar os jogos não realizados, já houver time com ou mais pontos, não há o que fazer. Consideremos então que todos os times têm no máximo pontos. Seja o número de pontos do time i. Queremos que um time i ganhe no máximo pontos com as próximas partidas.

Vamos definir nosso grafo. Crie um nó para cada partida restante e um nó para cada time, além dos vértices fonte e destino, s e t, respectivamente. Para cada partida p, crie uma aresta (s, p) com capacidade 2, que representa o total de pontos que aquela partida vale. Além do mais, sejam u e v os times envolvidos na partida p. Crie uma aresta (p,u) e (p,v), ambas com capacidade 2. Finalmente, para cada time i, crie uma aresta (i, t) com capacidade .

Modelagem de uma partida entre os times u e v.

Afirmamos que existe uma combinação de resultados tal que nosso time de escolha fique em primeiro lugar isolado, se e somente se, o fluxo máximo na grafo definido acima for exatamente igual a 2*npr onde npr é o número de partidas restantes.

Prova: Observe que se o fluxo máximo for 2*npr, todas as arestas que saem de s estarão saturadas, ou seja, estará passando 2 unidades de fluxo. Temos duas arestas saindo de cada partida p. Sejam fu e fv a quantidade de fluxo nessas arestas respectivamente. Dadas as 2 unidades de fluxo chegando em p, as possíveis saídas (fu, fv) são (2, 0), (1, 1) ou (0, 2), sendo que cada uma dessas possibilidades representa um possível resultado de jogo. Já para cada time i, a quantidade de fluxo que chega no seu vértice correspondente a partir de uma dada partida p, é a quantidade de pontos que ganhou com aquela partida. Por conseguinte, a quantidade de fluxo que sai dele é o total de pontos conquistados. Note que, devido à capacidade da aresta, estamos limitando a quantidade de pontos que um dado time pode ganhar. Assim, se o fluxo é 2*npr, significa que conseguimos distribuir os pontos das partidas restantes entre os times, de forma que nenhum deles alcance nosso time predileto.

Além disso, dada uma combinação de resultados das partidas, é fácil construir um fluxo máximo de tamanho 2*npr.

Modelagem de um time.

Uma otimização para que o grafo não fique muito grande é: se existem k’ partidas restantes entre os times u e v, ao invés de criar k’ nós, criamos apenas um, mas multiplicamos as capacidades das arestas de entrada e saída por k’.

Observe que o sistema de pontuação foi modificado para que essa modelagem fosse possível. Se a vitória valesse 3, não conseguiríamos modelar as pontuações (3, 0), (1, 1) e (0, 3).

Algoritmo Guloso

Alguns maratonistas implementaram uma solução gulosa, que foi aceita no site nuevo portal.

A ideia é a seguinte. Computamos os pontos dos jogos já ocorridos e também assumimos que o time escolhido ganha o restante de seus jogos. Além disso, assumimos, a princípio, que todos os outros times empatam seus jogos.

O passo guloso é assim: Verificamos se o nosso time está na liderança isolada. Se sim, então temos uma combinação de resultados válida. Caso contrário, selecionamos o primeiro colocado x (ou algum que esteja dividindo a liderança com nosso time) e o time pior classificado y que tinha inicialmente um jogo não jogado com x. Desfazemos o empate entre x e y e fazemos x perder pra y. Reordenamos os times com essa nova pontuação e repetimos o passo. Se não houver tal y, declaramos que não existe nenhuma configuração de jogos que leve à situação desejada.

Pensei em um contra-exemplo que pode estragar essa estratégia se nenhum cuidado adicional for tomado. Considere 7 times, A, B, C, D, E, F e G, sendo que estamos torcendo pelo time A. Suponha que k=1, e já tiveram vários jogos de forma que só restam as partidas: (B,E), (B,F), (C,E) e (D,E) e que A, B, C, D têm 7 pontos, F e G têm 5 e E tem 4 (depois de considerados os empates dos jogos restantes).

Imagine que o algoritmo selecione B para perder de E (que é o pior classificado), ficando B com 6 pontos e E com 5. Agora suponha que ele selecione C, que necessariamente tem que perder para E (é a única partida que lhe resta). C tem 6 e E tem 6. O único time que está empatado com A é o D, que só pode perder para E, fazendo com que D tenha 6 e E tenha 7. Agora E passa a ficar empatado com A, mas como E não tem mais jogos, o algoritmo vai acusar que não há solução.

Tabelas de classificação ao longo da execução do algoritmo guloso.

Porém, se B perder para F ao invés de E e tanto C quanto D perderem para E, todos esses times ficam com 6 pontos e A ficará na liderança isolada.

Tabelas de classificação ao longo da estratégia ótima.

Uma pergunta é: o resultado que eu usei como contra-exemplo pode ser obtido com alguma combinação de jogos? Eu fiz na mão e aparentemente dá sim. Tive inclusive que adicionar o vértice G para a conta bater :P (note que ele não é usado no contra-exemplo).

Porém, essa é uma pergunta que pode ser respondida com uma modelagem por fluxo em rede e uma consequente redução ao problema do fluxo máximo, usando as ideias do modelo apresentado anteriormente.


Google Developer Day 2010

Novembro 5, 2010

Sexta-feira passada amigos do instituto e eu, fomos ao Google Developer Day, que é um evento para apresentar as novas tecnologias do Google para desenvolvedores de aplicativos. O evento era gratuito. Para se inscrever tinha que mandar um currículo e resolver uns probleminhas de programação.

Introdução

Havia quatro assuntos principais de palestras: Android, Chrome/HTML5, Computação em Nuvem e API’s do Google. As palestras ocorreram em três salas diferentes, de forma que não era possível assistir a todas. Meu principal interesse eram as palestras sobre Chrome e HTML5, pois tenho alguma experiência com desenvolvimento web. Não sabia nada sobre Android, mas como queria aprender alguma coisa, decidi assistir algumas das palestras relacionadas.

Minha experiência com desenvolvimento de aplicativos sempre foi bem superficial. Já tinha lido alguns tutoriais sobre Web Toolkit e usado a API do Google Maps. Também já comecei o desenvolvimento de uma extensão para o Firefox (até descobrir que alguém já tinha feito o que eu estava pensando em fazer, só que melhor :P – considerei a hipótese de adaptá-la para o Google Chrome, mas faltou tempo e disposição).

Bonequinho que ganhamos de brinde

Abertura

A palestra de abertura deu uma geral sobre os quatro tópicos. Uma das apresentações que mais chamaram a atenção foi sobre Chrome/HTML5, onde apresentaram um vídeo que roda usando um componente do HTML5, chamado canvas. Ele usava o acelerômetro presente em alguns notebooks e celulares, pois quando o notebook no qual o vídeo era apresentado foi inclinado, o vídeo desmoronou. Também apresentaram cenas 2D e 3D, renderizadas em tempo real, usando aceleração por hardware (através de GPUs).

Outra palestra que arrancou aplausos foi sobre o sistema de reconhecimento de voz em português, presente na nova versão do Android. Funcionou muito bem quando o palestrante fez uma pesquisa pronunciando uma determinada frase.

Depois tivemos que escolher as palestras. Vou comentar brevemente sobre as que assisti. Para o cronograma completo, veja o site oficial.

Melhore seu Navegador com Extensões para o Google Chrome

Nessa palestra foi apresentado o sistema de extensão do google chrome. Pareceu bem simples de usar. O criador do Chromed Bird apareceu por lá para dividir suas experiências. Foi passado o endereço do google-groups dos desenvolvedores de extensões do Chrome.

Desenvolvendo para uma Web mais rápida

Aqui foram apresentados aspectos do HTML5 e da nova versão do Javascript (1.6) relacionados a desempenho. Alguns deles são: uso de cache para aplicações web, uso de processadores multi-core (através de passagem de mensagens) e websockets, que é quase um TCP/IP para Javascript, bastante interessante para aplicativos multi-usuários que exigem resposta rápida, como por exemplo chats e jogos multi-player.

HTML5++ – O Futuro da Web, Agora!

Foram Detalhadas as novas funcionalidades do HTML5. As que me lembro são:

  • Execução de vídeos usando canvas (como na palestra incial);
  • Drag-and-drop (sem Javascript): mover objetos dentro de uma página, ou fazer upload de arquivos apenas movendo ícones da pasta local para o browser;
  • Geolocalização: acesso às coordenadas geográficas do usuário;
  • Orientação do aparelho, usando o acelerômetro (também exibido na palestra inicial).
  • WebGL: análogo ao OpenGL para a Web

Exemplo de cena renderizada no próprio browser (fonte).

Também falaram um pouco da nova versão do CSS, o CSS3, que traz muitas facilidades que antes só podiam ser feitas com magia-negra :)

  • Atributos como reflection, text shadow, round corners agora são padrão;
  • Além disso, foram adicionadas transformações e animações de objetos.

Práticas Efetivas de Interface com o Usuário

O palestrante deu umas dicas sobre como melhorar a interface de um aplicativo android. Algumas características são:

  • Beleza: o aplicativo deve ser visualmente agradável;
  • Rapidez: tempo de resposta do aplicativo deve ser impeceptível ao usuário;
  • Uso intuitivo: deve haver pouca ou nenhuma instrução;
  • Modos de visualização: o aplicativo deve sempre ser desenvolvido para retrato e paisagem;
  • Integração: deve se integrar a aplicativos já existentes, e não conter todas as funcionalidades em si próprio;
  • Não deve exibir pop-ups de confirmação de uma ação e sim oferecer a possibilidade de desfazê-la.

Outras palestras

Assisti a mais duas palestras: “Aplicativos Android Flexíveis: Adaptando-se ao Hardware/Local” e “Construindo Aplicativos de Alto Desempenho”. Mas elas entraram em detalhes muito técnicos sobre o Android e por isso não consegui absorver nenhum conteúdo direito.

Conclusão

Achei as palestras bem legais e tiveram bastantes brindes (bonequinho, camiseta, bloco de notas, squeeze, pasta, capa de notebook, bolinhas). Porém, como respondi no questionário final, é um tipo de conteúdo que conseguiríamos obter na internet. Aliás, acho que eu teria aproveitado bem melhor o conteúdo das palestras técnicas se fosse através de tutoriais. Por outro lado, é o tipo de material que coloco na fila de coisas a aprender e quase nunca acabo vendo. As palestras forneceram uma boa introdução e deram direções a seguir. Acho que com esse empurrãozinho, fico mais animado a desenvolver uma extensão para o Chrome e me aprofundar em HTML5.