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

Mapas de Símbolos Proporcionais

Abril 17, 2011

Sexta-feira passada apresentei uma palestra na série de seminários do LOCo. Falei sobre o problema que estou atacando no mestrado.

Um mapa de símbolos proporcionais emprega símbolos para exibir eventos associados a alguma localidade e intensidade. O símbolo é posicionado no local de ocorrência do evento e a sua área fica sendo proporcional à intensidade desse evento. Focamos em mapas que usam círculos opacos como símbolos. A figura abaixo é um exemplo representando as populações das maiores cidades do Brasil.

Note que há sobreposição entre os discos. Dependendo da ordem em que os empilhamos, pode ser que haja mais ou menos porções dos discos visíveis. Há casos ruins em que a borda do disco fica totalmente encoberta, como na figura abaixo.


Não podemos inferir o centro nem o raio do disco com bordo escondido.

Para tentar fazer com que o desenho tenha bastante borda visível, usamos uma métrica que consiste em maximizar o comprimento visível total dos discos. Com isso em mente, é possível definir um modelo de programação linear inteira, com um modelo que atribui cada disco a um nível.

Além do modelo básico, desenvolvemos algumas desigualdades adicionais para tornar o modelo mais forte, nos baseando em propriedades geométricas, que impedem certas configurações de acontecerem.

Também desenvolvemos duas técnicas de decomposição de instâncias. Um jeito trivial de decompor instâncias é considerar componentes de discos conexas de maneira independente.

Nossa primeira técnica de decomposição vem da observação que um disco que está contido no outro sempre pode ser desenhado por cima em uma solução ótima. Dessa forma, em uma instância como a da figura abaixo, a componente {a, b} pode ser desenhada de maneira independente de {c, d, e, f} e na hora de construir a solução ótima, basta desenhar a solução obtida para {a, b} em cima da solução {c, d, e, f}.

Componente {a,b} está contida em {f} e pode ser resolvida separadamente.

Podemos definir um grafo Gs sobre os discos de S, com conjunto de vértices correspondendo aos discos e há uma aresta (i, j) em Gs se os discos correspondentes se interceptam. Falei sobre esse tipo de grafo em um post anterior.

A outra técnica consiste em remover um ponto de articulação de Gs e replicá-lo nas componentes conexas resultantes, como na figura abaixo.


O disco f representa um ponto de articulação em Gs. As figuras (ii), (iii) e (iv) são as componentes resultantes de sua remoção, com f replicado.

Mostramos que é possível resolver cada componente com o ponto de articulação replicado de maneira independente. Depois, basta juntar os discos mantendo a ordem relativa de cada sub-solução. Isso pode ser feito através de uma ordenação topológica.

Implementamos todas essas ideias e reportamos os resultados. As instâncias testadas foram as mesmas de um trabalho anterior no qual nos baseamos. As técnicas de decomposição foram efetivas na redução do tamanho das instâncias e o resolvedor XPRESS conseguiu resolver nosso modelo para quase todas as instâncias. Porém, ficaram algumas componentes sem serem resolvidas, o que nos motiva a procurar novos modelos e novas desigualdades.

Esse nosso trabalho foi aceito na Computational Geometry and Applications 2011.


Leilões

Abril 12, 2011

Recentemente me indicaram um site de leilões, http://www.olhonoclick.com.br/. A ideia é bem simples, mas com um mecanismo muito inteligente. Nesse leilão, você paga R$1,00 por lance. A cada lance dado o valor do produto final em R$0,01 e um contador de 15 segundos é iniciado. Quando o contador zera, a última pessoa que deu lance leva o produto.

Em geral a pessoa que leva o produto paga cerca de apenas 10% do valor original. O vendedor, porém, é o que mais ganha com isso. Sendo V o valor do item, a pessoa que leva paga 0,1V. Mas como um incremento de 1 centavo dá ao vendedor R$1,00 ele ganha 100 vezes o valor pago pelo último comprador, ou seja, 10V.

Quem leva o prejuízo mesmo são as pessoas que deram lance mas não levaram o produto. Porém ninguém se importa muito de gastar uns R$5 com risco de levar um item por 10% do preço. Só que como são muitas pessoas que dão pequenos lances, o negócio dá lucro.

Eu achei a ideia desse tipo de leilão mais próximo ao de uma loteria, onde muitas pessoas contribuem com pouco para que pouquíssimas pessoas levem muito. Há um post relacionado muito bacana, o “Valor do Dinheiro (e loterias)”, do Renato Paes Leme.

Leilões me lembram de um amigo do laboratório, o Carlos, que estuda leilões combinatoriais. Eu não sei nada sobre isso mas parece ser um assunto interessante. Particularmente, esse tipo de leilão é chamado penny auctions (auction é leilão em inglês). Dia 11 de maio haverá o VI Workshop de Teses, Dissertações e Trabalhos de Iniciação Científica do IC Unicamp, onde ele irá apresentar seu trabalho com leilões.

Leilões combinatoriais são um ramo de teoria dos jogos. Não sei nada sobre o assunto, mas é uma ferramenta que pode auxiliar na tomada de decisão, o que a torna interessante do ponto de vista de pesquisa operacional, sobre a qual tenho interesse. Há no laboratório professores que estudam teoria dos jogos algoritmica, como o prof. Flávio. Ele já ofereceu uma disciplina sobre isso e os slides podem ser escontrados em sua página.

Gostaria de aprofundar mais no assunto, mas isso desviaria um pouco do meu foco no momento. Fica para estudos futuros :)


Escrevendo com o emacs

Abril 3, 2011

Desde 2005 uso emacs devido às aulas introdutórias de programação. Nunca estudei muito a fundo esse editor que é capaz de realizar incontáveis tipos de tarefas. Mas aprendi algumas funcionalidades interessantes.

Sátira do xkcd com diversos editores (clique para ampliar)

Editando LaTeX

O auctex é uma extensão que facilita a edição de documentos LaTeX. Para quem usa ubuntu, basta instalar o pacote auctex.

Depois de instalar essa extensão, ao abrir arquivos .tex uma nova interface aparecerá, parecida com a imagem abaixo:

O botão do leão é equivalente a executar o comando latex no arquivo atual. Ele gera um arquivo no formato .dvi. O botão do óculos abre o arquivo .dvi com o programa xdvi. O botão do livrinho executa o comando bibtex sobre o arquivo .aux gerado com o comando latex. O último botão é um preview dentro do próprio emacs, mas eu particularmente não gosto.

Nota: o padrão do auctex é usar o comando latex que gera arquivos dvi. É possível mudar esse padrão para sempre gerar pdf’s usando o comando pdflatex. Para isso, adicione a seguinte linha ao arquivo de configuração do emacs, em ~/.emacs:

(add-hook 'LaTeX-mode-hook 'TeX-PDF-mode)

Observe ainda que existem diferenças entre os comandos latex e pdflatex. Uma delas é que latex só trabalha com imagens no formato .eps enquanto pdflatex trabalha com vários tipos de formatos (pdf, jpg, png), mas não .eps.

Correções ortográficas

O emacs tem uma funcionalidade de indicar erros ortográficos, chamada flyspell. O dicionário padrão é o inglês, mas é possível alterar para português brasileiro. Antes de mais nada, é preciso instalar suporte do aspell a essa linguagem. No ubuntu, basta instalar o pacote aspell-pt-br.

Depois, para trocar o dicionário, abra a linha de comandos no emacs (Alt+X) e digite o seguinte comando:

ispell-change-dictionary

Ele vai pedir o argumento, o qual deve ser:

portugues

Agora, se o seu texto já está escrito e você quer fazer a revisão ortográfica, abra a linha de comandos e digite:

flyspell-buffer

Se você quer começar a fazer a revisão ortográfica conforme vai escrevendo, use

flyspell-mode

As palavras que não estiverem de acordo com o dicionário ficarão destacadas. Clicando com o botão do meio do mouse aparece um menu com sugestões de correção ou opções de ignorar ou adicionar ao dicionário. Para ir para o próximo erro, é possível usar o comando flyspell-goto-next-error ou o atalho

Ctrl+,