Dados em Memória no Python, Dicionários ou Listas?

Esses dias eu estava desenvolvendo um modulo para o meu novo projeto. Esse novo modulo será responsável por "criar" um banco de dados e uma interface de comunicação. Esse banco de dados irá armazenar informações de alguns hosts de rede e seus detalhes. A interface de comunicação deve ser capaz de prover acesso a todas as informações de um dado host bem como definir métodos de adição, remoção e alteração de hosts.

Algumas pessoas podem se perguntar "por que não usar um banco de dados pronto?". Bem, eu acho que essa aplicação não exige um banco de dados de verdade. Ela só precisa realizar a persistência de alguns dados, buscas e alterações de registro, nada muito complexo.

Em Python, você dispõe de alguns módulos básicos que disponibilizam a possibilidade da serialização de dados. Dentre elas eu destaco o Shelve, o Pickle e o cPickle. Dentre essas eu escolhi o cPickle, uma reimplementação da biblioteca Pickle, que realiza a serialização de objetos ecrito em C. Ele é capaz de ser 1000 vezes mais rápido que o módulo Pickle. Diferentemente do Shelve o cPicke não define uma estrutura padrão para armazenar e recuperar dados, o que me levou a uma questão: Devo recuperar esses dados em uma lista ou em um dicionário?

Antes de responder, nós devemos entender a pergunta. Quais são os parâmetros para decidir qual desses objetos é mais vantajoso? Eu resalto dois quesitos: Tamanho em memória e "tempo de pesquisa".

Primeiramente vamos analisar a ocupação de memória por esses dois objetos:

Código PHP:

>>> from sys import getsizeof as size
>>> d = {}
>>> for n in range(200): 
...  d[str(n)] = ['192.168.1.'+str(n), 'icon'+str(n)+'.jpg', 'campo'+str(n)] 
... 
>>> d['0']
['192.168.1.0', 'icon0.jpg', 'campo0']
>>> size(d)
6284
>>>
>>>
>>> l = [] 
>>> for n in range(200): 
...  l.append([str(n), '192.168.1.'+str(n), 'icon'+str(n)+'.jpg', 'campo'+str(n)])
...
>>> l[0]
['0', '192.168.1.0', 'icon0.jpg', 'campo0']
>>> size(l)
840
>>>
>>> float(size(d))/size(l) 
7.480952380952381 


No código acima, primeiramente eu importei a função getsizeof do módulo sys renomeando-a para size. Depois eu criei um dicionário com o conteúdo variado, conforme mostrado na linha a seguir. Depois podemos verificar que esse objeto ocupou 6284 bytes. Em seguida criei uma estrutura semelhante utilizando uma lista, que ocupou 840 bytes. Dessa forma podemos ver que uma lista ocupa menos espaço em memória que um dicionário. Ao realizar uma comparação podemos ver que o dicionário chegou a ocupar quase 7.5 vezes mais espaço em memória que uma lista.

Continuando a execução do código anterior, vamos fazer testes de consulta nessas estrutura.

Código PHP:

>>> import random 
>>> import time 
>>> 
>>> def busca_na_lista(nome, lista):
...  for item in lista:
...   if item[0] == nome:
...    return item
...
>>>
>>> def busca_no_dicionario(nome, dicionario):
...  return dicionario[nome]
... 
>>>  
>>> def teste_lista(n_buscas, lista):
...  tamanho = len(lista)
...  vetor_aleatorio = [random.randrange(0, tamanho) for i in range(n_buscas)]
...  inicio = time.time()
...  for n in vetor_aleatorio:
...   x = busca_na_lista(str(n), lista)
...  fim = time.time()
...  print 'Inicio em: %s\tFim em: %s'%(inicio, fim)
...  return fim - inicio
...
>>>
>>> def teste_dicionario(n_buscas, dicionario):
...  tamanho = len(dicionario)
...  vetor_aleatorio = [random.randrange(0, tamanho) for i in range(n_buscas)]
...  inicio = time.time()
...  for n in vetor_aleatorio:
...   x = busca_no_dicionario(str(n), dicionario)
...  fim = time.time()
...  print 'Inicio em: %s\tFim em: %s'%(inicio, fim)
...  return fim - inicio
... 
>>> 
>>> teste_lista(200, l)
Inicio em: 1277733024.04        Fim em: 1277733024.04
0.0
>>> teste_dicionario(200, d)
Inicio em: 1277733041.37        Fim em: 1277733041.37
0.0
>>> 
>>> 
>>> teste_lista(2000, l)
Inicio em: 1277735153.49        Fim em: 1277735153.5
0.016000032424926758
>>> teste_dicionario(2000, d)
Inicio em: 1277735159.19        Fim em: 1277735159.19
0.0
>>> 
>>> 
>>> teste_lista(200000, l)
Inicio em: 1277735175.41        Fim em: 1277735177.06
1.6559998989105225
>>> teste_dicionario(200000, d)
Inicio em: 1277735181.16        Fim em: 1277735181.24
0.078000068664550781
>>>
>>> 
>>> teste_lista(200000, l) - teste_dicionario(200000, d)
Inicio em: 1277735213.7 Fim em: 1277735215.22
Inicio em: 1277735215.52        Fim em: 1277735215.6
1.437999963760376
>>> teste_dicionario(200000, d)/teste_lista(200000, l)
Inicio em: 1277735219.72        Fim em: 1277735219.8
Inicio em: 1277735220.1 Fim em: 1277735221.61
0.051485190272963291
>>>
>>> 


Primeiro eu criei duas funções busca_na_lista e busca_no_dicionario. Em seguida criei duas funções de teste teste_lista, teste_dicionario. Em ambas são passados como argumento um numero de buscas e a estrutura que será buscada. A função time.time() é utilizada para gravar o tempo em segundos daquele instante, a subtração desse valores informa o tempo de busca. A função random.randrange é utilizado para gerar números aleatórios entre 0 e o tamanho da lista (nesse caso é 200) durante a busca. Podemos ver que ao realizar 200 buscas não é notado diferença de desempenho. Eu realizei mais alguns testes e até 800 buscas não havia diferença de tempo. Como esse teste depende muito das configurações da máquina é possível que os testes apresentem resultados diferentes. Com 2000 pesquisas é possível ver que a diferença ainda é pouca (0.016 segundos). Já no teste com 200000 buscas na lista vemos um aumento no tempo de resposta para pouco mais de 1 segundo (1.655 segundos) enquanto a mesma busca no dicionário leva 0.078 segundos.

Com esses dados tenho algumas conclusões:
1. Buscas em listas são mais rápidas do que eu imaginei;
2. Buscas em dicionários são incrivelmente rápidas;
3. Dicionários ocupam grandes espaços em memória;
4. Listas são muito boas para economia de memória.

Dado o conhecimento que tenho, arrisco afirmar que a lentidão das buscas em listas é causada somente pela forma que a busca é realizada. Como o dicionário já possui a busca embutida ela é extremamente mais rápida por ser um código escrito em C e compilado. O lado negativo do dicionário é que você pode acabar consumindo todo o recurso de memória da sua plataforma e prejudicando assim o tempo de busca, levando a um desempenho inferior ao que seria com as listas.

Desta forma, quem busca muito desempenho e possui recursos de memória sobrando utilize dicionários (com moderação). Se sua aplicação deve rodar em dispositivos com pouca memória desaconselho o uso de dicionários. Se quiser algo realmente rápido, talvez seja interessante escrever esse "trecho de interface" em Cython o que possivelmente garantirá um pouco mais de desempenho.