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 o objetivo de aprendizagem desta unidade é:

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.

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 !!!

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 dinâmica 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.