• 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 escrito 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 ressalto 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.

    Este artigo foi publicado originalmente no blog: Dados em Memória no Python, Dicionários ou Listas? iniciado por Magnun
    Sobre o Autor: Magnun


    Comentários 2 Comentários
    1. Avatar de allisonvoll
      allisonvoll -
      Você está fazendo o teste buscando valores em listas, e nos dicionários está fazendo por índices, o que não é uma comparação justa ao meu ver.

      Deveria ser buscado por valores no dicionário da mesma forma que nas listas, neste caso o tempo seria aproximadamente o mesmo pois dicionários nada mais são do que listas indexadas ao estilo hash table, ou então fazer as buscas por índices nas listas também (neste caso nas listas seriam mais rapido).

      Listas e Dicionários são estruturas de dados bem diferentes e para propósitos diferentes, normalmente dicionários são utilizados para algo como o próprio nome sujere, armazenar valores relativos a chave enquanto listas são para armazenar vários de objetos. Um exemplo simples é a própria implementação da orientação a objetos em python, onde cada objeto é na verdade um dicionário com sua chave atrelada á 'métodos' e 'atributos'.

      A um grosso modo dicionários podem ser comparados com 'estruturas' do C e listas com 'vetores' ou 'matrizes' (mas bem mais semelhante o tipo 'List' implementado em C++).

      Se a idéia é persistir estruturas serializáveis, além do pickle você pode utilizar o módulo struct que serializa valores da mesma forma que estruturas são armazenadas em arquivos em C, normalmente utilizado para compatibilidade com aplicativos escritos em outras linguagens, comunicação com dispositivos ou sockets. E poderia representar estas estruturas em python como dicionários ou classes.

      Outra alternativa seria utilizar banco de dados embarcados como o sqlite que já vem junto com o python na maioria das distribuições.
    1. Avatar de Magnun
      Magnun -
      Você está fazendo o teste buscando valores em listas, e nos dicionários está fazendo por índices, o que não é uma comparação justa ao meu ver.
      Sim, não é justa. Como eu falei, essa diferença ocorre somente porque a busca por índices no dicionário está implementada na linguagem. Talvez meu texto não tenha ficado claro, mas minha intenção era mostrar que, ao contrário do que eu esperava, a busca através de iteração na lista é bem rápida.


      Deveria ser buscado por valores no dicionário da mesma forma que nas listas, neste caso o tempo seria aproximadamente o mesmo pois dicionários nada mais são do que listas indexadas ao estilo hash table, ou então fazer as buscas por índices nas listas também (neste caso nas listas seriam mais rapido).
      Se você observar a forma como estruturei a lista, vai perceber que não há como realizar busca na lista utilizando o método index.

      Listas e Dicionários são estruturas de dados bem diferentes e para propósitos diferentes, normalmente dicionários são utilizados para algo como o próprio nome sujere, armazenar valores relativos a chave enquanto listas são para armazenar vários de objetos. Um exemplo simples é a própria implementação da orientação a objetos em python, onde cada objeto é na verdade um dicionário com sua chave atrelada á 'métodos' e 'atributos'.
      Concordo plenamente, mas uma vez que temos diversos objetos nos servindo devemos analisar qual deles mais atende uma dada necessidade. Foi por isso que escrevi esse artigo, visando mostrar que os dicionários são uma ótima solução, desde que sua aplicação não vá rodar em plataformas com pouca memória.

      A um grosso modo dicionários podem ser comparados com 'estruturas' do C e listas com 'vetores' ou 'matrizes' (mas bem mais semelhante o tipo 'List' implementado em C++).

      Se a idéia é persistir estruturas serializáveis, além do pickle você pode utilizar o módulo struct que serializa valores da mesma forma que estruturas são armazenadas em arquivos em C, normalmente utilizado para compatibilidade com aplicativos escritos em outras linguagens, comunicação com dispositivos ou sockets. E poderia representar estas estruturas em python como dicionários ou classes.
      Antes de trabalhar da forma apresentada acima, eu testei o armazenamento de objetos usando o shelve o pickle, mas eles apresentaram uma deficiência. Se eu vier a necessitar adicionar ou remover atributos desse objeto toda a minha base armazenada torna-se inválida. Por isso optei por armazenar em dicionários ou listas. Quanto ao struct, eu o desconhecia, muito obrigado pela dica, vou estudá-lo.

      Outra alternativa seria utilizar banco de dados embarcados como o sqlite que já vem junto com o python na maioria das distribuições.
      Como eu disse no início, eu não quero ter que usar um banco de dados para uma coisa tão simples. Foi o que eu disse no texto, a solução do listas e dicionários atende bem até 2000 ítens. Para valores muito grandes seria mais sensato usar um banco de dados, mas minha aplicação não ai chegar a isso.

      Mas você me deu uma boa idéia de como melhorar as buscas nas listas. Vou escrever um outro artigo sobre isso. Se quiser me ajudar, toda ajuda é bem vinda!

      Até mais...
    + Enviar Comentário

Visite: BR-Linux ·  VivaOLinux ·  Dicas-L