Contando Ocorrências de Números em C, C++ e Common Lisp

Mais uma vez, deparei-me com mais uma situação em que precisei explicar para colegas a respeito de algum conceito de programação que não era muito trivial. Desta vez, trata-se de um exercício de programação onde, dada uma entrada de n números, que podem ser diferentes ou não, precisamos contar as ocorrências de cada uma e imprimi-las na tela.

Existem várias formas de resolver este problema, provavelmente até mesmo sem armazenar absolutamente nada extra memória. Um dos meus colegas, inclusive, encontrou uma maneira bem interessante, envolvendo ordenar os números; o fato de estarem agrupados sinalizaria apenas a necessidade de contá-los e exibir o resultado na tela, a cada grupo.

Mas por que vamos facilitar, se podemos complicar? :D

Neste artigo, pretendo explorar três formas diferentes de resolver o problema: a primeira em C, muito parecida com o que fiz no momento de resolução do exercício; a segunda, em C++, tirando o máximo proveito da STL; e a terceira, em Common Lisp, para efeitos comparativos.

A ideia principal para resolver este problema em C é criar uma estrutura de dados capaz de armazenar repetições para cada número; ou seja, uma forma de mapear cada número, como uma chave, para seu respectivo número de repetições.

Primeiramente, precisamos de um struct que represente este mapeamento número => repetição. Digamos, também, que vamos receber dez números, que iremos armazenar em um vetor simples.

#include <stdio.h>

// Estrutura representando as repetições para um número
typedef struct {
    int num;
    int rep;
} repetition_t;

// Vetor de números a serem recebidos
int numbers[10];

// Entradas
{
    int i;
    for(i = 0; i < 10; i++) {
        scanf("%d", &numbers[i]);
    }
}

Agora, vamos analisar o que faremos a seguir. Sabemos que temos que contar números repetidos. No pior dos casos, pode ocorrer de os dez números serem diferentes. Nesta situação, teremos dez entradas de repetições diferentes.

Sendo assim, podemos nomear um vetor baseado no máximo de repetições possíveis, e um contador para as repetições já registradas:

int          num_repetitions = 0;
repetition_t repetitions[10];

Podemos, agora, percorrer o vetor de números. Para cada número no vetor, verificamos se já há uma entrada registrada para ele no nosso vetor de repetições.

Se há uma repetição registrada, apenas incrementamo-na. Se não, incrementamos o número de repetições registradas, e criamos uma nova entrada, começando a contar o número de repetições a partir de 1:

int i, j;
for(i = 0; i < 10; i++) {
    int entry_found = 0;
    for(j = 0; j < num_repetitions; j++) {
        if(numbers[i] == repetitions[j].num) {
            entry_found = 1;
            repetitions[j].rep++;
            break;
        }
    }
    if(!entry_found) {
        repetitions[num_repetitions].num = numbers[i];
        repetitions[num_repetitions].rep = 1;
        num_repetitions++;
    }
}

Depois disso, tudo o que nos resta é iterar sobre as repetições registradas, imprimindo o número e a quantidade de repetições registradas para ele.

for(i = 0; i < num_repetitions; i++) {
    printf("%d => %d\n",
           repetitions[i].num, repetitions[i].rep);
}

Teremos a seguinte interação no console:

% g++ find_numbers.c 
% ./a.out 
1 1 1 3 5 5 7 8 9 9
1 => 3
3 => 1
5 => 2
7 => 1
8 => 1
9 => 2

Vamos ser honestos. Tudo o que fiz em C foi emular, de forma ineficiente (para um caso com mais números), uma estrutura que conhecemos bem em C++: um std::map. E é exatamente por isso que, ao invés de tentarmos emulá-la novamente, usaremos o que a linguagem tem a nos oferecer como algo pré-implementado.

Vamos começar da mesma forma: declarando o que é necessário para registrar as repetições. Teremos nosso vetor de dez números, e um std::map registrando as repetições.

#include <iostream>
#include <map>

// Declarações
int numbers[10];
std::map<int, int> repetitions;

// Entrada
for(int i = 0; i < 10; i++) {
    std::cin >> numbers[i];
}

Agora, iteramos sobre os números. Da mesma forma, verificamos se já os registramos; se sim, é só uma questão de incrementá-los. Se não, basta criarmos a chave e realizarmos a primeira atribuição para aquele número.

ERRATA: Na realidade, não é necessário verificar se a chave já está registrada, em um std::map! Basta realizar a incrementação, uma vez que C++ inicializa as chaves com o valor nulo do tipo, ou seja, neste caso, com 0. Obrigado ao Paulo Alvarenga por apontar isso para mim via Facebook.

for(int i = 0; i < 10; i++) {
    repetitions[numbers[i]]++;
}

Por fim, iteramos sobre o mapa e imprimimos a mesma relação de chave para repetição. Mas faremos isto com uma sintaxe limpa, baseada em C++11:

for(auto& pair : repetitions) {
    std::cout << pair.first << " => " << pair.second << std::endl;
}

Eis a interação no console.

% g++ --std=c++11 find_numbers.cpp 
% ./a.out 
1 1 1 3 5 5 7 8 9 9
1 => 3
3 => 1
5 => 2
7 => 1
8 => 1
9 => 2

Common Lisp é uma linguagem madura. Em termos de recursos esperados por um programador, digamos, no caso de contêineres, ela não decepciona. Assim como em C e C++, há um enorme número de maneiras para resolver nosso problema. Ao invés de escolher uma maneira mais "esperta", vou adequar a solução em CL às outras soluções: armazenar os números, criar um mapa e estabelecer uma relação entre chave e número de repetições.

Começaremos criando uma lista de números – que equivale a um átomo de nulidade –, e também criando a nossa estrutura que armazenará a relação chave/repetições: Uma Hash Table.

(defparameter *numbers* nil)
(defparameter *repetitions* (make-hash-table))

;; Entrada
(dotimes (i 10)
  (push (read) *numbers*))

Uma coisa interessante a notar é que os números serão lidos na ordem inversa aos casos anteriores: como estamos utilizando uma lista para armazenar nossos números, a função push modificará *numbers*, colocando o número diretamente na frente da lista.

Nosso próximo passo é iterar sobre cada um dos elementos e verificar se eles são chaves da hash table, como fizemos nos outros exemplos. Se sim, incrementamos o elemento; se não, definimo-no pela primeira vez com um valor 1.

(loop for x in *numbers*
   if (gethash x *repetitions*)
   do (incf (gethash x *repetitions*))
   else do (setf (gethash x *repetitions*) 1))

Este comando pode parecer um complicado à primeira vista, então vou me esforçar para explicá-lo mais um pouco.

Este é o famigerado macro loop. Alguns lispeiros não gostam muito dele porque, muitas vezes, utilizar este macro também implica utilizar praticamente uma linguagem diferente de Common Lisp, própria para ser usada dentro deste macro. Estou utilizando ele exatamente para evitar um uso extra de estruturas de controle de fluxo.

A instrução (gethash chave hash-table), assim como em C++, funciona como uma forma tanto de recuperar quanto atribuir um valor a uma chave qualquer. Se a chave não existir na Hash Table, esta instrução retorna nil, equivalente a falso; se existir, ela retorna o valor associado, tratado como verdadeiro. (incf variável) é uma instrução que incrementa diretamente o valor associado à chave, quando aplicado a (gethash ...). Já (setf variável valor), independente de a chave já existir no Hash Table ou não, realiza uma atribuição de um valor a uma chave.

Como você pode ver pela minha descrição, isto em nada difere do que fizemos em C++; a única diferença é a sintaxe e a estrutura em si, que funcionam praticamente da mesma forma.

Para finalizar, iteramos sobre nosso Hash Table, imprimindo as relações. Para tanto, não utilizaremos um loop explícito, mas sim a função maphash: ela é responsável por chamar uma função que indicarmos para cada par (chave, valor) no mapa:

(maphash (lambda (key value)
           (format t "~a => ~a~%" key value))
         *repetitions*)

Podemos executar o código como script, utilizando o Steel Bank Common Lisp:

% sbcl --script find-numbers.lisp --no-linedit
1 1 1 3 5 5 7 8 9 9
9 => 2
8 => 1
7 => 1
5 => 2
3 => 1
1 => 3

Como você pode ver, não importa a linguagem que você venha a utilizar; você será capaz de resolver problemas simples como este. Mas acredito que seja interessante observar o problema sendo resolvido da mesma forma, em várias linguagens. Esta aproximação cria uma espécie de pedra-de-roseta, algo que poderia servir para o aprendizado de várias linguagens, ainda que não representem a forma de resolver o problema com a melhor performance.

Como dica para você, deixo a seu cargo reimplementar este ou outro problema que tenha resolvido, em uma linguagem diferente da inicial, ou até mesmo com outra estratégia diferente da mais óbvia. Uma mudança de perspectiva pode significar uma nova forma de explorar seu próprio raciocínio lógico.