Ver Feed RSS

root@blog:/# chmod o+r *

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

Avalie este Post de Blog
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
>>> = {}
>>> 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
>>>
>>>
>>> 
= [] 
>>> 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(nomelista):
...  for 
item in lista:
...   if 
item[0] == nome:
...    return 
item
...
>>>
>>> 
def busca_no_dicionario(nomedicionario):
...  return 
dicionario[nome]
... 
>>>  
>>> 
def teste_lista(n_buscaslista):
...  
tamanho len(lista)
...  
vetor_aleatorio = [random.randrange(0tamanho) for i in range(n_buscas)]
...  
inicio time.time()
...  for 
n in vetor_aleatorio:
...   
busca_na_lista(str(n), lista)
...  
fim time.time()
...  print 
'Inicio em: %s\tFim em: %s'%(iniciofim)
...  return 
fim inicio
...
>>>
>>> 
def teste_dicionario(n_buscasdicionario):
...  
tamanho len(dicionario)
...  
vetor_aleatorio = [random.randrange(0tamanho) for i in range(n_buscas)]
...  
inicio time.time()
...  for 
n in vetor_aleatorio:
...   
busca_no_dicionario(str(n), dicionario)
...  
fim time.time()
...  print 
'Inicio em: %s\tFim em: %s'%(iniciofim)
...  return 
fim inicio
... 
>>> 
>>> 
teste_lista(200l)
Inicio em1277733024.04        Fim em1277733024.04
0.0
>>> teste_dicionario(200d)
Inicio em1277733041.37        Fim em1277733041.37
0.0
>>> 
>>> 
>>> 
teste_lista(2000l)
Inicio em1277735153.49        Fim em1277735153.5
0.016000032424926758
>>> teste_dicionario(2000d)
Inicio em1277735159.19        Fim em1277735159.19
0.0
>>> 
>>> 
>>> 
teste_lista(200000l)
Inicio em1277735175.41        Fim em1277735177.06
1.6559998989105225
>>> teste_dicionario(200000d)
Inicio em1277735181.16        Fim em1277735181.24
0.078000068664550781
>>>
>>> 
>>> 
teste_lista(200000l) - teste_dicionario(200000d)
Inicio em1277735213.7 Fim em1277735215.22
Inicio em
1277735215.52        Fim em1277735215.6
1.437999963760376
>>> teste_dicionario(200000d)/teste_lista(200000l)
Inicio em1277735219.72        Fim em1277735219.8
Inicio em
1277735220.1 Fim em1277735221.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.
Categorias
Python , Artigos , Artigos , Projetos , Tutoriais

Comentários

  1. Avatar de PEdroArthurJEdi
    E aí, Magnum, tudo na paz?

    Tanto as questões da quantidade de memória e do tempo de busca são relativas a natureza das estruturas.

    Uma lista é um encadeamento de valores. Assim, para encontrar um valor numa lista, você tem que percorrê-la do início ao fim, tal qual está no seu código. Em relação ao consumo de memória, as listas precisam apenas do espaço necessário para armazenar os valores e um indicador (ponteiro) para a próxima posição.

    Os dicionários podem ser implementados através de diferentes abordagens. A que o Python se utiliza é baseado no conceito de tabelas hash.

    Uma função hash mapeia um dado de entrada em um valor numérico único. Uma tabela hash é uma estrutura de dados que se utiliza de funções hash para que a busca de dados seja feita de maneira mais rápida. Para isso, as tabelas hash pré-alocam vetores vazios para que sejam utilizados como espaço de armazenamento para as chaves e os dados. Abaixo vai um exemplo de uma tabela hash.

    th[0]: null
    th[1]: null
    th[2]: null
    th[3]: null
    th[4]: null

    Assim, quando uma chave e valor são adicionados, digamos "asd" valor 10, a chave passa por uma função hash para determinar a posição que será inserida. Digamos que h(x) seja a função e que h("asd") = 3. Ao inserir na nossa tabela, ela ficará:

    th[0]: null
    th[1]: null
    th[2]: null
    th[3]: [ ("asd", 10) ]
    th[4]: null

    Para buscar, basta passar a chave "c" para a função h e verificar se ela está presente na posição h(c). Caso sim, retorna o dado. Caso não, retorna nulo. Ou seja, bem mais rápido do que procurar um por um.

    A maior quantidade de memória necessária é relativa a pré-alocação dos vetores, arranjos, lista, ou qualquer outra estrutura, para armazenar os dados e as chaves.
  2. Avatar de Magnun
    E ai PEdroArrthurJEdi,

    Suas explicações são sempre incríveis. Eu realmente devia ter abordado dessa forma antes de explicar. Mas o meu post na verdade não foi nem pra esclarecer esse tipo de assunto, mas pra fazer uma comparação entre os tempos de busca e espaço em memória. O que mais me chamou a atenção foi o fato da iteração pela lista não ficar tão atrás da busca do dicionário (quando fazemos menos de 700~800 buscas). Eu pessoalmente achei que em 200 buscas já seria mostrado uma grande diferença.

    Em conversas com outros usuários, formulei uma nova forma de busca para as listas, em breve estarei postando aqui!

    Obrigado pelo comentário e até a próxima.
  3. Avatar de PEdroArthurJEdi
    Aparentemente, as listas de Python não são implementadas através de ponteiros. São vetores que o interpretador redimensiona conforme o necessário. Logo, os dados estão em regiões contíguas. Se você criar uma lista vazia e for adicionando ítens e medindo o tamanho dela, verá que é alocado mais espaço do que o necessário. Então, não é de se espantar que o tempo de percorrê-las seja baixo.
  4. Avatar de Magnun
    Realmente, você parece estar certo:
    Código :
    >>> l = [1,2,3,4,5,6]
    >>> l1 = []
    >>> l1.append(1)
    >>> l1.append(2)
    >>> l1.append(3)
    >>> l1.append(4)
    >>> l1.append(5)
    >>> l1.append(6)
    >>> from sys import getsizeof as size
    >>> size(l)
    60
    >>> size(l1)
    68
    >>> l
    [1, 2, 3, 4, 5, 6]
    >>> l1
    [1, 2, 3, 4, 5, 6]
    >>>

+ Enviar Comentário



Visite: BR-Linux ·  VivaOLinux ·  Dicas-L