6

Eu uso muito dicionários em Python:

dic = dict() #ou
dic = {}

dic['113654'] = {'nome': 'João', 'idade': 21}
dic['853872'] = {'nome': 'Maria', 'idade': 27}
dic['427845'] = {'nome': 'Fernando', 'idade': 33}
dic['720720'] = {'nome': 'Lucas', 'idade': 16}

Eles facilitam muito verificar se uma chave existe e pegar seu valor:

cod = '853872'
if cod in dic:
    return dic[cod]

Minha pergunta é: usar dicionários dessa forma é eficiente? Dicionários em Python implementam uma maneira eficiente de encontrar as chaves (hash, árvore, etc.)? Ou quando meu dicionário ficar muito grande convém usar uma estrutura de dados mais tradicionalmente eficiente como uma árvore ou um hash por exemplo?

1 Resposta 1

7

A implementação interna do dicionário de Python é usando tabelas hash, então tem complexidade O(1) para achar chaves, isto pode ser confirmado na wiki oficial de Python (obrigado ao AlexCiuffa).

Ele é, em tese, e em quase todas as situações, mais rápida que uma árvore que tem complexidade O(log n), mas ele não pode ter as chaves naturalmente classificadas como uma árvore pode, e não pode ter chaves repetidas. Um dicionário era não "ordenado". Segundo o jsbueno abaixo em comentário agora ele consegue ser ordenado usando uma estrutura auxiliar, então mantém o O(1) para acesso ao elemento e consegue atravessar todos elementos na ordem que foram inseridos, ao custo de ocupar mais espaço que poderia, o que para Python não é um grande problema porque já fazia isto antes. Ele ainda é não classificado e só poderia ser assim de forma eficiente com uma árvore ou algo parecido.

Coloquei no GitHub para referência futura.

10
  • Fontes que suportam essa resposta (e uma referência para quem quiser aprofundar neste assunto) são: wiki.python.org/moin/TimeComplexity (complexidade da busca em dicionário e outras estruturas) e wiki.python.org/moin/DictionaryKeys (mostra como o dicionário funciona e como utiliza hash).
    – AlexCiuffa
    Commented 29/05/2019 às 22:33
  • Se ele é basicamente um hash já resolve meu problema. Muito obrigado! Commented 29/05/2019 às 22:42
  • @AlexCiuffa links excelentes! Commented 29/05/2019 às 22:43
  • 1
    Sobre não ser ordenado - o código dos dicionários de Python foi refatorado na versão 3.6, e a partir da 3.7 foi oficializado que os dicionários respeitam a ordem de inserção de chaves - (como o collections.OrderedDict, que agora vai para o museu)
    – jsbueno
    Commented 31/05/2019 às 15:26
  • @jsbueno então isso quer dizer que ele não é mais um hash e sim uma árvore ou algo parecido, e portanto não tem mais como ser O(1), pode ser O(logN) ou O(N), o que seria terrível e duvido que seja, ou ainda para ser O(1) teria duas estruturas, uma para garantir a ordem e outra para dar a O(1), o que ocuparia muito espaço.
    – Maniero
    Commented 31/05/2019 às 15:29

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .