Notas sobre optimizações

Em um artigo que eu logo escreverei, eu mostrei um programa que lê configurações de um arquivo de texto (Nota mental: André, pare de viajar no tempo que seus artigos estão ficando mais confusos que de costume).

A idéia é bem simples, um struct com dois char*s: o nome da variável e o valor dela, mas como organizar isso? Um array eu descartei logo de início, (mas escrever isso me deixou curioso com como ele se comportaria), sobravam listas e árvores binárias.

Árvores tem a vantagem na hora da busca por uma variável. Na pior hipótese ela funcionará como uma lista praticamente (cada folha está ligada a apenas uma outra), dando um caso O(n). Na melhor hipótese (árvore bem distribuída), nós não precisamos buscar a árvore inteira. Por exemplo, uma árvore de 15 membros terá 1 folha no primeiro nível, 2 no seguinte, 4 no próximo e 8 no último. Mesmo que a variável que queremos esteja no último nível, isso significa que passamos por 4 níveis até chegar nela.

Já as listas na hora da busca vão depender da posição da variável. Se a variável buscada estiver no início da lista, será rápido, se estiver no fim, irá demorar. Sim, é sério.

Porém, listas têm a vantagem na hora de adicionar uma nova variável, simplesmente empurrá-la no início da lista. As árvores colocam a nova variável no nas “pontas” e precisam checar se a nova variável vai à esquerda ou à direita.

Outra questão é que árvores são um pouco maiores, já que guardam dois ponteiros e não um só.

Para testar, eu criei um arquivo de “configuração” de 200 mil linhas na mão. Mentira, eu usei o seguinte código:

#include
#include
#include

#define MAX 200000

int main(int argc, char *argv[])
{
int count = 0;
FILE *fptr = fopen(“/tmp/example.cfg”,”w”);

srand(time(0));

for(count = 0; count < MAX; count++) fprintf(fptr, "%d = %d\n", rand() % 1000000, rand() % 1000000); fclose(fptr); return(0); } [/sourcecode] Sim, eu usei números. Na pratica isso não faz diferença já que o nome da variável continuará sendo um char*, só que um char* que representa um número. Eu rodei esse programa uma vez apenas e usei o mesmo arquivo para todos os testes (é claro que eu editei na hora de colocar a opção ‘message’).

Nos resultados eu chamo de mean a média aritmética de todos os valores e sanatized mean a média aritmética descartando o valor mais alto e o mais baixo.

PARSE TIME é o tempo de ler o arquivo e não fazer mais nada. Depois eu meço o tempo para achar a opção ‘message’ na primeira linha, na linha 100 mil, na linha 200 mil e quanto tempo demora para descobrir que não há um message ali.

Talvez depois eu faça um novo teste, usando arrays, listas, listas sem reverse().

file (3.1MB):
-rw-r--r-- 1 andre users 3155925 2009-02-15 15:17 example.cfg


===PARSE TIME===
list:
  times: 0.793 0.789 0.789 0.788 0.790
  mean: 0.7898
  sanatized mean: 0.7893

tree:
  times: 1.921 1.917 1.926 1.941 1.911
  mean: 1.9232
  sanatized mean: 1.9213


===PARSE TIME + FIND 'message' IN THE BEGGINNING OF FILE===
list:
  times: 0.803 0.804 0.813 0.805 0.806
  mean: 0.8062
  sanatized mean: 0.8050

tree:
  times: 1.953 1.957 1.936 1.939 1.955
  mean: 1.9480
  sanatized mean: 1.9490


===PARSE TIME + FIND 'message' IN THE MIDDLE OF FILE===
list:
  times: 0.823 0.825 0.823 0.825 0.829
  mean: 0.8250
  sanatized mean: 0.8243

tree:
  times: 1.917 1.921 1.924 1.928 1.917
  mean: 1.9214
  sanatized mean: 1.9206


===PARSE TIME + FIND 'message' IN THE END OF FILE===
list:
  times: 0.843 0.843 0.845 0.847 0.850
  mean: 0.8456
  sanatized mean: 0.8449

tree:
  times: 1.918 1.937 1.919 1.920 1.915
  mean: 1.9218
  sanatized mean: 1.9190


===PARSE TIME + FIND UNEXISTING 'message'===
list:
  times: 0.834 0.833 0.834 0.833 0.832
  mean: 0.8332
  sanatized mean: 0.8333

tree:
  times: 1.922 1.910 1.922 1.921 1.919
  mean: 1.9188
  sanatized mean: 1.9206


===MEMORY USAGE===
list:
USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
andre     3695 76.0 16.8  54860 53700 tty1     S+   15:44   0:00 ./list example.cfg

tree:
USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
andre     3706 95.0 17.3  56444 55264 tty1     S+   15:46   0:01 ./tree example.cfg
Publicidade

7 Respostas para “Notas sobre optimizações

  1. NiX fevereiro 25, 2009 às 7:28 pm

    André, qual script você usou para gerar essas estatísticas de tempo médio e uso de memória?

  2. William fevereiro 28, 2009 às 8:52 pm

    Resumindo: A arvore foi mais lenta em todos os testes?

    Que pena eu apostaria nela em termos de velocidade.

    • André Ramaciotti fevereiro 28, 2009 às 9:11 pm

      Foi uma surpresa para mim também. Eu primeiro implementei a versão com listas e depois implementei a versão com árvores justamente por achar que seria mais rápida.

      Um detalhe, porém, é que eu não utilizei nenhum tipo de árvore optimizado, mas creio que isso aumentaria ainda mais o tempo de criação da árvore e você pode ver que o tempo de busca é quase desprezível.

  3. William fevereiro 28, 2009 às 9:25 pm

    André nao duvido da qualidade do seu código, muito pelo contrario: leio frequentemente seus posts e tenho aprendido bastante a respeito.

    Mas fico aguardando o codigo utilizado nos teste só para termos um ideia mesmo.

    Parabéns!

  4. André Ramaciotti fevereiro 28, 2009 às 9:36 pm

    Quando eu falei da optimização, eu quis dizer dos métodos que existem para garantir que a “altura” de uma árvore seja mais ou menos a mesma saindo de qualquer tronco dela. Na verdade, eu ainda preciso estudar melhor esses métodos.

    De qualquer forma, obrigado pelo comentário. É bom saber que tem gente acompanhando o blog e aproveitando o que eu escrevo aqui. :)

  5. Pingback: Notas sobre optimizações II: O código « Aletéia

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

%d blogueiros gostam disto: