Notas sobre optimizações II: Os resultados

Parte I: O código

A metodologia foi basicamente a mesma da primeira vez, um arquivo aleatório de 200.000 linhas que depois foi editado para conter a opção “message” em diferentes lugares do arquivo. A diferença que dessa vez eu usei um script para agilizar as coisas um pouco.

Os resultados foram mais ou menos os mesmos que eu espera, considerando que as árvores já haviam me decepcionado na primeira vez. Comentarei um pouco mais sobre elas no fim.

Tempo de leitura do arquivo
Tempo que demorou para ler o arquivo e não fazer nada depois disso:

./array example.cfg
0.689197
0.688433
0.691231
0.68705
0.69087
mean: 0.689356
sanatized mean: 0.6895

./list example.cfg
0.79316
0.793905
0.796184
0.795348
0.793757
mean: 0.794471
sanatized mean: 0.794337

./list-sem_reverse example.cfg
0.751995
0.753233
0.753524
0.753044
0.754556
mean: 0.75327
sanatized mean: 0.753267

./tree example.cfg
2.16172
2.16645
2.18843
2.16645
2.17281
mean: 2.17117
sanatized mean: 2.16857

Uso de memória
Quantidade de memória usada após a leitura de todo o arquivo (porcentagem, virtual, residente):

16.3  53384 52116 ./array example.cfg
16.8  54860 53676 ./list example.cfg
16.8  54860 53680 ./list-sem_reverse example.cfg
17.3  56444 55244 ./tree example.cfg

“Message” no início
Tempo para carregar todo o arquivo e achar a opção “message” no começo do arquivo:

./array example.cfg
0.688658
0.694065
0.688985
0.688744
0.68947
mean: 0.689984
sanatized mean: 0.689066

./list example.cfg
0.793489
0.795995
0.795357
0.79465
0.796324
mean: 0.795163
sanatized mean: 0.795334

./list-sem_reverse example.cfg
0.790127
0.792349
0.789369
0.796447
0.789332
mean: 0.791525
sanatized mean: 0.790615

./tree example.cfg
2.20567
2.16939
2.17606
2.18844
2.1768
mean: 2.18327
sanatized mean: 2.18043

“Message” no meio do arquivo

./array example.cfg
0.703901
0.705752
0.705194
0.702771
0.706824
mean: 0.704888
sanatized mean: 0.704949

./list example.cfg
0.815561
0.816635
0.815653
0.814707
0.818573
mean: 0.816226
sanatized mean: 0.81595

./list-sem_reverse example.cfg
0.772795
0.76906
0.772435
0.771212
0.771204
mean: 0.771341
sanatized mean: 0.771617

./tree example.cfg
2.16675
2.15574
2.15595
2.17071
2.15465
mean: 2.16076
sanatized mean: 2.15948

“Message” no fim

./array example.cfg
0.720208
0.718758
0.718837
0.717367
0.719027
mean: 0.718839
sanatized mean: 0.718874

./list example.cfg
0.836076
0.837332
0.835622
0.8371
0.837129
mean: 0.836652
sanatized mean: 0.836768

./list-sem_reverse example.cfg
0.752963
0.752791
0.753955
0.754778
0.754702
mean: 0.753838
sanatized mean: 0.753873

./tree example.cfg
2.16553
2.15707
2.15758
2.15895
2.15237
mean: 2.1583
sanatized mean: 2.15787

“Message” inexistente

./array example.cfg
0.720048
0.718647
0.718389
0.720061
0.718486
mean: 0.719126
sanatized mean: 0.71906

./list example.cfg
0.836933
0.836048
0.837255
0.835262
0.836835
mean: 0.836467
sanatized mean: 0.836605

./list-sem_reverse example.cfg
0.7914
0.79624
0.790245
0.788936
0.791683
mean: 0.791701
sanatized mean: 0.791109

./tree example.cfg
2.16843
2.1546
2.1635
2.17302
2.15543
mean: 2.163
sanatized mean: 2.16245

Perceba que a versão das listas sem reverse, a performance de busca fica “invertida”, já que sem inverter a lista, a primeira linha fica por último.

As árvores foram um pouco mais lentas ainda dessa vez, mas isso depende muito do arquivo. Por exemplo, eu criei mais dois arquivos de configuraçao, com o mesmo tamanho, e esses foram os resultados, para apenas lê-los:

./tree example.cfg
2.21104
2.18054
2.16946
2.18486
2.17937
mean: 2.18505
sanatized mean: 2.18159

./tree example2.cfg
2.07847
2.08813
2.09765
2.08891
2.07667
mean: 2.08596
sanatized mean: 2.08517

./tree example3.cfg
2.15432
2.13977
2.14519
2.16794
2.15948
mean: 2.15334
sanatized mean: 2.153

Depois eu tentei rodar tree em um arquivo que tivesse sido colocado em ordem antes da leitura. O problema nesse caso é que ela começa a se comportar como uma lista, e as perdas são enormes, de passar 15 minutos para fazer uma única leitura.

Mas porque então as listas mesmo não sofrem desse mal? É simples: o código das listas usa um método de push, ela empurra novos nós no início da lista, enquanto que as árvores fazem um método de append, elas tem que percorrer toda a lista antes de adicionar um novo nó.

Publicidade

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: