PRG29003: Etapa 2: Projeto de estruturas de dados

Desde o início do semestre foi usada a biblioteca STL, que contém implementações das estruturas de dados estudadas. Na primeira etapa da disciplina se enfatizou conhecer e usar essas estruturas de dados. Na segunda etapa o foco está no projeto de uma estrutura de dados, e o resultado esperado é a criação de estruturas de dados pelas equipes. Podem ser criadas versões que reproduzam (possivelmente com um toque pessoal) as características das estruturas de dados estudadas, ou mesmo novas estruturas de dados, diferentes daquelas conhecidas.

As estruturas de dados que já conhecemos são:

• Lineares: filas, pilhas e listas
• Associativas: tabelas hash, conjuntos e árvores de pesquisa binária

Mais especificamente os objetivos de aprendizagem desta unidade são:

1. Desenvolver (criar) uma estrutura de dados que possa ser utilizada em programas, possuindo uma interface de programação bem definida, e incluindo os algoritmos específicos necessários para a eficiência de suas operações quanto ao uso de memória e tempo computacional.
2. Avaliar o projeto de uma estrutura de dados, usando sua documentação como referência para emitir um julgamento sobre sua eficiência e usabilidade

Algumas das estruturas conhecidas são bastante simples, e não serviriam como objeto de estudo nesta etapa da disciplina (refiro-me especificamente a filas e pilhas). As demais têm complexidade adequada para serem desenvolvidas neste último mês de aula. Além delas, outras estruturas de dados podem ser escolhidas:

• Trie: uma trie é um tipo de árvore n-ária (que pode ter um número n de ramos por nodo), em que os dados estão armazenados nos ramos, e não nos nodos. Esse tipo de árvore armazena prefixos dos dados, então são adequadas para dados formados por cadeias de elementos (ex: strings, endereços IP, sequências de bits em geral, ...). Um uso conhecido para tries é como dicionário de termos para um sistema do tipo auto-completar. Uma variação de tries é radix tree.
• Array Deques: um array deque é um tipo de fila que usa um array dinâmico (i.e. que pode ser expandido ou contraído) para armazenar dados. Ela possibilita a inserção e remoção eficiente de dados de seus extremos, e o acesso a qualquer dado pode ser feito com tempo constante (i.e. o custo de tempo computacional dessa operação é O(1)).
• Hashed Array Tree: um hashed array tree (ou HAT) é parecido com um array deque, porém sua estrutura interna faz um melhor uso de memória. Apesar do nome, ela nada tem a ver com tabelas hash.
• Lista desenrolada: uma lista desenrolada é parecida com uma lista usual, porém ela possibilita armazenar múltiplos dados em cada nodo da lista. Isso traz algumas vantagens quanto ao uso de memória e localização dos dados.
• Filtros Bloom: um filtro Bloom serve para informar sobre a existência ou não de um dado, porém probabilisticamente. Ele pode resultar em falsos positivos, quando retorna verdadeiro para um dado inexistente ou desconhecido, mas nunca retorna falsos negativos. Assim, se um filtro informa que um dado é desconhecido ou inexistente, com certeza isso é verdade. Essa estrutura de dados possui várias aplicações importantes.
• ... e possivelmente outras !!!

Descrição da avaliação

A realização desse último projeto será avaliada da seguinte forma:

1. Cada equipe deve entregar a implementação de sua estrutura de dados, acompanhada de sua documentação
   • A implementação da estrutura de dados corresponde ao seu código-fonte
   • A documentação é composta pelo seguinte:
     1. Uma descrição da estrutura de dados, que informe seu propósito e como os dados são nela armazenados
     2. Declaração da API da estrutura de dados devidamente comentada. Essa API é formada pelos tipos de dados e operações (funções) que um programa precisará conhecer para poder usar sua estrutura de dados
     3. Instruções sobre como compilar programas que usem a estrutura de dados
2. A estrutura de dados deve ser avaliada individualmente por colegas de outras equipes:
   • Cada avaliador deve avaliar uma estrutura de dados, escolhida aleatoriamente pelo professor
   • Cada avaliador deve usar a estrutura de dados: isso implica escrever um programa de teste que verifique cada operação da estrutura de dados
   • Avaliação será feita usando um formulário fornecido pelo professor: esse formulário possuirá itens a serem observados e ponderados na avaliação
   • Cada avaliador deverá entregar ao professor o seu formulário preenchido, acompanhado de comentários sobre como avaliou a estrutura de dados, e os programas de teste que foram criados
3. Ao final desse processo, cada estudante será avaliado da seguinte forma:
   • Peso 4: A média das avaliações feitas pelos colegas avaliadores sobre a estrutura de dados de sua equipe
   • Peso 6: A avaliação do professor sobre a qualidade de suas avaliações
   • OBS: a avaliação será ZERO caso a equipe do estudante não apresente sua estrutura de dados

Datas importantes:

• 29/09: início do projeto da estrutura de dados
• 13/10: entrega das estruturas de dados pelas equipes, incluindo documentação
• 13/10: sorteio dos avaliadores e início das avaliações por colegas
• 16/10: entrega das avaliações dos colegas
• 20/10: publicação das avaliações pelo professor

Alternativa

O projeto 4 pode ser avaliado desta outra forma:

1. Cada equipe deve entregar a implementação de sua estrutura de dados, acompanhada de sua documentação
   • A implementação da estrutura de dados corresponde ao seu código-fonte
   • A documentação é composta pelo seguinte:
     1. Uma descrição da estrutura de dados, que informe seu propósito e como os dados são nela armazenados
     2. Declaração da API da estrutura de dados devidamente comentada. Essa API é formada pelos tipos de dados e operações (funções) que um programa precisará conhecer para poder usar sua estrutura de dados
     3. Instruções sobre como compilar programas que usem a estrutura de dados
2. Cada estudante deve escrever um programa que demonstre o uso da estrutura de dados de outra equipe
   • O problema resolvido deve ser explicado, incluindo como a estrutura de dados foi usada e como ela facilitou a solução
   • Esse programa deve verificar cada operação da estrutura de dados
3. Ao final desse processo, cada estudante será avaliado da seguinte forma:
   • Peso 4: A avaliação da estrutura de dados feita por sua equipe
   • Peso 6: A avaliação do seu programa de demonstração
   • OBS: a avaliação será ZERO caso a equipe do estudante não apresente sua estrutura de dados

Requisitos para escrever estruturas de dados

O projeto de uma estrutura de dados envolve alguns requisitos.

O mais evidente é ter clara a finalidade da estrutura de dados, o que significa entender e prever o tipo de uso que se pode fazer dela. Uma consequência desse requisito é identificar as operações que podem ser feitas sobre essa estrutura de dados. A finalidade da estrutura, e seu conjunto de operações, tem forte correlação com a forma com que os dados são armazenados em memória.

O requisito seguinte diz respeito à organização dos dados em memória nessa estrutura de dados. Existem diversas técnicas para armazenar e organizar os dados em memória, de forma que as operações definidas possam ser realizadas com a eficiência projetada. A alocação dinâmica de memória, e esquemas de endereçamento indireto, são comuns ao se projetar o uso de memória em uma estrutura de dados.

Um outro requisito envolve escolher ou projetar algoritmos eficientes para as operações da estrutura de dados. Esses algoritmos têm forte dependência da forma com que os dados são organizados em memória. A eficiência desses algoritmos tem relevância, implicando compromissos entre menores tempos computacionais e usos de memória.

Alocação de memória

Alocação de memória significa reservar uma certa quantidade de memória do computador para um uso específico pelo programa. A forma mais simples de alocar memória é criar variáveis. Quando se declara uma variável, implicitamente aloca-se a memória necessária para armazenar seu conteúdo. Essa alocação é definida pelo compilador ao se compilar o programa. Para ter uma ideia de como isso funciona, veja este exemplo.

#include <iostream>
#include <string>

using namespace std;

// Esta função mostra informações sobre uma variável
// Ela é uma função template para funcionar com qualquer tipo de variável
// Parâmetros:
//  varname: nome da variável
//  val: uma referência à variável a ser mostrada
template <typename T> void mostra(const string & varname, T & val) {
  cout << "######################################################" << endl;

  // mostra o valor da variável
  cout << varname << " = " << val << endl;

  // mostra o endereço da variável
  T * ptr = &val;
  cout << "Endereço de " << varname << ": " << (void*)ptr << endl;

  // Mostra a quantidade de memória alocada à variável
  cout << "Memória alocada: " << sizeof(T) << " bytes" << endl;
}

int main() {
  // algumas variáveis
  // a memória para elas é alocada automaticamente
  int x = 35;
  float y = 3.1416;
  double h = 6.62607015e-34;
  char c = 'A';
  char v[8] = {'a','b','c','d','e','f','g',0};

  mostra("x", x);
  mostra("y", y);
  mostra("h", h);
  mostra("c", c);
  mostra("v", v);
}

Ao executá-lo, o resultado é este:

######################################################
x = 35
Endereço de x: 0x7ffd895a65e0
Memória alocada: 4 bytes
######################################################
y = 3.1416
Endereço de y: 0x7ffd895a65e4
Memória alocada: 4 bytes
######################################################
h = 6.62607e-34
Endereço de h: 0x7ffd895a65e8
Memória alocada: 8 bytes
######################################################
c = A
Endereço de c: 0x7ffd895a65de
Memória alocada: 1 bytes
######################################################
v = abcdefg
Endereço de v: 0x7ffd895a6610
Memória alocada: 8 bytes

Observe que cada variável possui um endereço de memória diferente (mostrado em hexadecimal). Dependendo do tipo de variável, a quantidade de memória alocada pode variar. O que determina quanta memória é necessária é o tipo da variável, não o dado que será armazenado. O compilador sabe quanta memória cada tipo de dados precisa, e por isso reserva a quantidade adequada para cada variável. Essa forma de usar memória é muito prática para o programador, que não precisa se preocupar com a alocação e liberação de memória para suas variáveis. Porém isso apresenta algumas limitações.

A primeira dificuldade aparece quando não se sabe exatamente quantos dados serão armazenados. Por exemplo, desejam-se armazenar números em um vetor, mas não se sabe exatamente quantos números serão fornecidos ao programa. Se forem usadas variáveis com alocação automática, o programador precisará criar um vetor cujo tamanho deve ser estimado pela quantidade de dados que provavelmente podem ser fornecidos no pior caso. Isso implica dois problemas:

1. Se a estimativa estiver incorreta, mais dados do que se pensou podem ser fornecidos e não haveria lugar no vetor para todos eles.
2. Se na maioria das vezes a quantidade de dados for bem menor do que o estimado, o vetor terá boa parte de sua capacidade ociosa. Isso significa que o programa estará reservando mais memória do que o necessário, e isso pode ter consequências negativas (lembre que memória é um recurso finito).

A segunda dificuldade é mais sutil. As variáveis existem apenas no escopo em que foram declaradas. Além de as variáveis de uma função não serem acessíveis em outra função, elas deixam de existir quando termina a função em que foram declaradas. Uma variável deixar de existir significa que a memória a ela alocada foi liberada, e pode ser usada para outros propósitos no programa. Portanto, se uma função armazena dados que devem estar disponíveis em outras funções, uma outra forma de alocar a memória deve ser usada. Esses dados devem ser armazenados em uma área de memória que não seja liberada automaticamente, quando terminar o escopo em que foi alocada.

Para usar memória sem essas limitações, recorre-se à técnica de alocação dinâmica de memória.