8

Tenho um dicionário da sequinte forma:

dicionario = {'1':'Banana','7':'Maçã','3':'Pera','2':'Melancia'}

Se eu verificar a chave '2' no dicionário: if '2' in dicionario:. Minha intuição de programador me diz que a complexidade desse comando é O(n) no pior caso, pois existem n elementos dentro desse dicionário. Porém isso é um dicionário e não uma lista e não sei exatamente como as "engrenagens mágicas" do dicionário do python funcionam.

A complexidade de realizar uma busca em um determinado item do dicionário seja procurando a chave como eu fiz ou acessando o elemento direto: dicionario['2'] possui complexidade O(n)? Ou existe um Hash dentro dessas "engrenagens" ou alguma estrutura que consegue optimizar essa busca, como a busca binária?

Em falar em busca binária, há alguma forma de acessar o elemento de um dicionário como eu fiz e ativar uma busca binárias nas "engrenagens" do dicionário considerando, é claro, que ele esteja ordenado?

3
  • 1
    O dicionário é implementado como hash table e no acesso direto a complexidade é O(1). Ver docs.python.org/2/faq/…
    – bfavaretto
    Commented 24/01/2018 às 17:30
  • ponha o link para a docuementação do Python 3. O google é último lugar do mundo que fica com esses links para a documentação do Python 2 ainda - só que ele só vai melhorar se os links que a gente põe pela internet forem para a versão 3.
    – jsbueno
    Commented 24/01/2018 às 20:19
  • docs.python.org/3/faq/…
    – jsbueno
    Commented 24/01/2018 às 20:19

2 Respostas 2

9

Até onde eu sei as duas formas de acessar uma chave no dicionário são basicamente equivalentes (claro uma retorna um booleano da existência e o outro retorna o valor, mas ambas conseguem tempo O(1), na maioria dos casos (tem casos extremos que pode ser O(n), mas que não chegam nem perto de ocorrer)).

Dicionários são tabelas de espalhamento, elas possuem performance quase ao do array para acesso aleatório, só perde um pouco porque precisa calcular o código hash antes de acessar o elemento. Existem casos de colisão de chaves onde a busca precisa ser feita de outra forma, podendo até mesmo chegar em complexidade O(n).

Um dicionário é quase o oposto de uma estrutura que permite busca binária. Um dicionário não pode estar nem ordenado (com regra específica), muito menos classificado (com critério determinado).

No exemplo tenho dúvidas se um array não seria a melhor escolha.

Tanto o array,quanto o dicionário terá complexidade O(n) para procurar por valores.

Já demonstrei que o dicionário é diferente do array.

Pode ser útil: Objetos são semelhantes a arrays?.

Coloquei no GitHub para referência futura.

5

Como está nos comentários e na outra resposta, dicionários em Python são uma tabela de hash, com tempo de busca O(1) - e a informação sobre isso está aqui: https://docs.python.org/3/faq/design.html#how-are-dictionaries-implemented

Dito isso, sobre o design de código que você pergunta - chave in dict vs dict[chave]: o tempo de acesso é o mesmo - só que se a chave não existir, a segunda forma levanta uma exceção.

Quando você vai recupear um valor que não tem certeza se existe no dicionário o recomendado é usar o método .get:

meu_valor = dicionario.get("chave") 

Nesse caso, se "chave" não existir, o .get retorna None e a vida continua. O .get também aceita um segundo parâmetro que é o retornado quando a chave não existe, em vez de None.

Isso economiza linhas de código - do tipo

if chave in dicionario:
    valor = dicionario[chave]
else: 
    valor = None

ou

try:
   valor = dicionario[chave]
except KeyError:
   valor = None

Desses, esse segundo caso seria o único que teria alguma diferença de performance, por conta do tempo de criação do contexto do try/except . Veja também o método .setdefault dos dicts: eles não só recuperam um valor padrão caso não exista um - mas nesse caso, fazem a atribuição do novo valor. Por exemplo, um loop para criar um dicionário com todas as palavras de um texto e a posição de cada palavra dentro do mesmo, numa lista, poderia ser:

palavras = texto.split()
posicoes = {}
for indice, palavra in enumerate(palavras):
    posicoes.setdefault(palavra, []).append(indice)

Nesse caso, se a palavra ainda não foi encontrada, é criada uma lista vazia que é ao mesmo tempo atribuida lá e retornada pelo método. Se posicoes[palavra] já existe, a lista existente é retornada.

Agora, já que você se interessa por isso e quer saber sobre busca binária, aqui vai o fato interessante: o Python tem uma interface bem definida para objetos do tipo "Mapping" - e é bme tranquilo implementar um objeto que se comporte exatamente como um dicionário, mas com os algoritmos internos que você decidir. Se você quiser criar um dicionário que internamente seja uma árvore binária, é bem fácil - a forma recomendada de se fazer isso é herdar a classe collections.abc.MutableMapping. Há várias classes em collections.abc que são a base para implementar estruturas de dados bem uteis e variadas. Uma árvore binaria teria busca O(log(n)), mas com a vantagem de você poder ter ordenação das chaves e poder usar slices na mesma, por exemplo. Confira em: https://docs.python.org/3/library/collections.abc.html

Eu tenho vários "superdicionários" implementados no módulo extradict - alguns são mais de brinquedo, outros eu uso mesmo em produção:

https://github.com/jsbueno/extradict

1
  • Sobre o extradict: eu não uso nada Python em produção, mas ja aprendi muito com esse projeto Commented 25/01/2018 às 0:36

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 .