20. Dicionários¶
Dicionários são a estrutura de dados mais importantes do universo! 😏 Nada como exagerar para chamar a atenção. 😄 Dicionários são muito usados e têm um papel primordial em várias aplicações cotidianas. Dependendo do contexto, dicionários também são chamados de Tabelas de Símbolos (Symbol Tables), Vetores Associativos (Associative arrays) e Mapas (Maps).
20.1. Objetivos de aprendizagem¶
Aprender conceitos que envolvem dicionários. Implementar algumas versões de dicionários para nos tornarmos melhores usuários de dicionários que são nativos em várias linguagens de programação.
Praticar, ao longo do caminho, rudimentos de análise de algoritmos e análise experimental de algoritmos. Tudo isso terá como pano de fundo o problema de contar a frequência de cada palavra em uma lista de palavras (dada através de um arquivo). Na solução desse problema o uso de dicionários tem um papel soberano.
20.2. Introdução¶
Um dicionário é uma tabela com duas colunas: uma coluna de chaves (= keys) e uma de valores (= values). Dizemos que cada linha da tabela é um item do dicionário, formado por um par chave-valor. Portanto, cada item associa um valor a uma chave.
Um exemplo simples é a tabela que associa os nomes de todas as alunas e alunos da USP aos seus números USP.
Um outro exemplo de dicionário é a tabela que associa as palavras em um texto ao número de vezes que cada palavra ocorre no texto. Para o texto abaixo (que se encontra sem acentos para simplificar seu processamento):
Fracassei em tudo o que tentei na vida.
Tentei alfabetizar as criancas brasileiras, nao consegui.
Tentei salvar os indios, nao consegui.
Tentei fazer uma universidade seria e fracassei.
Tentei fazer o Brasil desenvolver-se autonomamente e fracassei.
Mas os fracassos sao minhas vitorias.
Eu detestaria estar no lugar de quem me venceu
Darci Ribeiro
temos o dicionário
20.3. Classe Dicio¶
Um pouco mais precisamente, um dicionário é um Tipo de Dados ou classe que consiste em um conjunto de itens, sendo cada item um par (chave, valor), munido de duas operações fundamentais:
put(), que insere um novo item no conjunto, eget(), que busca o valor associado a uma dada chave.
Para ilustrar o uso da classe Dicio, considere a função crie_dicionario() como abaixo.
Nesse caso constumamos dizer que crie_dicionário() é cliente da classe Dicio.
def crie_dicionario(lst, n):
'''(list, int) -> Dicio
RECEBE uma lista lst e um inteiro n.
CRIA e RETORNA um dicionário em que cada chave é um elemento da lista[0:n]
e o valor associado é o número de vezes que o item ocorre lst[0:n].
'''
# cria um dicionário vazio
dicio = Dicio()
for i in range(n):
# pega o valor associado a chave lst[i]
valor = dicio.get(lst[i])
# se valor == None, lst[i] não estava no dicionário
if valor == None:
# insira o item (lst[i], 1) no dicionário
dicio[lst[i]] = 1
else:
# atualize o item no dicionário
dicio[lst[i]] = valor + 1
return dicio
20.4. Comportamento¶
Ao ser criado, um objeto Dicio representa um dicionário vazio.
In [2]: d = Dicio()
In [3]: print(d) # note a linha vazia a seguir
In [4]:
Como sempre, a string utilizada quando escrevemos print(d) é aquela retornada pelo método mágico __str__()
que retorna uma string que representa d.
Um item, ou seja, par (chave, valor) pode ser inserido em um dicionário de duas formas diferentes.
Uma delas é usando o método put():
In [4]: d.put('fracassei', 3)
In [5]: d.put('em', 1)
In [6]: d.put('tudo', 1)
In [7]: print(d)
fracassei: 3
em: 1
tudo: 1
A outra maneira é semelhante a mudarmos o valor de um elemento de uma lista.
Esse comportamento é de responsabilidade do já visto método mágico __setitem__().
In [8]: d['o'] = 2
In [9]: d['que'] = 3
In [10]: d['tentei'] = 4
In [11]: print(d)
fracassei: 3
em: 1
tudo: 1
o: 2
que: 3
tentei: 4
Bacana, né?! 😎
Podemos atualizar o valor associado a uma chave procedendo da mesma forma que inserimos um item no dicionário.
In [12]: d.put('o', 2)
In [13]: d['que'] = 1
In [14]: d['tentei'] = 5
In [15]: print(d)
fracassei: 3
em: 1
tudo: 1
o: 2
que: 1
tentei: 5
Para obtermos, ou, como dizem, buscar o valor associado a uma chave usamos o método get().
In [16]: d.get('fracassei')
Out[16]: 3
In [17]: d.get('em')
Out[17]: 1
In [18]: d.get('tudo')
Out[18]: 1
Podemos ainda manipular dicionários como listas.
Essa característica é de responsabilidade do conhecido método mágico __getitem__().
In [19]: d['o']
Out[19]: 2
In [20]: d['que']
Out[20]: 1
In [21]: d['tentei']
Out[21]: 5
Esses métodos retornam None se a chave não estiver no dicionário:
In [27]: print(d.get('vida'))
None
In [28]: print(d['vida'])
None
Tenha em mente que as chaves de dicionários não precisam ser da classe str e nem os valores da classe int.
O que acontece é que, como no problema que trataremos mais a frente, as chaves são da classe str e os valores são da classe int, os nossos exemplos estão concentrados nesses tipos mas poderia ser diferente:
In [29]: d[1] = 'na'
In [30]: d[2] = 'vida'
In [31]: print(d)
fracassei: 3
em: 1
tudo: 1
o: 2
que: 1
tentei: 5
1: na
2: vida
Como você pode observar, em um dicionário podemos ter valores repetidos, entrentanto as chaves são únicas! Faz sentido, certo?! 🤔
Para sabermos se uma chave pertence a um dicionário podemos utilizar o operador in, de maneira semelhante ao que fazemos
com objetos da classe list. Essa é uma característica patrocinada pelo método mágico __contains__():
In [32]: 'tentei' in d
Out[32]: True
In [33]: '1' in d
Out[33]: False
In [34]: 1 in d
Out[34]: True
In [35]: 5 in d
Out[35]: False
Essa funcionalidade nos faz lembrar de comandos de repetição como for i in range(n): ... e
for elemento in lista:....
Com o patrocínio do método mágico __iter__() podemos proceder de maneira semelhante com dicionários:
In [36]: for chave in d: print(f"{chave}: {d[chave]}")
fracassei: 3
em: 1
tudo: 1
o: 2
que: 1
tentei: 5
1: na
2: vida
Dá hora! 😎
Graças ao conhecido método mágico __len__() podemos saber o número de itens em um dicionário.
Em particular, se len(objeto_Dicio) é zero, então objeto_Dicio é um dicinário vazio.
In [37]: len(d)
Out[37]: 8
In [38]: objeto_Dicio = Dicio()
In [39]: len(objeto_Dicio)
Out[39]: 0
Por fim, objetos da classe Dicio têm ainda três outros métodos que podem ser bem úteis, inclusive para testarmos nossas implementações.
Esses métodos são:
keys()que retorna a lista de chaves do dicionário;values()que retorna a lista de valores do dicionário; eitems()que retorna a lista dos itens do dicionário.
In [54]: d.keys()
Out[54]: ['fracassei', 'em', 'tudo', 'o', 'que', 'tentei', 1, 2]
In [55]: d.values()
Out[55]: [3, 1, 1, 2, 1, 5, 'na', 'vida']
In [56]: d.items()
Out[56]:
[('fracassei', 3),
('em', 1),
('tudo', 1),
('o', 2),
('que', 1),
('tentei', 5),
(1, 'na'),
(2, 'vida')]
20.5. Implementação¶
Passaremos agora à implementação da classe Dicio.
No esqueleto que está adiante há muitos métodos completamente implementados como __init__() e __str__().
Observe o comportamento dos métodos implementados.
Você deverá implementar alguns outros métodos que fazem parte do motor da classe Dicio.
Em particular você deverá implementar o método administrativo indice() e os métodos put() e get().
Chamamos um método de administrativo se ele trabalha atrás do balcão, mantendo as coisas em ordem e funcionando, mas que não são conhecidos pelo público geral, as clientes da classe. Na verdade, esses métodos administrativos nem são de interesse desse público.
Para as clientes de uma classe os métodos que importam são aqueles que fazem parte da chamada interface de programação do aplicativo (Application Programming Interface, API) da classe.
O arquivo main.py tem uma função main() no final que é uma unidade de teste para sua classe.
20.6. Testes¶
Para testar a sua implementação você pode utilizar a função main() a seguir.
def main():
'''
Unidade de teste para a classe Dicio
'''
print("Testes para a classe Dicio")
print("--------------------------\n")
# __init__() e __str__()
print("crie um dicionário vazio")
d = Dicio()
print(f"d:\n{d}")
pause() # aprecie a paisagem
# put()
print("\nteste put()")
d.put('fracassei', 3)
d.put('em', 1)
d.put('tudo', 1)
print(f"d:\n{d}")
pause() # aprecie a paisagem
# __setitem__()
print("\nteste __setitem__()")
d['o'] = 2
d['que'] = 3
d['tentei'] = 4
print(f"d:\n{d}")
pause() # aprecie a paisagem
# put() e __setitem__()
print("\nteste put() e __setitem__()")
d.put('o', 2)
d['que'] = 1
d['tentei'] = 5
print(f"d:\n{d}")
pause() # aprecie a paisagem
# get()
print("\nteste get()")
print(f"d.get('fracassei')={d.get('fracassei')}")
print(f"d.get('em')={d.get('em')}")
print(f"d.get('tudo')={d.get('tudo')}\n")
pause() # aprecie a paisagem
# __getitem__()
print("\nteste __getitem__()")
print(f"d['o']={d['o']}")
print(f"d['que']={d['que']}")
print(f"d['tentei']={d['tentei']}")
print(f"d.get('vida')={d.get('vida')}")
print(f"d['vida']={d['vida']}\n")
pause() # aprecie a paisagem
# mais __setitem__()
print("\nmais teste __setitem__()")
d[1] = 'na'
d[2] = 'vida'
print(f"d:\n{d}")
pause() # aprecie a paisagem
# teste __contains__()
print("\nteste __contains__()")
print(f"'tentei' in d={'tentei' in d}")
print(f"'1' in d={'1' in d}")
print(f"1 in d={1 in d}")
print(f"5 in d={5 in d}\n")
pause() # aprecie a paisagem
# teste __iter__()
print("\nteste __iter__()")
for chave in d: print(f"{chave}: {d[chave]}")
pause() # aprecie a paisagem
# teste __len__()
print("\nteste __len__()")
print(f"len(d)={len(d)}")
dicio_vazio = Dicio()
print(f"len(dicio_vazio)={len(dicio_vazio)}\n")
pause() # aprecie a paisagem
# teste keys(), values() e items()
print("\nteste keys(), values() e items()")
print(f"d.keys()={d.keys()}")
print(f"d.values()={d.values()}")
print(f"d.items()={d.items()}\n")
pause() # aprecie a paisagem
print("FIM")
A saída esperada produzida pela função main() está logo a seguir
Testes para a classe Dicio
--------------------------
crie um dicionário vazio
d:
Tecle ENTER para continuar:
teste put()
d:
fracassei: 3
em: 1
tudo: 1
Tecle ENTER para continuar:
teste __setitem__()
d:
fracassei: 3
em: 1
tudo: 1
o: 2
que: 3
tentei: 4
Tecle ENTER para continuar:
teste put() e __setitem__()
d:
fracassei: 3
em: 1
tudo: 1
o: 2
que: 1
tentei: 5
Tecle ENTER para continuar:
teste get()
d.get('fracassei')=3
d.get('em')=1
d.get('tudo')=1
Tecle ENTER para continuar:
teste __getitem__()
d['o']=2
d['que']=1
d['tentei']=5
d.get('vida')=None
d['vida']=None
Tecle ENTER para continuar:
mais teste __setitem__()
d:
fracassei: 3
em: 1
tudo: 1
o: 2
que: 1
tentei: 5
1: na
2: vida
Tecle ENTER para continuar:
teste __contains__()
'tentei' in d=True
'1' in d=False
1 in d=True
5 in d=False
Tecle ENTER para continuar:
teste __iter__()
fracassei: 3
em: 1
tudo: 1
o: 2
que: 1
tentei: 5
1: na
2: vida
Tecle ENTER para continuar:
teste __len__()
len(d)=8
len(dicio_vazio)=0
Tecle ENTER para continuar:
teste keys(), values() e items()
d.keys()=['fracassei', 'em', 'tudo', 'o', 'que', 'tentei', 1, 2]
d.values()=[3, 1, 1, 2, 1, 5, 'na', 'vida']
d.items()=[('fracassei', 3), ('em', 1), ('tudo', 1), ('o', 2), ('que', 1), ('tentei', 5), (1, 'na'), (2, 'vida')]
Tecle ENTER para continuar:
FIM
20.7. Arquivos¶
Para testar essa implementação e medir sua eficiência é desejável que criemos dicionários automaticamente a partir de arquivos.
A função que nos ajudará nessa tarefa é a pegue_palavras():
def pegue_palavras(nome_arq):
'''(str) -> list
RECEBE uma string nome_arq que é o nome de um arquivo.
RETORNA uma lista com as strings que correspondem às palavras que estão no arquivo.
PRÉ-CONDIÇÃO: as palavras no arquivo devem estar separadas por ' ' ou '\n'.
'''
try:
# abra o arquivo
arq_entrada = open(nome_arq, 'r', encoding='utf-8')
except:
print(f"ERRO: arquivo '{nome_arq}' não encontrado.")
return None
print("lendo as palavras do arquivo")
# LEIA o texto no arquivo
texto = arq_entrada.read()
# FECHE o arquivo
arq_entrada.close()
# FIM da leitura
print("leitura encerrada")
# CRIE lista de palavras
print("criando listas de palavras...")
lst_pals = texto.split()
print("lista de palavras criada")
return lst_pals
Alguns arquivos foram preparados sob medida para que pegue_palavras() retorne a lista de palavras contidas neles.
Esses arquivos têm a extensão .pal e podem ser baixados daqui.
São eles