Programming Pearls: Parte 4

Abril 25, 2011

Coluna 14: Heap

Essa coluna descreve a estrutura de dados heap e como usá-la para implementar uma fila de prioridades e para ordenar um vetor de elementos (heapsort). O código de heapsort fornecido é bem conciso:

void down(int *v, int l, int u){
    while (1){
        int c = 2*l;
        if(c > u) return;
        if(c + 1 <= u && v[c+1] > v[c]) c++;
        if(v[l] >= v[c]) return;
        std::swap(v[c], v[l]);
        l = c;
    }
}
void heapsort(int *v, int n){
    for(int i=n/2; i>=1; i--)
        down(v, i, n);
    for(int i=n; i>=1; i--){
        std::swap(v[1], v[i]);
        down(v, 1, i-1);
    }
}

Observando que o vetor v deve conter os n elementos nas posições de 1 a n (e não de 0 a n-1 como de costume).

Um dos exercícios dá como aplicação de heaps, a soma de n números do tipo ponto flutuante. A motivação é que somar números pequenos com grandes pode acarretar perda de precisão. A ideia é ir somando a partir dos menores. Dá para fazer isso em O(n log n) usando heaps. Acho que daria um exercício de laboratório legal de estruturas de dados.

Coluna 15: String of Pearls

Como o nome sugere, nesta coluna são apresentados alguns algoritmos envolvendo strings. Inicialmente o autor apresenta um algoritmo para contar a frequência de palavras em um texto. A primeira abordagem é usando o set da biblioteca STL. Depois ele apresenta uma versão usando hash.

Depois é introduzida uma outra estrutura de dados, o array de sufixos. A definição é bem simples: dada uma string S, gere todos os seus sufixos e ordene-os em ordem lexicográfica, o que pode ser feito de maneira simples em O(L^2 log L), onde L é o tamanho de S — dá pra construir essa estrutura em O(L log L) com um algoritmo mais complicado. Algumas operações como por exemplo encontrar quais substrings de S têm os primeiros k caracteres iguais, podem ser feitas de maneira eficiente usando essa estrutura.

A parte mais interessante da coluna é sobre a cadeia de Markov. Como exemplo ele utiliza um gerador de texto aleatório (por exemplo o gerador de lero-lero ou o that can be my next tweet). A ideia é bem simples: pegue um texto e para cada palavra p, conte quais e quantas palavras sucedem p no texto. Inicialmente geramos uma palavra do texto aleatoriamente, denotada p0. Olhamos para as palavras que sucedem p0 e escolhemos uma delas com probabilidade proporcional à frequência delas. Repetimos esse procedimento até ter gerado um número suficiente de palavras.

Por exemplo no seguinte texto,

Toda a poesia – e a canção é uma poesia ajudada – reflecte o que a alma não tem. Por isso a canção dos povos tristes é alegre e a canção dos povos alegres é triste.

Fernando Pessoa

Para a palavra “a”, temos as palavras “poesia”, “alma” e três vezes “canção”. Se geramos “a” em algum momento, a próxima palavra será: “alma” ou “poesia” com 20% de chance cada e “canção” com 60%.

Como a escolha da próxima palavra só depende da última palavra gerada, temos uma cadeia de ordem 1. Generalizando, é possível usar as k últimas palavras na escolha da próxima, usando uma cadeia de ordem k. Note que conforme a ordem vai aumentando, o texto aleatório vai se tornando mais parecido com o texto original.

O autor fornece um algoritmo para gerar um texto aleatório de ordem k a partir de um texto fornecido através da entrada padrão:

– Comece com um trecho correspondente ao início do texto.
– Procure ocorrências no texto que têm as k primeiras palavras iguais a esse trecho (isso pode ser feito de maneira eficiente usando array de sufixos + busca binária).
– Escolha uma das ocorrências de forma aleatória (como não sabemos a priori quantas ocorrências existem, aquele algoritmo de selecionar um elemento de um vetor de tamanho desconhecido é bem útil).
– Imprima a (k+1)-ésima palavra da ocorrência escolhida e faça o trecho corrente começar na segunda palavra dessa ocorrência e repita o procedimento até que um número suficiente de palavras tenha sido gerado.

A ideia da leitura da entrada é bem interessante: as palavras lidas são concatenadas em um vetorzão chamado buffer e ao mesmo tempo vamos salvando em um vetor W, o endereço em que cada palavra começa em buffer. Note que cada entrada de W representa um sufixo de buffer no nível de palavras.

Para gerar o array de sufixos, precisamos ordenar os sufixos em W. Para esse problema em especial, estamos interessados apenas em agrupar os sufixos que têm as k primeiras palavras iguais. É exatamente isso que a função wordncmp implementa. A função wordnless é apenas um wrapper para a função sort da STL. Observe que usamos um vetor auxiliar P para evitar de ordenar o vetor W, já que estamos interessados em preservar a ordem inicial de W. O i-ésimo elemento do vetor ordenado é dado por W[P[i]].

vector<char *> W; // vetor de enderecos das palavras
vector<int> P; // vetor de permutacao dos indices de W

/*
 * Constroi o array de sufixos que trabalha no nivel
 * de palavras.
 */
void build_suffix_array(char *buffer){
  /* Salva o endereco em buffer onde se inicia cada
     palavra */
  W.assign(1, buffer);
  while (scanf("%s", W.back()) != EOF)
    W.push_back(W.back() + strlen(W.back()) + 1);

  /* Gera indices correspondendo a um vetor ordenado 
     comparando as k primeiras palavras */
  P.resize(W.size());
  for(int i = 0; i < (int) P.size(); i++)
    P[i] = i;
  sort(P.begin(), P.end(), wordnless);
}

/*
 * Compara as k primeiras palavras dos textos 
 * começando em p e q */
int wordncmp(char *p, char *q){
  int n = k;
  for(; *p == *q; p++, q++)
    if (*p == 0 && --n == 0) 
      return 0;
  return *p - *q;
}
/*
 * Função para ordenar os indices de W
 */
bool wordnless(int a, int b){
  return wordncmp(W[a], W[b]) < 0;
}

Uma vez que temos o vetor ordenado, dado um sufixo S do texto, encontrar a primeira posição no vetor ordenado que tem as k primeiras palavras iguais a S pode ser feito com uma busca binária.

/*
 * Busca binaria para encontrar a primeira ocorrencia
 * da palavra W[curr_index] no vetor ordenado de
 * palavras 
 */
int binsearch(int curr_index){
  int l = -1, u = (int)P.size(), m;
  while (l + 1 != u){
    m = (l + u) / 2;
    if (wordnless(P[m], curr_index))
      l = m;
    else u = m;
  }
  return u;
}

Definidas essas funções, o gerador de textos aleatórios de ordem k pode ser assim definido:

/*
 * Gerador de texto aleatorio
 */
void generator(){

  char buffer[100000];
  /* Lê a entrada em 'buffer' e gera o array de 
     sufixos */
  build_suffix_array(buffer);

  int curr = rand() % W.size();
  for(int wleft = 100; wleft > 0; wleft--){
    
    /* Encontra a primeira ocorrencia, no vetor 
       ordenado, da palavra word[curr] */
    int j = binsearch(curr);
    
    /* Para todos os trechos no texto que têm as k
       primeiras palavras iguais ao trecho corrente, 
       escolha uma aleatoriamente */
    int tmp_index;
    for(int i = 0; j + i < W.size() && 
	  wordncmp(W[curr], W[P[j + i]]) == 0; i++)
      if (rand() % (i+1) == 0)
        tmp_index = P[j + i];
    curr = tmp_index + 1;
    if (curr + k - 1 >= (int) W.size()) break;
    printf("%s ", W[curr + k - 1]);
  }
  printf("\n");
}

O código completo encontra-se aqui.

Conclusão

Com esse capítulo eu fecho a leitura do livro Programming Pearls do Jon Bentley. A minha impressão é que o livro é mais voltado para programadores sem um background teórico em computação. O conteúdo não foge muito do que aprendemos durante cursos da graduação na Unicamp e nos treinos de maratona, exceto pelos tópicos de geradores de números aleatórios e cadeias de Markov. Além disso, o autor fornece algoritmos bastante elegantes para diversos problemas clássicos.

A experiência de fazer posts conforme ia estudando, foi boa. Esse é um dos únicos livros técnicos que li do fim ao começo (pulando os apênces :P), embora a leitura seja bem leve. Já tenho outros livros na fila de leitura com os quais pretendo repetir a experiência.

Anúncios

Tarefa 8: Escola

Julho 9, 2010

O último laboratório da disciplina era sobre ordenação externa. Esse é um tópico que é dado na disciplina de estruturas de dados (embora não estivesse na ementa na vez que cursei). O problema é basicamente o seguinte: dado um arquivo muito grande em disco, queremos ordená-lo, sem ter que carregá-lo completamente na memória. A ideia para resolver é subdividir o arquivo em blocos de tamanho fixo e pequenos o suficiente para caberem em memória. Lemos cada bloco de uma vez na memória, ordenamos com um algoritmo de ordenação qualquer e escrevemos de volta no arquivo. Imagine agora que temos vários vetores ordenados e queremos fazer uma intercalação entre eles e gerar um único vetor ordenado. Observe que esta é uma generalização do passo do algoritmo Merge-sort.

No caso básico temos dois vetores ordenados e mantemos apontadores para o começo de cada um deles, Pa e Pb, por exemplo. Sejam a[1] e b[1] os valores dos elementos apontados por tais apontadores. Se a[1] for menor do que b[1], então A deverá vir primeiro no vetor final ordenado. Caso contrário será b[1] (no caso de empate tanto faz). Ou seja, colocamos o menor entre a[1] e b[1] no vetor final. Supondo que a[1] foi colocado, a pergunta que devemos fazer é: qual elemento poderia aparecer depois de a[1] num vetor ordenado? É claro que é b[1] ou a[1], pois estes são os menores elementos maiores do que a[1]. Então andamos com o apontador Pa em 1 posição e repetimos o procedimento.

Como generalizar essa ideia? Suponha agora que temos m vetores, dados em uma matriz a[m][n] e apontadores (P1, …, Pm) para o começo de cada um deles. O primeiro elemento no vetor de saída será o menor entre todos os elementos. Só que como os vetores estão ordenados, sabemos que o menor elemento está na primeira posição de algum dos vetores ou seja, queremos min(a[1][1], a[2][1], ….. a[m][1]). Seja i* o vetor com menor elemento. Colocamos então a[i*][1] na saída. Com argumentação semelhante ao caso base, sabemos que o próximo elemento a aparecer depois de a[i*][1] é min(a[1][1], a[2][1], …, a[i-1][1],a[i][2], a[i+1][1], …, a[m][1]). Que é equivalente a ardamos uma posição com o ponteiro de i*. Achar o menor entre dois elementos é fácil, mas e para n elementos? Bom, para isso podemos utilizar a estrutura de fila de prioridades. Dela conseguimos extrair o menor elemento em O(1) e inserir em O(log n). Assim, extraímos a[i*][Pi*] e inserimos a[i*][Pi*+1].

Qual a complexidade do algoritmo? Seja m o número de blocos e n o tamanho de cada bloco. Para cada bloco devemos realizar uma operação de ordenação sobre O(n) elementos, implicando em uma complexidade de O(m*n*log n). Após isso, temos a etapa de intercalação. Observe que a fila de prioridades nunca tem mais de um elemento por vetor, logo tem tamanho no máximo O(m). Isso é importante porque as complexidades das operações sobre a fila são sobre o número de elementos nela. Logo, a remoção é O(1) e a inserção O(log m). Como todo elemento de cada vetor entra e sai da fila, vamos fazer uma operação de inserção e remoção para cada um dos O(n*m) elementos, resultando na complexidade O(n*m*log m). No total temos O(n*m*(log n + log m)) = O(n*m*log(n*m)). Seja N=n*m o tamanho do arquivo. Então a complexidade desse algoritmo O(N*log N).

Um tira no jardim de infância (velho!)

Para quem leu o enunciado, verá que o problema não está descrito desta forma. Decidi colocar um contexo de treinamento contra incêncios de uma escola. Dá para fazer as seguintes correspondências: a escola representa o arquivo, os alunos representam os elementos do arquivo, as salas correspondem aos blocos em memória e o pátio junto com o diretor representam a fila de prioridades. Minha intenção com isso era tornar o problema mais interessante e quem sabe deixar a ideia por trás do algoritmo mais intuitiva. Não sei se foi devido às provas de fim de semestre ou à dificuldade do problema (ou porque muita gente já tinha passado na parte prática), mas essa foi a tarefa com menor número de submissões.


Tarefa 7: RPG

Julho 2, 2010

A tarefa 07 de MC202 consistia em simular uma batalha de RPG em turnos. São dados 2 equipes inimigas, cada qual com vários personagens com atributos diferentes, tais como força, velocidade, resistência e pontos de vida. Cada personagem tem um “período” inversamente proporcional a sua velocidade. Dados os períodos, podemos determinar os instantes de ataque de cada personagem. Quando dois personagens têm mesmo instante de ataque, existem alguns critérios de desempate que não cabe detalhar aqui.

Humano vs. Orc

Para determinar a ordem dos ataques, poderíamos fazer uma simulação discreta, por exemplo iterando sobre o tempo segundo a segundo e a cada instante verificar quem tinha um instante de tempo que caía bem naquele momento. A primeira desvantagem de tal método é que esse algoritmo é proporcional ao valor dos períodos, e a gente acaba iterando sobre instantes de tempo em que ninguém ataca. Além do mais, se os períodos forem números reais, esse tipo de abordagem pode ser impossível! Uma alternativa consiste em usar uma estrutura de dados chamada de fila de prioridades. A prioridade utilizada no caso é o próximo instante de ataque de cada personagem. Com uma fila de prioridades temos acesso ao elemento de maior prioridade em O(1). Assim, sabemos quem será o próximo atacante. Após efetuar o ataque, o próximo instante de ataque de uma personagem é a soma do instante atual e o período. Desta forma, basta reinseri-lo na fila com essa nova prioridade que em O(log n) conseguimos atualizar o heap mantendo suas propriedades.

Fila de Prioridades visualizada como árvore

Outro aspecto importante é a escolha do atacado. A estratégia de ambos os times consiste em atacar sempre o membro do time adversário com menos vida (mais alguns critérios de desempate). Uma observação importante é que todos do mesmo time “miram” no mesmo personagem inimigo até que este morra (porque se este já tinha menos pontos de vida, depois de sofrer os ataques continuará sendo o mais frágil). Isso nos possibilita ordenar inicialmente os membros dos times por ordem de não-decrescente de pontos de vida e, usando lista ligada, descobrir o membro a ser atacado em O(1), removendo-o da lista em caso de morte (também em O(1)). Aqui porém, eu permiti fazer do jeito força-bruta O(n) para escolher o mais fraco.

Esse método de simulação é mais eficiente do que a primeira proposta, sendo O(m log m), onde m é o número de turnos realizados antes de o jogo terminar. Porém, m pode ser proporcional aos valores de entrada, tornando nosso algoritmo pseudo-polinomial. Um exemplo seria dois times com um jogadores cada, um deles o personagem tem ataque 1 e no outro o personagem tem velocidade 0 e vida V. É fácil ver que o número de turnos é O(V), que pode ser tão grande quanto quisermos. Neste caso poderíamos ter feito algo mais eficiente, tal como calcular quantas vezes o personagem do time 1 ia atacar antes do personagem do time 2, mas acho que precisamos de uma ideia mais elaborada para funcionar em casos mais gerais. Porém, não cheguei a nenhuma conclusão se é possível resolver a simulação “analiticamente”.


Tarefa 6: AVL

Maio 29, 2010

Dando continuidade às tarefas de MC202, vou comentar sobre o laboratório 6, que consistia em implementar uma árvore AVL.

A árvore AVL é uma árvore binária balanceada de busca. Isso garante que a altura da árvore fica em torno de log n, onde n é o número de elementos na árvore. Tal propriedade é que possibilita busca, insersão e remocão em tempo log n. Porém, para mantear a árvore balanceada são necessárias operações chamadas de rotação (esquerda ou direita), o que torna a implementação de tal estrutura relativamente complexa.

Considerando que o laboratório pudesse ser complicado demais para se fazer em duas semanas, decidi fornecer um conjunto de cabeçalhos das funções, mais a estrutura da árvore para guiar os alunos na implementação. Isso ainda serve para evitar que os alunos enviassem código pronto copiado da internet, uma vez que dificilmente haverá um código que utiliza a mestra estrutura que eu defini.

Além do mais, optei por cobrar apenas a insersão na árvore, ficando os alunos incumbidos de implementar as rotações. A deleção me pareceu complicada demais a primeira vista e preferi não exigir.

O resultado foi melhor do que eu esperava. O número de submissões que vinha decrescendo a cada laboratório, voltou a atingir 40 (lembrando que para a tarefa Python, esse número fora 27). A minha impressão é de que uma boa parte da dificuldade dos alunos menos experientes é definir as estruturas e funções que servirão de base para a implementação. Ao fornecer a estrutura básica, deixei a eles apenas o trabalho de aplicar os algoritmos da teoria.

O único porém é que uma das minhas funções consistia em, dado um nó i, calcular a altura da subárvore a partir dele. Como havia um campo altura na estrutura do nó, minha ideia era, sempre que houvesse algum tipo de rotação envolvendo i, atualizar sua altura com o máximo da altura do filho esquerdo e do filho direito mais um. Só que essa função deveria ser O(1), uma vez que já temos calculado os valores das alturas do filho esquerdo e direito (hipótese). O problema é que a maior parte dos alunos calculou tal altura recursivamente, chamando a função novamente tanto para o filho esquerdo quanto para o direito, e isso torna a complexidade O(n), o que inutiliza a eficiência da inserção, que era O(log n).

Apesar de tudo, fiquei satisfeito com o resultado e sinto que desta forma os alunos focam mais em entender e aplicar a teoria do que desenvolvimento de sofware. Entretanto essa última habilidade é igualmente importante e deve ser trabalhada. No próximo laboratório, optei por um esquema parecido com o da AVL, mas pretendo deixar a implementação do último trabalho, o qual ainda não defini.


Tarefa 5: DNA

Maio 21, 2010

Nesse extenso intervalo sem postar, especifiquei três laboratórios: python (listas generalizadas), do qual falei no post anterior; dna (árvores binárias), que comentarei nesse post; e avl, a tarefa que está sendo feita atualmente.

A tarefa basicamente pede para avaliar uma expressão através de árvores binárias. Não é difícil encontrar implementações que envolvam avaliações de expressões do tipo:

E para não acontecer de o pessoal pegar código pronto, optei por modificar ligeiramente a especificação. Ao invés de avaliar expressões envolvendo números, o laboratório consistia em avaliar conjuntos. Ao invés de números a expressão consistia de variáveis representando um conjunto de características e no lugar dos operadores de adição, subtração, etc, inclui os operadores de união, interseção e diferença.

A partir daí, deixei os alunos implementarem do jeito que quisessem. Porém, alguns truques facilitam a tarefa:

1) As características eram dadas como strings. Porém, podemos guardar as strings em um dicionário (vetor de strings) e trabalhar só com o índice das strings nesse dicionário (int).

2) Quando os elementos do conjunto estão ordenados, é mais simples (e eficiente) implementar as operações sobre conjuntos. A ideia é parecida com a do merge sort: mantemos ponteiros para cada um dos conjuntos A e B. No começo cada qual aponta para o primeiro elemento do seu respectivo conjunto. Seja o valor do elemento apontado pelo ponteiro do conjunto A e o equivalente para o conjunto B. Na união, se , incluímos na união e andamos com o ponteiro de A. Se fazemos o mesmo com o ponteiro de B, se , incluímos qualquer um dos dois, mas apenas um, pois em conjuntos não consideramos elementos repetidos, e então andamos com ambos os ponteiros. Entendida a ideia, é simples derivar o algoritmo para a operação de interseção e diferença.

Para padronizar a resposta e comparar com minha saída no SuSy, exigi que as características do conjunto final estivessem ordenadas. Porém os alunos não tinham visto ordenação ainda, então passei um código que supostamente iria ordenar um vetor de strings:

qsort(saida, n, sizeof(char*MAXLEN), cmp);

Para quem não sabe, o qsort é uma função que implementa o quicksort e está disponível na biblioteca padrão do C. A função exige que você passe uma função de comparação por parâmetro, que compara duas strings. Porém, se o vetor de strings foi alocado estaticamente (minha sugestão inicial), a função não funciona. Uma alternativa é declarar o vetor como um vetor de ponteiros de char e alocar cada string dinamicamente (porém com tamanho fixo MAXLEN). Aí sim funciona. Outra alternativa, a que acabei sugerindo após descobrir o erro, é ordenar apenas os índices do vetor. Para isso nós orderamos um vetor auxiliar (vetor de permutação), indicando que a posição do i-ésimo elemento é . Inicialmente .

A função de comparação recebe dois inteiros i e j, mas na verdade compara as respectivas linhas da matriz (com strcmp). A vantagem desse método é que as strings continuam no mesmo lugar. O que muda são apenas os índices.


Tarefa 4: Python

Maio 21, 2010

O último post foi a mais de um mês atrás, pois estive muito ocupado. Tive prova e entrega de trabalho de PLI e ainda, com o fim da OBI, comecei a preparar aulas para o pessoal da maratona. Agora com o horário mais folgado, decidi escrever sobre o laboratório 04 de MC202.

O tema central da tarefa 4 de MC202 eram listas generalizadas. Sinceramente não me lembro de ter visto essa estrutura de dados em MC202 (talvez tenha esquecido, afinal cursei-a em 2005). Mas para quem conhece árvores essa estrutura é relativamente fácil de aprender.

Eu estava pensando em algum contexto em que fosse necessário o uso de tais listas, quando me deparei com a estrutura “List” da linguagem de programação python. Ela é justamente uma implementação de listas generalizadas. Propus então que o pessoal implementasse um interpretador para comandos envolvendo as listas generalizadas.

Para simplificar as coisas, restringi os tipos dentro da lista a inteiros. Além do mais os comandos possíveis eram apenas o de impressão e o de atribuição. Mesmo com essas restrições, o exercício ficou bem trabalhoso. Dei duas semanas de prazo e mesmo assim a taxa de submissão foi 27/47 (57,44%) e a média geral foi 3.01 :(


Tarefa 3: Minotauro

Abril 12, 2010

O professor da disciplina sugeriu que o laboratório 3 de MC202 fizesse uso de recursão. Apesar de ser uma técnica ensinada em MC102, é um conceito que demora a ser aprendido, ao meu ver porque exige maior abstração. Enfim, devido a essa dificuldade tal tópico costuma ser revisto em MC202.

A ideia que tive foi a de um problema de percorrer labirintos. A tarefa foi contextualizada com uma história da mitologia grega em que Teseu procura o Minotauro e para não se perder no caminho de volta utiliza uma corda cedida por Ariadne.

Para não ter que tratar múltiplas soluções, especifiquei uma regra de percurso: primeiro tenta-se ir em frente, se não houver sucesso, tente ir à direita e finalmente à esquerda. O primeiro passo consiste em encontrar a entrada, representada por um buraco na parede mais externa. É garantido que haverá exatamente um buraco. Depois disso, aplicamos a técnica de backtracking seguindo as regras acima até encontrar o Minotauro (representado pela letra ‘M’).

Para especializar um pouco mais o problema, exigi no enunciado que fosse impresso, além do caminho utilizado para chegar da entrada ao Minotauro, o caminho por onde ele passou. Essa informação adicional seria útil no caso em que o Minotauro não fosse encontrado, pois sem imprimir o caminho por onde Teseu passou, o mapa de saída seria igual ao de entrada. Porém, por distração acabei especificando que apenas fosse impressa uma string caso o Minotauro não fosse encontrado. Só percebi o erro que tinha cometido quando fui corrigir o laboratório de um aluno, cujo programa era mais ou menos o seguinte:

#include <stdio.h>
int main (){
    printf("O Minotauro eh lenda.");
}

Ele ia passar em 2 dos 12 testes do SuSy se não tivesse esquecido de pular linha.

Alguns alunos também tentaram detectar a existência do Minotauro pelo mapa de entrada: se o caracter ‘M’ fosse rodeado por paredes (‘X’) então ele não poderia ser encontrado. Essa é uma condição suficiente, mas não necessária (por quê?)

Finalmente, não sei se o enunciado é que ficou confuso demais ou se o conceito ainda não foi absorvido, mas o fato é que a maior parte dos alunos não entendeu que não era preciso voltar explicitamente para trás quando uma das direções não era a certa. Isso porque depois de retornar das chamadas recursivas obtemos esse efeito implicitamente.