2.7. Dicionários¶

O dicionário é outra das estruturas de dados principais do Python. Como você provavelmente se lembra, a diferença entre dicionários e listas é que você pode acessar itens em um dicionário através de uma chave ao invés de uma posição. Em capítulos futuros neste livro você verá que há diversas maneiras de implementar um dicionário. O mais importante agora é perceber que os operadores de acesso e atribuição a um item de um dicionário são \(O(1)\). Outro operador importante em dicionários é o operador contém (in). Verificar se uma chave está no dicionário ou não também é \(O(1)\). A eficiência de todas as operações de dicionário está resumida em Table 3. É importante notar que as eficiências apresentadas na tabela são performances médias. Em alguns casos raros as operações contém, acessar e atribuir item se tornam \(O(n)\), mas discutiremos isso em capítulos futuros quando falamos sobre as diferentes maneiras como um dicionário poderia ser implementado.

Para o nosso último experimento vamos comparar a performance do operador contém entre listas e dicionários. Durante o processo vamos confirmar que o operador contém para listas é \(O(n)\) e o operador contém para dicionários é \(O(1)\). O experimento que realizaremos para comparar as duas operações é simples. Vamos criar uma lista com uma determinada quantidade de números. Então vamos escolher números aleatórios e verificar se esses números estão na lista. Se nossa tabela de performances está correta, quanto maior a lista, mais tempo deve ser necessário para determinar se qualquer número está contido nela.

Vamos repetir o mesmo experimento para um dicionário que contém números como chaves. Nesse experimento deveríamos ver que determinar se um número está ou não no dicionário é, não somente muito mais rápido, mas também o tempo necessário para a verificação deve permanecer constante mesmo se o dicionário aumentar em tamanho.

Listing 6 implementa essa comparação. Note que estamos realizando exatamente a mesma operação, número in x. A diferença é que na linha 7 x é uma lista e na linha 9 x é um dicionário.

Listing 6

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import timeit
import random

for i in range(10000,1000001,20000):
    t = timeit.Timer("random.randrange(%d) in x"%i,
                     "from __main__ import random,x")
    x = list(range(i))
    tempo_lista = t.timeit(number=1000)
    x = {j:None for j in range(i)}
    tempo_dic = t.timeit(number=1000)
    print("%d,%10.3f,%10.3f" % (i, tempo_lista, tempo_dic))

A Figura 4 resume os resultados da execução de Listing 6. Você pode ver que o dicionário é consistentemente mais rápido. Para a menor lista, com 10.000 elementos, o dicionário é 89,4 vezes mais rápido do que a lista. Para o maior tamanho, de 990.000 elementos, o dicionário é 11.603 vezes mais rápido! Você também pode ver que o tempo necessário para o operador contém na lista cresce linearmente com o tamanho da lista. Isso verifica a afirmação de que o operador contém em uma lista é \(O(n)\). Também é possível ver que o tempo para o operador contém no dicionário é constante, mesmo conforme o dicionário cresce. De fato para um dicionário de tamanho 10.000 o operador contém levou 0.004 milissegundos e para o dicionário de tamanho 990.000 ele também levou 0.004 milissegundos.

Figura 4: Comparando o Operador contém (in) para Listas e Dicionários em Python¶

Como Python é uma linguagem em evolução, sempre há mudanças ocorrendo por trás dos panos. A informação atualizada sobre a performance de estruturas de dados do Python pode ser encontrada na página do Python. No momento da escrita deste texto a wiki do Python possui uma página bastante interessante sobre a complexidade de tempo, que pode ser encontrada em Time Complexity Wiki.