array_of_doubles.c – Utilitários para arrays de double

Este é o ficheiro de implementação correspondente ao ficheiro de cabeçalho ou de interface array_of_double.h. Ambos correspondem ao módulo físico array_of_double, cujo objectivo é fornecer um conjunto de ferramentas para lidar com arrays de double.

Note que optámos por não incluir comentários de documentação Doxygen em nenhum dos módulos deste programa.

Começamos por incluir o próprio ficheiro de interface. Isso ajuda-nos a garantir a coerência entre os dois ficheiros, pois desta forma o compilador poderá gerar erros quando detectar incoerências.

Inclusão de ficheiros de interface

Incluímos os vários ficheiro de interface necessários:

• stdlib.h – Para podermos usar o valor especial NULL dos ponteiros e para podemos usar as rotinas malloc() e realloc() e o procedimento qsort().

• stdio.h – Para podermos usar as rotinas fopen(), fclose() e fscanf().

• math.h – Para podermos usar a função sqrt() e as macros NAN e INFINITY.

• assert.h – Para podermos usar a macro assert().

Definições de rotinas

Note como classificamos length como const. Esta prática ajuda o compilador a detectar os nossos próprios erros. Ao afirmarmos explicitamente que não tencionamos alterar um parâmetro, permitimos que o compilador detecte alterações realizadas por engano. Seguimos esta prática em todo o código deste projecto.

Começamos por abrir um novo canal de leitura para o ficheiro cujo nome recebemos como argumento.

Em C, o código que lida com casos de erro e casos excepcionais emaranha-se com o código «normal». Isso torna todo o código menos legível. Para evitar este problema a melhor solução é mesmo mudar de linguagem. :-)

O array onde iremos guardando os itens lidos tem de ir crescendo à medida que a leitura prossegue. Em cada instante, o array terá como capacidade o valor guardado nesta variável. O número de itens já lidos e guardados no array será sempre inferior ou igual à sua capacidade.

Criamos o array com a capacidade definida inicialmente.

No caso de não se conseguir criar o novo array dinâmico, fechamos o canal aberto para o ficheiro em leitura e retornamos devolvendo o valor especial NULL, de modo a assinalar o erro.

O ciclo de leitura é feito recorrendo a duas variáveis locais. A primeira, i, indica em cada momento, e simultaneamente, quantos itens já foram lidos e o índice do item do array onde será guardado o próximo valor lido do ficheiro. A segunda variável é usada para ler cada um dos itens. Em caso de sucesso na leitura, o valor contido neste variável será atribuído ao item apropriado do array.

A guarda do ciclo inclui a própria operação de leitura. Esta forma de escrever o ciclo é idiomática do C e seria considerada uma má prática em qualquer outra linguagem. Fazemos a leitura usando a usual rotina fscanf(), recorrendo à especificação de conversão %lg, onde a utilização de l é necessária por se tratar de doubles. A leitura é realizada para a variável item, pelo que passamos o seu endereço à rotina fscanf(). Se a leitura tiver sucesso, a rotina devolve o valor 1, pois terá sido atribuído exactamente um valor, nomeadamente o valor lido do ficheiro e guardado na variável item.

Se o número de itens lidos com sucesso e guardados no array for igual à capacidade do array, então esta encontra-se esgotada. Sendo necessário aumentar a capacidade do array, pode-se demonstrar que uma forma eficiente de o fazer é duplicá-la, pois leva a uma número médio de cópias por item do array que é constante e pequeno. Note que o valor da variável capacidade é aumentado na mesma instrução em que se aumenta a capacidade do array, pelo que essa instrução terá dois efeitos distintos. Mais uma vez, trata-se de código muito discutível, mas idiomático na linguagem C.

Atribuímos o valor lido ao item do array com índice i e incrementamos o próprio i! O valor de i usado na indexação é o valor original de i, antes da incrementação. Trata-se, outra vez, de código muito discutível, mas idiomático na linguagem C.

Finda a leitura, a variável i contém o número de itens lidos e guardados no array. Guardamos o seu valor na variável apontada por length.

Se necessário, ajustamos a capacidade do array de modo a corresponder exactamente ao número de itens lidos, de modo a garantir que não há desperdício de memória.

Fechamos o canal de entrada.

Retornamos, devolvendo o endereço do primeiro item do array dinâmico criado, que contém os valores lidos do ficheiro.

Note a utilização de um ciclo com apenas um local de terminação.

Esta função é usada durante a ordenação de arrays de double realizada através do procedimento qsort() da biblioteca padrão do C. A utilização de ponteiros para void como tipo dos seus parâmetros é um requisito do procedimento qsort(), que, desta forma, é capaz de ordenar arrays de itens de qualquer tipo. O procedimento qsort() requer que esta função devolva um valor inteiro que indica a relação de ordem entre o primeiro e o segundo argumento. Se o primeiro for superior ao segundo, o valor int devolvido deverá ser positivo. Se for igual, o valor devolvido deverá ser nulo. Se for menor, deverá devolver um valor negativo. Sendo esta função de utilidade restrita, optámos por lhe dar ligação local, usando para isso o qualificador static.

Os argumentos são ponteiros para os itens a comparar. Sendo o procedimento qsort() genérico, os parâmetros correspondentes são do tipo void *. Para aceder aos valores do tipo double, fazem-se coerções para o tipo ponteiro para double.

Uma função auxiliar devolvendo o quadrado do valor recebido como argumento.

Esta implementação é simples, mas ineficaz. Ver mais abaixo uma implementação do cálculo do desvio padrão que não exige percorrer o array duas vezes.

Usamos uma forma de cálculo muito ineficaz: ordenar o array de modo a obter a mediana através do ou dos valores centrais. Há formas bem mais eficazes de calcular a mediana. Nomeadamente, pode-se usar uma versão modificada do algoritmo de ordenação rápida que não se preocupa em ordenar o array, mas apenas em realizar particionamentos sucessivos até determinar o valor do ou dos itens centrais do array, que não precisa por isso de ser totalmente ordenado.

Primeiro lidamos com o caso especial da mediana de zero itens.

Criamos um array de trabalho que é uma cópia do array original, pois este não deve ser alterado.

Usamos o procedimento de ordenação genérico do C qsort(), que utiliza o algoritmo de ordenação rápida, para ordenar o array de trabalho.

Se o array tiver um número par de itens, a sua mediana é a média aritmética dos valores dos dois itens mais próximos do meio do array ordenado. Se tiver um número ímpar de itens, então a mediana é o valor do item central do array ordenado.

Note que esta função está definida mesmo para zero itens, devolvendo infinito (+∞) nesse caso, pois o infinito é o elemento neutro da operação de obtenção do menor de dois operandos, da mesma forma que o zero (0) é o elemento neutro da operação de obtenção da soma de dois operandos.

Note que esta função está definida mesmo para zero itens, devolvendo infinito negativo (-∞) nesse caso, pois o infinito negativo é o elemento neutro da operação de obtenção do maior de dois operandos, da mesma forma que o zero (0) é o elemento neutro da operação de obtenção da soma de dois operandos.

Esta variável guarda os valores das estatísticas e será devolvida quando a função retornar. Note a forma de inicialização dos campos da estrutura.

Lidamos primeiro com o caso especial em que há zero itens apenas. O valor inicial da variável statistics foi escolhido de modo a cobrir este caso.

Uma vez que se calculam as várias estatísticas numa única função, podemos fazer algumas optimizações. Ainda assim, seria possível melhorar francamente a forma de cálculo da mediana, como referido anteriormente.