Apresentando dados de experimentos com algoritmos

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

Os comentários estão fechados.

%d bloggers like this: