Programming Pearls: Parte 1

Estou lendo o livro “Programming Pearls” do Jon Bentley. O livro consiste de um agregado de diversas colunas (publicadas no Communications of ACM) abordando aspectos práticos de programação. Uma curiosidade: Jon Bentley é autor do conhecido algoritmo de geometria computacional para encontrar as interseções de um conjunto de segmentos de reta, o algoritmo de Bentley-Ottmann.

O livro é dividido em 15 colunas, agrupadas em 3 partes. Pretendo fazer posts comentando as partes que mais gostei em cada parte. Começo pela parte I, que abrange as colunas 1 a 5.

Coluna 1: Cracking the Oyster

Nesse capítulo o autor apresenta um problema de ordenar um arquivo com entradas com valor de 1 a únicas, com limitação de memória.

Podemos usar um algoritmo de ordenação linear. A sacada é usar um vetor de bits. O i-ésimo bit é 1 se o valor i está no arquivo. Logo são necessários bits ao invés dos se fôssemos usar inteiros de 32-bits.

Coluna 2: Aha Algorithms

Aqui ele apresenta alguns algoritmo de “sacada”. O que achei mais interessante foi o seguinte: rotacionar um vetor de tamanho n, i posições à equerda, em tempo O(n) e espaço adicional O(1).

A ideia que eu tive inicialmente satisfaz as restrições de tempo-espaço, mas é bem complicada. Ao rotacionar k posições, sabemos que v[0] receberá v[i] e v[i] receberá v[2i] (sendo que talvez 2i eventualmente dê a volta do vetor). Seguimos trocando v[ki] com v[(k+1)i] até que alguma hora voltamos no 0.

O problema é que isso pode não percorrer todos os elementos. Considere um vetor v com 6 elementos e que queremos rotacioná-lo em 2 posições.

Aqui temos v[0] <- v[2] <- v[4] <- v[0]. Precisamos fazer também iniciando em v[1], ou seja, v[1] <- v[3] <- v[5] <- v[1]. A pergunta é: como saber quando um elemento não foi ainda coberto, se só podemos usar um número constante de espaço extra?

Para isso, temos a seguinte proposição: Seja m = mdc(i, n). Então um ciclo iniciado no elemento v[x] cobre a posição j se e só se

Esboço da prova: Se j é visitado, então para algum k inteiro não-negativo, ou seja, x + ki = qn + j, para algum q inteiro não-negativo. Como por definição m divide i e n, o resto de j por m dá x. Se j não é visitado, dá para mostrar que o resto de j por m é diferente de x.

No exemplo acima, mdc(i=2, n=6) = 2. Logo, o ciclo iniciado em 0 vai cobrir 0, 2 e 4 e o iniciado em 1 vai cobrir 1, 3 e 5.

Um corolário dessa proposição é que podemos percorrer m ciclos, começando de 0, 1, …, m-1, que todos os elementos serão contemplados.

O autor apresenta uma solução extremamente simples e elegante. Primeiro, divida o vetor V em 2 partes. De 0 a i-1 e de i a n-1. Chame-as respectivamente de A e B.


Vetor original

Rotacionar o vetor correspondente à figura acima resulta na figura abaixo.

Vetor rotacionado

Que é simplesmente trocar os blocos A e B de lugar. Para fazer isso, considere a operação que inverte a ordem dos elementos em um vetor. É fácil fazer in-place e em O(n).

Vamos denotar por A’ e B’ os vetores A e B invertidos. Ao inverter o vetor V = AB, teremos B’A’ . Ora, para chegar em BA, basta inverter separadamente A’ e B’!

Coluna 3: Data Structures Program

Esse capítulo discute o uso de estruturas de dados, principalmente vetores, não para melhorar a eficiência dos algoritmos, mas para diminuir o tamanho do código. Não é apresentada nenhum técnica interessante, é mais uma dica mesmo.

Coluna 4: Writing Correct Programs

Aqui o autor faz uso de assertivas (os assert‘s em C e python), incluindo pré e pós condições para checar invariantes de laços e funções. Para isso ele usa como exemplo o algoritmo de busca binária, que é relativamente simples, mas muito tricky de implementar. (Tão tricky que o caderno de algoritmos do time do ITA para o mundial da maratona de 2008 tinha umas 4 implementações de busca binária).

Discutindo sobre quais assertivas usar para ter certeza de que a busca binária termina, ele apresenta dois exercícios interessantes. Primeiro, mostrar que o seguinte algoritmo termina:

while x != 1:
    if x é par:
        x = x/2
    else:
        x = 3x + 1

Esse exercício é praticamente uma pegadinha, pois a resposta do exercício é conhecida como a conjectura de Collatz, um problema em aberto.

O outro é o seguinte: Dado um saco com W feijões brancos e B feijões pretos, repita o seguinte procedimento: escolha dois feijões aleatórios desse saco. Se tiverem a mesma cor, joga fora ambos os feijões e devolve um feijão preto ao saco. Se forem de cor diferente, devolve um feijão branco. Pede-se para mostrar que isso eventualmente terminar e caracterizar o resultado em função de W e B.

Coluna 5: A small matter of programming

Esse capítulo parece ser um complemento do anterior. Além de assertivas, o autor introduz testes automáticos e medidas de tempo ao código da busca binária.

Ele chama esses componentes adicionais de scaffolding, que faz alusão aos andaimes que se usam em construção de prédios e depois são removidos. Ao contrário da construção civil, porém, pode ser uma boa prática deixar esses componentes em código de produção (desde que o overhead não seja muito grande).

Os comentários estão fechados.

%d bloggers like this: