AEDES 2 Documentacao Trabalhos Praticos

Prévia do material em texto

TRABALHO PRATICO DE AEDS2
TP2: OTIMIZACAO SERVIDOR DE EMAILS
Prof. Gisele Pappa e Rodrygo Santos
Aluna: Julia Ferri Leite Storino
Matricula: 2014088661
1. Introdução
Ao longo da disciplina, foi trabalhado dois conceitos fundamentais: Alocação 
dinâmica de memória e Tipo Abstrato de dados. Alem desses, que foram base para 
o feitio do Trabalho, foi utilizada duas estruturas, Tabela Hash e Arvore Binaria, que 
deram um “upgrade” no funcionamento do antigo servidor de emails, implementado 
com listas encadeadas.
O objetivo desse trabalho é melhorar um programa ja existente de um 
simulador de um servidor de emails com listas encadeadas. Este servidor da o 
suporte ao gerenciamento de contas, assim como entrega mensagens de usuários, 
consulta de contas, cadastramento de usuário, e remoção de emails. Para essa 
melhoria, foi criado uma Tabela Hash, no qual os registros armazenados na tabela 
são diretamente endereçados a partir de uma transformação aritmética sobre a 
chave de pesquisa. Entretanto, essa pode gerar colisões, enderecando ao mesmo 
local; para resolver esse problema cada entrada da tabela hash apontara para uma 
arvore binaria que, em cada no desta arvore estará um email armazenado, 
totalizando a arvore então, uma caixa de entrada.
Assim, espera-se com isso reforçar os conceitos de Alocação dinâmica de 
memória, e Tipo Abstrato de dados, trabalhados no primeiro e segundo trabalho 
pratico. Além disso, espera-se aprender a trabalhar e manipular Tabelas Hashing, 
que são tipicamente usadas para indexação de grandes volumes de informação 
(como bases de dados), no caso, provenientes do servidor de emails. Assim como o 
manuseio e implementação das Arvores, estrutura muito utilizada na computação 
para realizar buscas, de extrema importância e uma boa eficiência.
2. Implementação
Estrutura de dados
Para facilitar a implementação e evitar a criação de varias variáveis, foi 
utilizado no código o conceito aprendido de Estrutura de Dados. De acordo com a 
proposta, foi criado, juntamente com o typedef, varias estruturas (structs) para 
armazenar os dados que estarão presentes dentro do servidor de emails. E 
importante ressaltar que o typedef foi utilizado para definir uma nova estrutura, que 
possa ser usada dentro de outra estrutura, sendo assim, uma definição de um novo 
tipo (type definition).
A primeira estrutura criada foi a Struct Mensagem. Nessa Estrutura encontra-
se uma variável do tipo inteiro “ID”, que será utilizado para identificar os usuários. 
Alem disso foi criado variável tipo caractere “mensagem” para armazenar o campo 
da mensagem, o conteúdo escrito do email. 
A segunda estrutura de dados criada foi a Struct MailBox, que possui uma 
variável Email do tipo Estrutura Mensagem que armazenara o email. Alem disso, 
Cada Estrutura do tipo Mailbox possui um apontador do tipo Mailbox para a sua 
esquerda (left) e para a sua direita (right). Alem disso, e criado a tabela Hashing, 
“GavetaUsuarios”, um vetor de arvores que vai de 0 a M-1. Sendo que o “M” e 
informado previamente. 
Alem disso, as funções que serão criadas também utilizam os parametros 
“struct Mailbox”, visto que essa estrutura será manipulada nas funções. 
Funções
Alem das estruturas de dados, foi implementado funções que dividiram o 
problema em 3: a entrega de uma mensagem (1), a remoção de um email (2), e a 
consulta de uma caixa de email presente na lista de usuários (3). Entretanto, foi 
necessário duas funções auxiliares: a criação de uma caixa de emails (0), e a 
procura do menor entre os maiores filhos de um no da arvore (00).
0) struct MailBox* cria_mail(Mensagem *email): essa função recebe um email do 
tipo Mensagem, e cria uma Mailbox vazia. Primeiramente é alocado dinamicamente 
um tipo “arvoredosmails”, a partir do “malloc”, para inicializar a estrutra. Então, os 
ponteiros contidos em “arvoredosmails”, são transformados, tal que o esquerda (left) 
e o direita (right) apontam para null, e o que aponta para o email recebe o email. 
Assim, a arvore contem apenas o email do tipo mensagem recebido na função.
00) struct MailBox* acha_menor(MailBox *arvoresdosmails): essa função recebe 
“arvoredosmails”, a arvore como parâmetro o primeiro filho da direita da arvore e a 
partir desse filho ela procura o menor dele. Ou seja, a função retorna o menor entre 
os maiores filhos da raiz. Essa funcao será útil para as principais, visto que a ordem 
da arvore (a esquerda menores do que a raiz e a direita maiores do que a raiz) deve 
ser mantida em todas as funcoes que serão descritas abaixo:
1) int entregaMsg(Mensagem *email, struct MailBox *arvoresdosmails): essa 
função recebe um email do tipo Mensagem, e uma arvoredosmails, a caixa de 
entrada, do tipo MailBox na qual o email devera ser inserido. Essa função faz um 
caminhamento binário na arvore com chamadas recursivas, realizando recursos 
percorrendo a arvore encontrada a partir do valor do hashing. Visto que o valor de 
entrada é conhecido, este vai diretamente para o endereço da arvore do usuário na 
tabela hash. Em seguida, para realizar essa entrega no lugar correto, foi criado um if 
que compara o valor do no atual e o valor do elemento a ser inserido. Caso o no 
seja maior, este vai para esquerda; caso seja menor, este vai para a direita; sempre 
mantendo a ordem da arvore binaria. Quando o resultado dessa operação é “null”, 
isso significa que o local de inserção foi encontrado. A partir desse momento, é 
alocado então o elemento a ser inserido. Desse modo, o email então é entregue. 
Entretanto, se o local de inserção não é encontrado, é constatado um erro. Se a 
operação é efetuada com sucesso, a função retorna “1”; se não esta retorna 0; ou 
seja, o elemento desse email ja existe na arvore.
2) struct MailBox* limpa(int id, struct MailBox *arvoresdosmails): essa função 
recebe um ID da mensagem a ser removida. Primeiramente, é verificado se a arvore 
de mensagens do usuário esta nula. Se sim, é constatado um erro, pois não ha 
nada a ser apagado. Se não, a arvore é percorrida por meio de apontadores em 
comparação com item a ser apagado. De modo que, se o id é menor que o 
apontador da arvore para o item a ser deletado, é chamado recursivamente a 
função limpa para o apontador da esquerda (arvoredosmails->left); caso contrario, é 
chamada a função recursivamente a função limpa para o apontador da direita 
(arvoredosmails->right). 
Entretanto, é necessário verificar se o no a ser deletado possui filhos. Se os 
apontadores da esquerda e da direita são nulos, isso significa que não possui filhos, 
não sendo necessário realocar os apontadores e simplesmente apagando com o 
comando “free”. Entretanto, se apenas o apontador da esquerda (arvoredosmails-
>left) é nulo, significa que existe apenas um filho para a direita. Assim, é criado um 
aux do tipo Estrutura Mailbox que recebe o filho existente, no caso, apontador da 
direita; e então, o apontador do email é deletado a partir do comando 
(free(arvoredosmails)) com sucesso. O mesmo processo é feito se apenas o 
apontador da direita é nulo (ou seja, existe apenas um filho para a esquerda), so 
que agora o auxiliar aux recebe o filho da esquerda. Em seguida, o o apontador do 
email é deletado a partir do comando (free(arvoredosmails)) com sucesso. Todavia, 
se o email a ser deletado possui 2 filhos, é criada uma nova variável “suc” do tipo 
MailBox que recebe o valor do menor filho a direita da arvore a partir da chamada 
da função acha_menor com os apontadores da direita, onde se localizam os 
maiores valores de uma arvore ordenada (arvoredosmails->right). Em seguida, essa 
variável suc passa a ocupar o lugar do email que foi apagado com sucesso.
3) struct MailBox* consulta(int id, struct MailBox *arvoresdosmails): a função 
recebe o id, e a arvore dos emails. Assim, a função procura o email a ser consultado 
com as operações básicas de arvores:se o id passado é igual ao ponteiro da arvore 
da id do email, a mensagem foi encontrada e retornada; se o id é menor que o 
ponteiro da arvore da id do email, a mensagem encontra-se a esquerda (é menor 
que onde o ponteiro aponta), e é chamado recursivamente o consulta para a 
esquerda (arvoredosmails->left). Caso contrario, se o id passado é maior que o 
ponteiro da arvore da id do email, a mensagem encontra-se a direita (é maior que 
onde o ponteiro aponta), e é chamado recursivamente o consulta para a direita 
(arvoredosmails->right). Entretanto, se mesmo com essas operações a mensagem 
não foi encontrada, isso significa que a mensagem não existe, retornando null. 
Programa Principal
O programa main.c e responsável por receber os argumentos de entrada e 
saída (input/output),e inseri-los nas devidas funções acima. O arquivo de entrada 
(input) é aberto com o comando “fOpen”, e fechado com o comando “fClose”. 
Para isso, primeiramente o programa lê o arquivo de entrada a partir do 
comando “fOpen”, que a partir da opção “r” (read) lê o arquivo, que contem as 
operações a serem feitas no servidor de email. Foi criado no programa principal, 
uma variável comando do tipo “char” que definira a operação a ser realizada. 
Primeiramente o numero M é lido pelo comando fscanf, e depois, é alocado 
dinamicamente o “GavetaUsuarios” pelo comando malloc, que cria um vetor de 
arvores de acordo com o tamanho de M; ou seja, em cada posição de i ate m-1 
desse existe a raiz de uma arvore. Então é feito um loop que cria para cada posição 
i desse vetor uma “caixinha”, uma parte reservada para o email. Isso também é feito 
dinamicamente com o comando malloc de acordo com o tamanho do tipo 
Mensagem. 
Em seguida, foi necessário ler os comandos contidos no arquivo de entrada. 
Para isso, foi criado um loop com o comando while no qual enquanto a função fgets, 
que pega uma linha inteira do arquivo de entrada e armazena na forma de uma 
string é diferente de zero. Depois de lido a string, é necessário codificar a string 
contida no arquivo de entrada. Ou seja, assimilar as palavras contidas no arquivo as 
operações a serem feitas, e assimilar o numero que esta escrito no arquivo de 
entrada como tipo “char” para um numero inteiro que será o ID. Para isso foi 
utilizado o comando “strcmp” utilizada para comparar strings, retornando “0” se as 
strings forem realmente iguais. No programa este comando compara a palavra 
escrita no arquivo de entrada com as operações disponíveis 
(apaga,entrega,consulta) e, dependendo do resultado (que será 0 se a comparação 
for realmente igual), chama a função relacionada a tal comando. Ja para a 
conversão do numero do tipo caractere para um inteiro ID, foi utilizado o comando 
“atoi”, que converte strings em números inteiros. Ademais, o endereço de cada 
“arvoredosmail” na tabela hash é feita pela operação de resto entre U, que é um 
numero também lido do arquivo de entrada pelo comando atoi, e o numero M, 
também lido da tabela anteriormente. Assim é cada arvore é endereçada na tabela 
hash.
Alem disso, dentro de cada função, como foi explicado, foi estabelecido um 
valor de retorno. Desse modo, se a função retorna “null”, ocorreu um erro durante a 
execução da função, que e explicitado na função main, que a partir do comando 
“printf”, alerta ao usuário sobre o erro ocorrido, de acordo com a especificação do 
servidor. Entretanto, se a função retorna o valor “1”, essa função foi executada com 
sucesso, e esse processo também e comunicado ao usuário, de acordo com a 
especificação do servidor. Esse processo de comparação dos valores de retorno da 
função foram feitos a partir do comando “if”, designando cada valor para seu 
respectiva saída adequada, de acordo com a especificação do servidor. 
Essa saída adequada é impressa na tela. Desse modo, o programa retorna, e 
imprime na tela a conclusão ou não de cada operação solicitada pelo arquivo de 
entrada. Desse modo, para cada operação requerida pelo arquivo de entrada é 
gerada uma saída. 
Vale ressaltar que o programa trabalha apenas com o retorno de funções, não 
acessando a estrutura interna dos TADS, apenas as funções oferecidas em sua 
interface.
Organização do Código, Decisões de Implementação e Detalhes técnicos
Em geral, o arquivo Emails foi dividido em 3 partes: o main.c, programa 
principal que define a entrada e a saída e “chama as funções”, Email.c onde foi 
definido o que cada função faz, e o Email.h onde foi definido as estruturas (structs) a 
serem utilizadas. Isso foi feito visando evitar a criação de variáveis e funções de 
forma desorganizada.
O programa foi compilado em Linux, e também pelo sistema pratico. Para 
executa-lo, bastou digitar “gcc Wall std=c99 *.c o tp1” no ambiente Linux, e “./
tp2 entrada ” no Pratico.
3. Analise de Complexidade
A complexidade de cada função varia, visto o uso do Hashing e Arvores; entretanto, 
como o programa busca otimizar o anterior, todas buscam ser menores que o 
servidor que utiliza listas encadeadas.
Foi considerado que a complexidade do hashing é O(1) pois para calcular uma 
posição qualquer em um vetor basta aplicar a operação aritmética explicitada na 
especificação. Desse modo, a analise de complexidade será feita em relação ao 
numero de comparações na arvore, de tal forma que:
⁃ Função CriaMail: essa função possui complexidade O(1), visto que sua 
função e de apenas criar o no da arvore inicial.
⁃ Função acha_menor: a função acha menor, que acha o menor dos filhos 
entre os maiores filhos da arvore, tem seus casos particulares que alteram 
sua complexidade. Seu pior caso é tido quando a arvore inteira é procurada, 
e o menor se encontra na ultima posição da arvore, sendo desse modo, O(n). 
Isso pode ocorrer nesta arvore pois não foram implementados mecanismos 
de balancear a arvore, sendo comparados todos seus elementos assim como 
em uma lista encadeada. Entretanto, se a arvore estivesse balanceada, seu 
pior caso seria O(log n). Ja seu o melhor caso é O(1), quando o elemento 
procurado é o primeiro a ser comparado. 
⁃ Função limpa: a função limpa é necessário analisar todos os casos. A função 
então apaga um email, mas leva em consideração os filhos ou não que esse 
no possui ou nao. Desse modo, se o no a ser apagado não possui filhos, a 
complexidade é o pior caso da função, em que ela percorre todos os 
elementos de uma arvore não balanceada, sendo então O(n). Se o no possui 
1 filho, no pior caso, da arvore não balanceada e na ultima posição, a arvore 
inteira é percorrida menos a posição que sucede, o seu filho; sendo então 
O(n-1). Entretanto, se o no possui 2 filhos, no pior caso, a arvore não 
balanceada é inteiramente percorrida menos suas 2 posições sucessoras, no 
caso, seus dois filhos, sendo assim O(n-2). Comparando com o primeiro 
trabalho, a complexidade se equiparam em uma arvore não balanceada, por 
ser O(n). Entretanto, se tivéssemos implementado mecanismos para 
balancear a arvore, o programa novo seria mais eficiente, visto que a 
complexidade de uma arvore balanceada é O(log n) se o no não possuir 
nenhum filho. 
⁃ Função EntregaMsg: essa função também deve ser analisada em seus casos 
extremos. Em seu melhor caso, a entrega possui O(1), pois é encontrado 
diretamente o local de entrega. Entretanto no seu pior caso, deve se 
considerar que a arvore não esta balanceada e o local de entrega é o ultimo, 
sendo desse modo, necessário percorrer todas as posições da arvore, pois 
todos os itens encontram-se em um lado da arvore, resultando em uma 
complexidade O(n). Desse modo, visto que a arvore não teve mecanismos de 
balanceamento, a complexidade se equipara ao programa anterior 
implementado com listas encadeadas.
⁃ Função Consulta: a função consulta deve achar o email o qual a consulta 
deve ser feita. Em seu melhor caso, o elemento a ser consultado é o 
primeiro, sendo feito assim apenas 1comparação; sendo assim O(1). Ao 
analisarmos seu pior caso, todos os itens encontram-se em um lado da 
arvore (arvore não foi implementada com mecanismos de balanceamento), e 
o item a ser consultado encontra-se na ultima posição, resultando desse 
modo em O(n). Ao compararmos com o programa anterior, os programas se 
equiparam, resultando em complexidades iguais a O(n).
⁃ Programa Principal: o programa principal apenas chama cada uma das 
funções descritas acima e faz alguns comandos constantes, tais quais abrir o 
arquivo, comparar strings.. Desse modo, a sua complexidade é regida pela 
função de maior custo computacional; se a arvore esta balanceada a 
complexidade é O(1) + O (log n) + O(log n-1) + O(log n) + O(log n) = O(log n) 
sendo mais vantajoso que o programa anterior. Entretanto se a arvore não 
esta balanceada, a sua complexidade O(1) + O (n) + O(n-1) + O(n) + O(n) = 
O(n); equiparando ao programa anterior,
4. Conclusão
O desenvolvimento do algoritmo ocorreu de forma tranquila, visto que foi 
trabalhado desde o dia do lançamento do trabalho, ate a data de entrega, evitando 
desesperos e surpresas. 
A principal dificuldade encontrada foi o desenvolvimento inicial do trabalho, 
visto que de primeira vista, o Trabalho parece requerer muitas funcionalidades, 
assustando um pouco. Entretanto, ao olhar mais cuidadosamente, foi possível 
encontrar soluções para o mesmo, buscando a forma mais simples possível. Apesar 
disso, o resultado foi satisfatorio, visto que o servidor de email foi criado, atendendo 
todos requerimentos, como por exemplo a criação de funções, uso de TADS, e 
manipulação da tabela hash e de arvores. 
Alem disso, foi constatado que o programa não foi totalmente otimizado, visto 
que as complexidades de certas funções permaneceram as mesmas em relacao ao 
programa implementado com listas encadeadas. Isso ocorreu pois não tivemos base 
o suficiente para implementar mecanismos que fossem capazes de balancear 
arvores, o que diminuiria a complexidade de O(n) para O(log n) em todos os piores 
casos. 
Referencias
[1] Ziviani, N., Projeto de Algoritmos com Implementações em Pascal e C, 2ª Edição, 
Editora Thomson, 2004.
[2] Material disponibilizado pelo Moodle da disciplina
[3] Pesquisas diversas no Google