Estruturas de Dados para Grande Quantidade de Dados

Prévia do material em texto

Roteiro da Aula 06 
 
Estruturas de Dados 
Grande quantidade de dados armazenados em aplicações do tipo: 
 
• Lojas on-line 
• Redes sociais 
• Sites de busca 
• ... 
 
Princípios 
 
Quais são os conceitos associados à aplicação? 
Os conceitos do domínio normalmente dão origem às classes da aplicação. 
Os verbos usados para descrever o domínio normalmente dão origem aos métodos das classes. 
 
 Conceitos → Classes 
 Verbos → Métodos 
 
Outro conceito normalmente presente no projeto de suas estruturas de dados é o conceito de identificador 
único. 
 
Exemplos: 
O DRE de um aluno, o ISBN de um livro, o username no Facebook, etc. 
 
No exercício da popularidade de nomes, o identificador único era o próprio nome, e o valor associado, a 
popularidade do nome ao longo das décadas. 
 
 
 
Projeto da estrutura de dados 
 
Você tem de considerar algumas questões no projeto de sua estrutura de dados. É preciso armazenar algum 
tipo de coleção de objetos? Talvez seja possível usar uma das estruturas existentes em Python para 
armazenar essas coleções (Lists, Dictionaries, Tuples) 
 
Algumas vezes, o identificador único de um dado pode ser uma combinação de atributos. Por exemplo, o 
nome da banda e o nome da música para identificar unicamente uma canção. 
 
 
 
Relembrando alguns métodos úteis de lists 
 
Lembre-se, no caso de dicionários, o conjunto de chaves e o conjunto de valores são também lists, então os 
seguintes métodos podem ser úteis para ambos os tipos de coleções (dicionários e listas): 
 
lista.append(objeto) 
Atualiza lista acrescentando o objeto objeto ao final da lista. 
 
lista.remove(valor) → item 
Remove da lista lista a primeira ocorrência de valor. O método lança uma exceção se o valor não 
pertence à lista. 
 
lista = [] 
Maneira rápida de limpar uma lista 
 
len(lista) 
Retorna o número de elementos em uma lista 
 
lista.count(valor) → integer 
Retorna o número de ocorrências de valor na lista lista. 
 
for elemento in lista: 
 ... 
Percorrendo uma lista através de um iterator 
 
 
Um exemplo 
 
Vamos juntar todos esses conceitos em um exemplo, uma loja on-line de músicas em mp3. 
 
Quais são os conceitos desse domínio? Músicas. Algumas vezes conjuntos de músicas são vendidas na 
forma de Álbuns. Uma música pode pertencer a mais de um álbum. 
 
Uma vez que Música é um conceito do domínio, provavelmente teremos na aplicação uma classe Música 
que armazenará as informações de uma dada canção. Os atributos de uma música são: 
 
• nome da música 
• nome da banda 
• preço 
 
O que usaremos como identificador único de uma música? O nome da música, juntamente com o nome da 
banda, parece ser um identificador apropriado. 
 
Que modificações podem sofrer as informações de uma música enquanto essa é mantida em estoque? O 
nome da música e o nome da banda não sofrem alterações, mas o preço pode mudar. 
 
 
A classe Música 
 
 
 
 
class Musica: 
 
 def __init__(self, nomeMusica, nomeBanda, precoMusica = 0.0): 
 self.__nome = nomeMusica 
 self.__banda = nomeBanda 
 self.__preco = precoMusica 
 
 def getNomeMusica(self): 
 return self.__nome 
 
 def getNomeBanda(self): 
 return self.__banda 
 
 def setPreco(self, precoMusica): 
 self.__preco = precoMusica 
 
 def getPreco(self): 
 return self.__preco 
 
 def __str__(self): 
 return '"%s" por %s custa R$ %.2f' % \ 
 (self.__nome, self.__banda, self.__preco) 
 
 
 
 
O outro conceito do domínio é um Álbum. Quais são os atributos de um Álbum? 
• nome 
• banda 
• lista de músicas 
 
Que estrutura de dados seria apropriada para armazenar uma lista de músicas? Um list Python! 
 
 
A classe Álbum 
 
 
 
class Album: 
 def __init__(self, nomeAlbum, nomeBanda): 
 self.__nome = nomeAlbum 
 self.__banda = nomeBanda 
 self.__musicas = [] 
 
 def getNomeAlbum(self): 
 return self.__nome 
 
 def getNomeBanda(self): 
 return self.__banda 
 
 def adicionaFaixa(self, musica): 
 self.__musicas.append(musica) 
 
 def getFaixas(self): 
 return self.__musicas 
 # talvez fosse mais seguro fazer: 
 return copy.deepcopy(self.__musicas) 
 
 def __str__(self): 
 return "\"%s\" por %s" % (self.__titulo, self.__banda) 
 
 
Vamos assumir que o nome de um álbum é um identificador único para um álbum. 
 
 
Estrutura de Dados 
 
 
 
 
Diagrama de objetos 
 
 
 
Existe um único objeto para cada música, referenciado pelo list de músicas e, eventualmente, por algum 
álbum no dicionário. 
 
 
As estruturas de dados em código 
# Coleção de todos os álbuns disponíveis para venda 
albuns = {} 
# Coleções de todas as músicas disponíveis para venda 
musicas = [] 
 
 
A loja 
 
Quais são os serviços oferecidos pela loja? Vamos observar o menu de opções: 
 
Por favor, escolha uma opção (0 para terminar): 
1. Lista todas as músicas 
2. Lista todos os álbuns 
3. Adiciona uma música 
4. Adiciona um álbum 
5. Lista faixas em um álbum 
6. Atualiza o preço de uma música 
Opção: 
 
 
Os métodos associados às opções: 
 
1. Lista todas as músicas 
 
# Lista todas as músicas disponíveis para venda 
def listaMusicas(): 
 print "Todas as músicas disponíveis para venda:" 
 for musica in musicas: 
 print musica 
 
 
... 
músicas 
We No Speak… 
Yolanda B Cool 
2.49 
Need You Now 
Lady Antebellum 
2.49 
California Gurls 
Katy Perry 
2.49 
Rock And Roll L… 
Pato Fu 
1.99 
Teenage Dream 
Katy Perry 
2.49 
Sonífera Ilha 
Pato Fu 
1.99 
Música de Brinquedo 
Pato Fu <<key>> 
álbuns 
... 
Sonífera Ilha 
Pato Fu 
1.99 
Primavera (Vai... 
Pato Fu 
1.99 
Frevo Mulher 
Pato Fu 
1.99 
Ovelha Negra 
Pato Fu 
1.99 
Live and Let Die 
Pato Fu 
1.99 
 
 
2. Lista todos os álbuns 
 
# Lista todos os álbuns disponíveis para venda 
def listaAlbuns(): 
 print "Todos os álbuns disponíveis para venda:" 
 for album in albuns.values(): 
 print album 
 
 
 
3. Adiciona uma música 
Antes de adicionar uma nova música, é preciso verificar se já existe um objeto instanciado, correspondente a 
essa música. 
 
# Verifica se uma música (identificada pelo seu título e nome 
# da banda) já existe na loja. Se a música já existe, o método 
# retorna a referência para o objeto correspondente. 
# Caso contrário, o método retorna None. 
def procuraMusica(titulo, banda): 
 for musica in musicas: 
 if musica.getNomeMusica() == titulo and \ 
 musica.getNomeBanda() == banda: 
 return musica 
 return None 
 
 
Se a música não existia, crio então o novo objeto e o adiciono à coleção de músicas. 
 
# Adiciona uma nova musica ao inventário da loja. 
# 
# Se a musica já existia na loja, o método retorna uma referência 
# para o objeto existente. 
# 
# Se a música não existia na loja, o método retorna uma referência 
# para o objeto recém-criado. 
# 
# O método pode retornar None, se o usuário decidiu não fornecer os 
# dados de uma música (isto é, o usuário apenas pressionou Enter 
# quando o programa solicitou o nome da nova música. 
def adicionaMusica(): 
 titulo = raw_input("Título da música (Enter para terminar): ") 
 if titulo == "": return None 
 banda = raw_input("Nome da banda: ") 
 musica = procuraMusica(titulo, banda) 
 if musica == None: 
 preco = input("Preço: ") 
 musica = Musica(titulo, banda, preco) 
 musicas.append(musica) 
 print "Nova música adicionada à loja." 
 else: 
 print "Essa música já existe na loja." 
 return musica4. Adiciona um álbum 
 
# Adiciona um novo álbum ao estoque da loja. Se o álbum 
# já existe na loja, a relação de álbuns não é alterada. 
# Caso contrário, o novo álbum e quaisquer novas musicas 
# que ele contenha são adicionados ao inventário da loja. 
def adicionaAlbum(): 
 titulo = raw_input("Título do álbum: ") 
 if albuns.has_key(titulo): 
 print "Esse álbum já existe na loja." 
 else: 
 banda = raw_input("Nome da banda: ") 
 album = Album(titulo, banda) 
 albuns[titulo] = album 
 while True: 
 musica = adicionaMusica() 
 if musica == None: break 
 album.adicionaFaixa(musica) 
 print "Novo álbum adicionado à loja." 
 
 
 
5. Lista faixas em um álbum 
 
# Lista todas as faixas em um álbum do estoque 
def listaFaixasEmAlbum(): 
 titulo = raw_input("Título do álbum: ") 
 if albuns.has_key(titulo): 
 faixas = albuns[titulo].getFaixas() 
 print "%s contém as seguintes faixas:" % titulo 
 for faixa in faixas: 
 print faixa 
 else: 
 print "Não existem álbuns com esse título no estoque." 
 
 
 
6. Atualiza o preço de uma música 
 
# Atualiza o preco de uma musica no estoque da loja. 
# Observe que esta atualização afetará também todos 
# os álbuns que contenham esta musica. 
def atualizaPrecoMusica(): 
 nome = raw_input("Nome da música: ") 
 banda = raw_input("Nome da banda: ") 
 musica = procuraMusica(nome, banda) 
 if musica == None: 
 print "Essa música não existe na loja." 
 else: 
 preco = input("Novo preço: ") 
 musica.setPreco(preco) 
 print "Preço de %s atualizado." % nome