Gnuplot e a complexidade de algoritmos
Esta semana, me peguei usando pela primeira vez o gnuplot. E o mais curioso disto, para analisar, a grosso modo, o comportamento de um programa que recebe como entrada uma matriz de dados, no caso, o haploview.
Não vamos entrar em detalhes aqui, mas o haploview é um aplicativo JAVA usado para estudar haplótipos, e a pergunta que eu tinha que responder era “qual o tamanho máximo de um dataset que eu posso usar dado um heap de tamanho X?”. Lógico que a resposta correta inclui “e se seu cliente te perguntar o que muda se você puder usar isso + X?”.
É interessante porque não é o tipo de pergunta que a gente se faz normalmente. Geralmente, você assume que o tamanho da entrada nunca vai ser grande demais, ou se você alocar um heap grande o suficiente, ainda que ao custo de alguma lentidão por conta do trabalho extra do garbage collector, as coisas funcionarão.
O mais comum são as pessoas fazerem o profiling em busca de gargalos, mas eu não ouço falar muito de gente que tenta descobrir até onde o sistema aguenta.
Bem, não é este exatamente o caso do haploview. É um software de terceiros e nem quem fez o software tem idéia de qual a ordem de complexidade (o big “O”) do sistema, muito menos da capacidade máxima.
E se tratando de dados “bioinformáticos”, sempre é fácil que as coisas se tornem rapidamente grandes demais. E a última coisa que se quer é morrer com um doloroso “OutOfMemory”. Você tem que saber os limites.
Basicamente, um dataset é uma grande matriz de dados, e como o haploview é uma caixa preta, podemos considerar que o número de linhas da entrada (no caso, o número de indivíduos) é uma dimensão e o número de colunas (o número de marcadores) é outra dimensão.
Vamos plotar no gráfico valores em 3 direções: [a] variando apenas o número de indivíduos, [b] variando apenas o número de marcadores e [c] variando ambos, proporcionalmente (diagonalmente). Assim podemos ter uma idéia, ainda que não muito refinada, do comportamento do sistema.
De posse destes pontos, você pode observar uma tendência na relação entre o consumo de memória e a entrada de dados. Conforme a “cara” do gráfico, você pode achar mais adequado tentar interpolar com algum tipo de superfície. No meu caso, uma superfície levemente abaulada ficou bem interpolada com uma superfície polinomial do tipo ax^2 + by^2 + cxy + d. Deu complexidade quadrática na veia.
Nesta hora, o gnuplot se revelou de uma simplicidade franciscana, já que você pode passar para ele uma função e mandar ele fazer o “fit” e achar os valores de a, b, c e d, passando como entrada um arquivo tabular (”data.txt”) com os valores de cada eixo em cada coluna.
set title “Haploview memory usage”
set xlabel “Individuals”
set ylabel “Markers”
set zlabel “Used Memory”
g(x,y) = a*x**2 + b*y**2 + c*x*y + d
fit g(x,y) ‘data.txt’ using 1:2:3:(1) via a, b, c, d
splot ‘data.txt’ using 1:2:3, g(x,y)
Você pode achar útil esta apostila em português sobre o gnuplot, pelo menos até que saia o livro.
Claro que existem uma série de outras boas ferramentas como matlab, R, octave, scilab e etc, mas se você quer algo rápido, gnuplot pode ser uma boa saída. E se for prá gerar coisas bem coloridas e visualmente atrativas prá colocar naquele seu paper, você pode tentar estas opções aqui também, prá ficar com aquela cara de Scientific American 
.
