Introdução a Guava – Revista Java Magazine 104

Junho 24, 2012

Este mês foi publicada na revista Java Magazine uma matéria que escrevi sobre o projeto Guava. O mais legal é que o convite foi feito por causa dos posts sobre Java que escrevi aqui no blog.

Basicamente o Guava é composto por um conjunto de bibliotecas que visam simplificar a vida do desenvolvedor. Ela foi inicialmente desenvolvida pelo Google e depois teve seu código-fonte disponibilizado.

No artigo descrevemos um probleminha simples e apresentamos uma solução que utiliza diversas bibliotecas do Guava. Usamos uma extensão da Collections do SDK, utilitários para estruturas de dados do SDK como List e Map, novas estruturas de dados como muli-mapas, manipulação de String e IO, funções que visam tornar expressões matemáticas mais legíveis, etc. Na solução também aplicamos um paradigma funcional para demonstrar o uso das classes Function e Predicate que podem simplificar e melhorar a legibilidade do código.

O conteúdo completo é restrito a assinantes, mas uma prévia está disponível aqui.

Acabei deixando alguns componentes do Guava de fora como Cache, Concorrência e EventBus, mas algum dia pretendo estudá-los.

Conclusão

Embora a escrita de um artigo para uma revista tome mais tempo que a de um post do blog, o conteúdo fica com uma qualidade melhor porque passa por revisão. Além disso, aprendi um assunto que eu vinha querendo estudar faz um tempo. Enfim, gostei da experiência e pretendo escrever novos artigos.

Anúncios

Mapas de Símbolos Fisicamente Realizáveis: a função Max-Min

Junho 5, 2012

Já escrevi sobre o tema de pesquisa do meu mestrado — otimização da visualização de mapas de símbolos proporcionais — em outros posts [1], [2] e [3].

Desta vez gostaria de falar sobre uma das variantes desse problema proposta por Cabello et al [4] onde o objetivo é basicamente dispor os símbolos no mapa de modo a maximizar a visibilidade do disco menos visível. Mais formalmente, dado um conjunto de discos S e uma disposição deles no plano, denotamos por b_i o comprimento da borda visível do disco i \in S.

O objetivo é encontrar uma disposição dos discos que maximize \min \{b_i\}. Não por acaso tal função é chamada de Max-Min.

Cabello et al. apresentaram um algoritmo guloso que maximiza essa função objetivo quando os discos só podem ser empilhados (não podem ser entrelaçados). A ideia é bem simples: dado um conjunto de n discos S, escolha o disco i^* que se posto por baixo de todos os outros teria o maior comprimento de borda visível (ou seja, b_i^* é máximo). Coloque i^* na base e determine a ordem dos outros discos recursivamente.

A versão “força-bruta” desse algoritmo é O(n^3), mas eles apresentam uma versão O(n^2 \log n) usando árvores de segmentos.

Se permitirmos que os discos possam ser entrelaçados, conforme a figura abaixo à esquerda, o problema se torna NP-difícil!

Disposição com entrelaçamento vs. disposição em pilha

Já havíamos atacado a versão que objetiva maximizar a soma das bordas visíveis considerando todos os discos (chamada de Max-Total) e permitindo entrelaçamento usando Programação Linear Inteira. Esse trabalho foi apresentado no Sibgrapi de 2011.

Após esse congresso, fomos convidados a estender nosso trabalho com pelo menos 30% de novo conteúdo e submeter para a publicação em um jornal científico, o The Visual Computer.

Decidimos então atacar a versão com função objetivo Max-Min usando PLI também. A formulação é bastante parecida com aquela que apresentamos no Sibgrapi, mas resolvedores de PLI têm bastante dificuldade em lidar com formulações do tipo max-min, onde se quer maximizar o menor valor de uma função.

Em nossos experimentos, instâncias para as quais o resolvedor achava a solução ótima da função Max-Total em segundos, não eram resolvidas mesmo rodando durante algumas horas para a versão Max-Min.

Uma possível causa para esse comportamento é que para formulações max-min temos muitas soluções com mesmo valor (platôs) e isso faz com que os otimizadores se percam.

Para um exemplo, considere as soluções na figura abaixo. Embora sejam bastante diferentes, elas possuem o mesmo valor da função Max-Min porque o disco destacado em vermelho é tão pequeno, que é ele que define o valor da função objetivo não importando a disposição entre o restante dos discos.

Soluções com mesmo valor da função Max-Min (definida pela borda do disco vermelho)

Como muitas das nossas instâncias podem ser decompostas em componentes menores, usamos a seguinte ideia para tentar melhorar o desempenho do nosso algoritmo. Considere as componentes decompostas c_1, c_2, \cdots, c_k. Seja s(c_i) o valor da solução ótima de c_i para Max-Min limitado a desenhos em pilha e p(c_i) permitindo também desenhos entrelaçados.

Suponha que as componentes estão numeradas de forma que s(c_1) \le s(c_2) \le \cdots \le s(c_k). Assim, a solução ótima da instância completa para desenhos em pilha é igual a s(c_1).

Temos também que s(c_i) \le p(c_i), pois estamos maximizando uma função e p considera tanto desenhos em pilha quanto entrelaçados.

Infelizmente não podemos afirmar que p(c_i) \le p(c_{i+1}). Porém, seja i^* = \mbox{argmin}_i\{p(c_i)\}. Se p(c_{i'}) \le s(c_{i'+1}) para algum i' \le k-1, então temos que p(c_{i'}) \le s(c_{j}) para i' < j e portanto p(c_{i'}) \le s(c_{j}) para i' < j, ou seja, i^* \le i'.

A ideia do algoritmo é resolver cada componente com o algoritmo polinomial de Cabello e ordená-las pelo valor da solução, obtendo s(c_1) \le s(c_2) \le \cdots \le s(c_k). Em seguida resolvemos as componentes nessa ordem usando a formulação do Max-Min permitindo desenhos entrelaçados, obtendo a cada passo p(c_i). Se em algum passo encontramos p(c_{i}) \le s(c_{i+1}), podemos parar pois já encontramos o valor ótimo.

Esse nosso trabalho foi aceito, tendo sido publicado online recentemente [5].

Referências

[1] Blog do Kunigami: Mapas de Símbolos Proporcionais
[2] Blog do Kunigami: Mapas de símbolos proporcionais e a meia integralidade da cobertura de vértices
[3]Blog do Kunigami: Visualização ótima de desenhos fisicamente realizáveis
[4] S. Cabello, H. Haverkort, M. van Kreveld, and B. Speckmann, “Algorithmic aspects of proportional symbol maps”, Algorithmica, 2010.
[5] G. Kunigami, P. de Rezende, C. de Souza and T. Yunes, “Generating Optimal Drawings of Physically Realizable Symbol Maps with Integer Programming”, 2012


Visualização ótima de desenhos fisicamente realizáveis

Outubro 23, 2011

Hoje vou descrever o trabalho que apresentei no Sibgrapi 2011, entitulado “Determining an Optimal Visualization of Physically Realizable Symbol Maps“, escrito em conjunto com meus orientadores (professores Pedro e Cid) e o professor Tallys da Universidade de Miami. Há um

Trata-se de uma extensão do estudo que realizamos para o problema de mapas de símbolos proporcionais usando desenhos em pilha, sobre o qual comentei em um post anterior.

Desenho fisicamente realizável

Um desenho fisicamente realizável é uma generalização de um desenho em pilha, pois este permite ordens cíclicas, como no exemplo abaixo.


Desenho fisicamente realizável e desenho em pilha

Podemos pensar que desenhos fisicamente realizáveis são aqueles feitos a partir de discos de papel, desde que estes não sejam dobrados nem cortados.

O problema é encontrar um desenho fisicamente realizável que maximize a soma dos comprimentos das bordas visíveis. Esse problema é chamado Max-Total para desenhos fisicamente realizáveis.

Tínhamos desenvolvido um modelo de programação linear inteira para o problema Max-Total para desenhos em pilha e mostramos que um subconjunto das desigualdades desse modelo, resolvia o problema Max-Total para desenhos fisicamente realizáveis.

Discutimos aspectos teóricos sobre as desigualdades utilizadas no modelo, argumentando que elas tornam a formulação apertada. Na prática um modelo com formulação apertada tende a ser resolvido mais rapidamente pelo algoritmo de branch and bound.

Técnica de decomposição

Desenvolvemos uma técnica de decomposição nova, que só serve para esse tipo de desenho. A ideia básica das decomposições é quebrar o conjunto de discos de entrada em componentes menores e mostrar que podemos resolver a cada componente de maneira independente e então combiná-las em tempo polinomial para gerar a solução ótima da instância completa. Uma decomposição óbvia é considerar conjuntos de discos disjuntos no plano.

Para desenhos fisicamente realizáveis, podemos ignorar a interseção de discos em alguns casos. Isso por sua vez pode gerar novas componentes disjuntas. No exemplo abaixo, mostramos que é possível ignorar a interseção dos discos nas faces amarelas. Isso quebra a componente em duas que podem ser resolvidas isoladamente.

Exemplo de decomposição

Junto com as outras decomposições que já havíamos desenvolvido para desenhos em pilha, conseguimos diminuir o tamanho das instâncias de teste.

Resultados computacionais

Após resolvermos a formulação do problema para desenhos fisicamente realizáveis, constatamos que na grande maioria dos casos, o valor da solução era exatamente igual ao da solução para desenhos em pilha.

Mesmo para as instâncias onde houve diferença, esse valor foi muito pequeno e visualmente é muito difícil distinguir as soluções, conforme pode ser visto na figura a seguir.

Zoom de uma solução ótima usando desenho em pilha e desenho fisicamente realizável

Entretanto, também tivemos uma boa surpresa, que foi o tempo de execução desse novo modelo. Em média, ele foi aproximadamente 2 ordens de magnitude mais rápido do que modelo para desenhos fisicamente realizáveis.

Conclusão

Devido aos tempos obtidos com o novo modelo e o fato de as soluções obtidas serem muito próximas a desenhos em pilha, uma ideia é usarmos esse modelo para resolver o problema de desenhos em pilha, adicionando restrições para remover os eventuais ciclos que apareçam.

Podemos adicionar essas restrições de remoção de ciclo através de um algoritmo de planos de corte, de um modo similar ao usado para resolver o problema do caixeiro viajante.


Temas do Beamer

Agosto 14, 2011

Faz um bom tempo já que eu faço slides usando latex, mais especificamente o pacote Beamer. Há vários temas que se pode escolher, como por exemplo Boadilla, Copenhagen, Cambridge, Darmstadt, etc. Sim, os nomes dos temas em geral são nomes de cidades.

Eu sempre usava algum desses temas sem nenhuma customização. Entretanto, algumas vezes eu queria combinar características de temas diferentes, mas acabava me conformando em usar apenas a de um tema.

Em meados de 2010 o Peterson fez um tema customizado, que acabamos adotando informalmente como o do laboratório, tanto que eu o usei nas duas apresentações que fiz nos seminários do LOCo.

Componentes de um tema

Na verdade um tema é composto por diversas partes: cor, tema externo, tema interno e fonte. Há vários desses temas pré-definidos no sistema, com nomes não muito sugestivos.

color — albatross, beaver, beetle, crane, default, dolphin, dove, fly, lily, orchid, rose, seagull, seahorse, sidebartab, structure, whale, wolverine;

outer — default, infolines, iniframes, shadow, sidebar, smoothbars, smoothtree, split, tree;

inner — circles, default, inmargin, rectangles, rounded;

font — default, professionalfonts, serif, structurebold, structureitalicserif, structuresmallcapsserif.

Como primeiro exemplo, vamos usar a seguinte combinação:

\usecolortheme{wolverine}
\useinnertheme{circles}
\useoutertheme{infolines}
\usefonttheme{default}

Código 1: Temas

Usando esse código latex de exemplo, a saída será:


Figura 1: Capa usando temas do Código 1


Figura 2: Texto usando temas do Código 1

Agora, usando uma nova combinação

\usecolortheme{albatross}
\useinnertheme{rectangles}
\useoutertheme{sidebar}
\usefonttheme{structurebold}

Código 2: Temas


Figura 3: Capa usando temas do Código 2


Figura 4: Texto usando temas do Código 2

Criando seu próprio tema

Segundo o manual (pdf), esses componentes de tema são apenas para uma melhor modularização, de modo que você pode definir tudo no próprio .tex em que estiver trabalhando.

Porém, se quiser manter a organização, e quiser criar um tema com nome xyz para as componentes color, inner, outer e font, deve editar um arquivo com nome beamercolorthemexyz.sty, beamerinnerthemexyz.sty, beamerouterthemexyz.sty ou beamerfontthemexyz.sty, respectivamente.

Tema de cores

O tema de cores, como o nome diz, contém as definições de cores das estruturas usadas pelos temas. Se quisermos que o tema de cores possa ser combinado com qualquer um dos outros temas, a sugestão é pegar o código de algum outro tema e editar as cores da maneira desejada. Desta forma, estaremos cobrindo todas as possíveis estruturas.

Tema interno

O tema interno controla diversos elementos como: página de título, o ambiente itemize, o ambiente enumerate, os blocos, figuras e tabelas, etc. Para escolher cada o estilo de cada item, usamos o comando \setbeamertemplate{nome do item}[valor]

Alguns exemplos:

\setbeamertemplate{blocks}[rounded][shadow=true]
\setbeamertemplate{items}[circle]
\setbeamertemplate{enumerate item}[square]

O exemplo é auto-explicativo, e é basicamente o que usei na adaptação do tema do Peterson.

Tema externo

O tema externo define como será o topo e a base da página, ou seja, a estrutura externa da mesma. O melhor é criar seu tema a partir de um pré-existente que mais se assemelha à estrutura desejada.

No exemplo abaixo, o trecho do tema infolines que define a parte inferior da página (footline):

\defbeamertemplate*{footline}{infolines theme}
{
  \leavevmode%
  \hbox{%

  \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot}\insertshortauthor~~(\insertshortinstitute)
  \end{beamercolorbox}%

  \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,center]{title in head/foot}%
    \usebeamerfont{title in head/foot}\insertshorttitle
  \end{beamercolorbox}%

  \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,right]{date in head/foot}%
    \usebeamerfont{date in head/foot}\insertshortdate{}\hspace*{2em}
    \insertframenumber{} / \inserttotalframenumber\hspace*{2ex} 
  \end{beamercolorbox}}%
  \vskip0pt%
}

O código acima está definindo três blocos de mesmo tamanho (controlado por wd – width), conforme pode ser conferido na Figura 2. Além disso, no primeiro bloco será inserido o nome encurtado do autor e do instituto, definidos pelas macros \insertshortauthor e \insertshortinstitute.

Dá para modificar essa parte do jeito que for mais conveniente. Por exemplo, se não quisermos que apareça o nome do autor/instituto pois é um seminário onde todos te conhecem, podemos usar apenas dois blocos e ajeitar a largura para wd=.5\paperwidth.

Como a contagem de páginas geralmente ocupa menos espaço e o nome do trabalho ocupa mais, eu modifiquei o tema acima para ficar com as proporções 3/6/1, sacrificando simetria por legibilidade.

Customizando as cores, as estruturas internas e externas, adaptei o tema do Peterson, que ficou com a seguinte cara:

Figura 5: Capa usando tema do LOCo modificado

Figura 6: Texto usando tema do LOCo modificado

Extra: Coloração das linhas de tabelas

Embora tabelas devam ser customizadas no tema interno, até onde eu sei essa em particular não pode ser inserida como parte do Beamer. Dado exemplo de tabela (código):

Queremos que as linhas alternem suas cores. Para fazer isso, podemos usar o comando \rowcolors{l}{cor1}{cor2}, onde l é deve conter o númnero da linha onde a coloração irá começar, cor1 e cor2 são as cores que serão alternadas.

Esse comando é bugado para tabelas com multi-colunas como no exemplo acima. Para isso é preciso acertar manualmente a cor da coluna com o comando \columncolor{cor}. O novo código pode ser conferido aqui.

O resultado fica então:

Referências

[1] Beamer User Guide (pdf)
[2] http://www.tug.org/pracjourn/2005-4/mertz/mertz.pdf


Mapas de Símbolos Proporcionais

Abril 17, 2011

Sexta-feira passada apresentei uma palestra na série de seminários do LOCo. Falei sobre o problema que estou atacando no mestrado.

Um mapa de símbolos proporcionais emprega símbolos para exibir eventos associados a alguma localidade e intensidade. O símbolo é posicionado no local de ocorrência do evento e a sua área fica sendo proporcional à intensidade desse evento. Focamos em mapas que usam círculos opacos como símbolos. A figura abaixo é um exemplo representando as populações das maiores cidades do Brasil.

Note que há sobreposição entre os discos. Dependendo da ordem em que os empilhamos, pode ser que haja mais ou menos porções dos discos visíveis. Há casos ruins em que a borda do disco fica totalmente encoberta, como na figura abaixo.


Não podemos inferir o centro nem o raio do disco com bordo escondido.

Para tentar fazer com que o desenho tenha bastante borda visível, usamos uma métrica que consiste em maximizar o comprimento visível total dos discos. Com isso em mente, é possível definir um modelo de programação linear inteira, com um modelo que atribui cada disco a um nível.

Além do modelo básico, desenvolvemos algumas desigualdades adicionais para tornar o modelo mais forte, nos baseando em propriedades geométricas, que impedem certas configurações de acontecerem.

Também desenvolvemos duas técnicas de decomposição de instâncias. Um jeito trivial de decompor instâncias é considerar componentes de discos conexas de maneira independente.

Nossa primeira técnica de decomposição vem da observação que um disco que está contido no outro sempre pode ser desenhado por cima em uma solução ótima. Dessa forma, em uma instância como a da figura abaixo, a componente {a, b} pode ser desenhada de maneira independente de {c, d, e, f} e na hora de construir a solução ótima, basta desenhar a solução obtida para {a, b} em cima da solução {c, d, e, f}.

Componente {a,b} está contida em {f} e pode ser resolvida separadamente.

Podemos definir um grafo Gs sobre os discos de S, com conjunto de vértices correspondendo aos discos e há uma aresta (i, j) em Gs se os discos correspondentes se interceptam. Falei sobre esse tipo de grafo em um post anterior.

A outra técnica consiste em remover um ponto de articulação de Gs e replicá-lo nas componentes conexas resultantes, como na figura abaixo.


O disco f representa um ponto de articulação em Gs. As figuras (ii), (iii) e (iv) são as componentes resultantes de sua remoção, com f replicado.

Mostramos que é possível resolver cada componente com o ponto de articulação replicado de maneira independente. Depois, basta juntar os discos mantendo a ordem relativa de cada sub-solução. Isso pode ser feito através de uma ordenação topológica.

Implementamos todas essas ideias e reportamos os resultados. As instâncias testadas foram as mesmas de um trabalho anterior no qual nos baseamos. As técnicas de decomposição foram efetivas na redução do tamanho das instâncias e o resolvedor XPRESS conseguiu resolver nosso modelo para quase todas as instâncias. Porém, ficaram algumas componentes sem serem resolvidas, o que nos motiva a procurar novos modelos e novas desigualdades.

Esse nosso trabalho foi aceito na Computational Geometry and Applications 2011.


Escrevendo com o emacs

Abril 3, 2011

Desde 2005 uso emacs devido às aulas introdutórias de programação. Nunca estudei muito a fundo esse editor que é capaz de realizar incontáveis tipos de tarefas. Mas aprendi algumas funcionalidades interessantes.

Sátira do xkcd com diversos editores (clique para ampliar)

Editando LaTeX

O auctex é uma extensão que facilita a edição de documentos LaTeX. Para quem usa ubuntu, basta instalar o pacote auctex.

Depois de instalar essa extensão, ao abrir arquivos .tex uma nova interface aparecerá, parecida com a imagem abaixo:

O botão do leão é equivalente a executar o comando latex no arquivo atual. Ele gera um arquivo no formato .dvi. O botão do óculos abre o arquivo .dvi com o programa xdvi. O botão do livrinho executa o comando bibtex sobre o arquivo .aux gerado com o comando latex. O último botão é um preview dentro do próprio emacs, mas eu particularmente não gosto.

Nota: o padrão do auctex é usar o comando latex que gera arquivos dvi. É possível mudar esse padrão para sempre gerar pdf’s usando o comando pdflatex. Para isso, adicione a seguinte linha ao arquivo de configuração do emacs, em ~/.emacs:

(add-hook 'LaTeX-mode-hook 'TeX-PDF-mode)

Observe ainda que existem diferenças entre os comandos latex e pdflatex. Uma delas é que latex só trabalha com imagens no formato .eps enquanto pdflatex trabalha com vários tipos de formatos (pdf, jpg, png), mas não .eps.

Correções ortográficas

O emacs tem uma funcionalidade de indicar erros ortográficos, chamada flyspell. O dicionário padrão é o inglês, mas é possível alterar para português brasileiro. Antes de mais nada, é preciso instalar suporte do aspell a essa linguagem. No ubuntu, basta instalar o pacote aspell-pt-br.

Depois, para trocar o dicionário, abra a linha de comandos no emacs (Alt+X) e digite o seguinte comando:

ispell-change-dictionary

Ele vai pedir o argumento, o qual deve ser:

portugues

Agora, se o seu texto já está escrito e você quer fazer a revisão ortográfica, abra a linha de comandos e digite:

flyspell-buffer

Se você quer começar a fazer a revisão ortográfica conforme vai escrevendo, use

flyspell-mode

As palavras que não estiverem de acordo com o dicionário ficarão destacadas. Clicando com o botão do meio do mouse aparece um menu com sugestões de correção ou opções de ignorar ou adicionar ao dicionário. Para ir para o próximo erro, é possível usar o comando flyspell-goto-next-error ou o atalho

Ctrl+,


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