Programming Pearls: Parte 3

Eu ia descrever as colunas 11 a 15 nesse post, mas devido à grande quantidade de informação e coisas interessantes para descrever o post ficaria gigantesco. Vou me restringir às colunas 11 a 13. Em um post futuro fecho com as colunas 14 e 15.

Coluna 11: Sorting

Aqui são revisados os algoritmos de insertion sort e quicksort. O que achei mais interessante nessa coluna foi um exercício em que se pede para ordenar um conjunto de strings de bits de diferentes tamanhos. A solução apresentada é bem elegante:

std::string *x[N];
void bsort(int lo, int up, int depth){
    if(lo <= up) return;
    for(int i=lo; i<=up; i++)
        if(x[i]->length() == depth)
            std::swap(x[i], x[lo++]);
    int m = lo;
    for(int i=lo; i<=up; i++)
        if(x[i]->at(depth) == '0')
            std::swap(x[i], x[m++]);
    bsort(lo, m-1, depth);
    bsort(m, up, depth + 1);
}

No código C++ acima, o conjunto de strings é armazenado em um array de ponteiros para std::string. O uso de ponteiros é necessário para que a troca de elementos seja feita em O(1) e não no tamanho das strings.

A hipótese em cada chamada da recursão é de que o intervalo [lo, up] possui os depth-1 primeiros bits iguais.
O primeiro for trata se separar as strings que têm tamanho exatamente depth, já que elas virão primeiro na ordenação lexicográfica.

O segundo for, separa as strings restantes pelo próximo bit em que elas diferem, ou seja, o depth-ésimo bit. Essa separação é semelhante àquela feita no pivoteamento do quicksort. Depois desse laço, as strings entre [lo, m-1] têm os depth primeiros bits iguais e aquelas entre [m, up] também. Logo, podemos chamar recursivamente a função pois mantivemos a invariante.

É possível verificar que estamos percorrendo cada string um número de vezes igual a seu comprimento. Em cada chamada estamos avançando um bit e depois que atingimos seu comprimento, deixamos a string de lado.

Coluna 12: A Sample Problem

Nessa coluna é abordado o problema de se gerar m números aleatórios entre 1 e n, sem repetição. São apresentados vários algoritmos muito elegantes! A primeiro deles foi proposto pelo Knuth. Segue uma implementação em C++

void gen_knuth(int m, int n){
    for(int i=0; i<n; i++)
        if(rand() % (n-i) < m){
            std::cout << i << "\n";
            m--;
        }
}

Onde a função rand() retorna um inteiro entre 0 e RAND_MAX (que depende de implementação, mas é pelo menos 32767). O que se deseja com rand() % (n-i) é gerar inteiros entre 0 e n-i-1, inclusive, com probabilidade uniforme. A distribuição não fica totalmente uniforme se RAND_MAX não for múltiplo de n-i, mas na prática é uma boa aproximação.

O algoritmo acima imprime m valores com probabilidade uniforme. A prova da uniformidade das probabilidades está no livro do Knuth, mas ainda não tive como consultá-la. Por outro lado, é fácil mostrar que o algoritmo sempre imprime m elementos. Ele não imprime mais do que m elementos pois quando m = 0, o if é sempre falso. Se n-i <= m, o if é sempre verdadeiro. Esse algoritmo é O(n) de tempo e O(1) de espaço. Se n for muito grande, o algoritmo fica muito lento.

Uma outra versão é usando conjuntos para marcar quais elementos já foram selecionados. Um código se encontra abaixo, usando a implementação set da STL. Para quem não sabe, essa estrutura é implementada usando árvore binária balanceada (acho que é a red-black tree), ou seja, inserir um elemento em um set, decidir se um elemento está no set ou remover um elemento de um set são operações que levam tempo O(log n).

void gen_set(int m, int n){
    std::set<int> s;
    while (s.size() < m)
        s.insert(rand() % n);
    std::set<int>::iterator it;
    for(it = s.begin(); it != s.end(); it++)
        std::cout << *it << "\n";
}

Nessa versão sorteamos um número até tirar um que não tenha sido escolhido ainda. Note que esse algoritmo é probabilístico. Assim, podemos descrever sua complexidade em termos do número esperado de vezes que teremos que sortear um número até encontrar m elementos distintos. Esse problema é conhecido como o problema do colecionador de figurinhas e diz que o número esperado de sorteios necessários é O(n log n). Como a inserção é feita em O(log n), o algoritmo tem complexidade O(n log^2 n).

Robert Floyd propôs uma solução que não faz inserções desnecessárias e é determístico.

void gen_floyd(int m, int n){
    set<int> s;
    for(int j = n - m; j < n; j++){
        int t = (rand() % (j+1));
        if(s.find(t) == s.end()) s.insert(t);
        else s.insert(j);
    }
    set<int>::iterator it;
    for(it=s.begin(); it!=s.end(); it++)
        cout << *it << "\n";
}

Esse algoritmo é O(m log n). Não encontrei a prova de que nesse algoritmo os elementos são escolhidos de maneira equiprovável.

Um dos exercícios dessa coluna pede para escolher um número aleatório com probabilidade uniforme de uma lista, sem que se conheça o tamanho da lista! Pode-se pensar que é a versão online do algoritmo de escolher um número aleatório de uma lista.

O algoritmo é bem simples:

int rand_online(){
    int v, pick, cnt = 1;
    while (std::cin >> v){
        if (rand() % cnt == 0)
            pick = v;
        cnt++;
    }
    return pick;
}

O algoritmo lê os elementos a serem sorteados sem no entanto armazená-los. A cada elemento lido v, o algoritmo troca o elemento anteriormente armazenado por v com probabilidade 1/i. Dá para mostrar que a chance de um elemento ser escolhido é uniforme.

Coluna 13: Searching

Fiquei com a sensação de que o nome dessa coluna não espelha muito bem seu conteúdo. Aqui basicamente são apresentadas diferentes estruturas de dados como: array e listas ligadas para manter os elementos do conjunto de maneira ordenada, uma árvore de busca binária (não balanceada, mas que funciona bem nesse caso porque os números inseridos são aleatórios), além de estruturas especializadas que aproveitam o fato dos elementos do conjunto serem inteiros como um array de bits onde o i-ésimo bit é 1 se o inteiro i está no conjunto e uma espécie de hash, que vale a pena detalhar um pouco.

Dado que queremos sortear m elementos de 1 a n, criamos um array de m ponteiros para listas ligadas. Cada lista ligada representa um bucket. O primeiro bucket armazenará os valores de 0 a n/m-1, o segundo de n/m a 2(n/m)-1 e assim por diante. Ao inserir um número t no conjunto, mapeamos esse valor para o bucket correto através de k = t/(n/m). Aí basta inserir na lista ligada apontada pelo bucket k. Embora a inserção na lista seja linear no seu tamanho, como vamos inserir apenas m elementos com valores distribuídos de maneira uniforme, as listas em cada bucket tem tamanho esperado 1! Então essa inserção é muito rápida na prática.