Olá, desta vez escrevo aqui sobre um tema um pouco diferente, Programação.

Ontem, a propósito de um exercício para um amigo meu, aproveitei para fazer umas experiências em C, dado que há algum tempo que não programo nesta linguagem.

O problema é o seguinte:

Desenvolver uma aplicação que dado um número n, devolva um conjunto de cardinalidade n (#n) em que os elementos são números de 1 até n, sem repetição.

Exemplo:

input> 10

output> 2 9 10 3 8 1 6 7 5 4

Existe várias abordagens para este problema, umas mais complexas e, mais eficientes. Outras mais simples e menos eficientes e, até outras, em que o custo de eficiencia é justificável.

Para o desenvolvimento em C, optei por duas vertentes. Usar um algoritmo “lento”, mas simples de entender e, um algoritmo mais “complexo”, mas bem mais rápido a fazer o processo.

Começaremos pelo primeiro:

Abordagem Simples - Ciclos + Comparações

Ideia:

  • Supondo um número n

  • Gera-se um array C

  • _Para cada posição de n: _

    • Gerar número aleatório a

    • Verificar se o número existe em C

    • Existe? Repete o passo;

    • Senão? Adiciona o valor a a C

A implementação deste algoritmo em C é extremamente simples:

#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main(int argc, char **argv)
{
	int i;
	int n = 0;
	int j;
	int a;
	int numbersLength = 0;
	int *numbers;
	short int repete;

	/* Converte o numero introduzido em string num numero inteiro */
	n = (int) strtol(argv[1], NULL,10);

	/* Aloca o espaco para os n numeros que vao ser posicionados */
	numbers = (int *) calloc(n,sizeof(int))
		srand(time(NULL));


	for (i=0;i<n;i++)
	{
		repete = 0;
		a = rand()%n+1;
		/* Verifica a existencia de uma repeticao */
		for (j=0; j < numbersLength; j++)
		{
			if (a == numbers[j])
			{
				repete = 1;
				break;
			}
		}
		if (repete == 0){
		       	numbers[i] = a;
			numbersLength++;
		}
		else { 
			i--;
		}
	}
	return 0;
}

Compilado com: gcc -Wall -pedantic -ansi -o output input.c

Ora bem, mas depois de ver esta abordagem. Decidi que seria interessante pegar numa nova… mais complexa, mas mais rápida.

Abordagem Complexa - Listas

Ideia:

  • Gerar uma lista com n elementos, cada um correspondente a um número x no intervalo [0,n] inteiros

  • Gerar um array C **com **n elementos que, vão suportar a nova ordenação

  • Para cada posição de C gerar um número aleatório a **no **intervalo [0,n]

    • Obter o valor correspondente ao nodo a na lista e colocar na posição em C

    • Eliminar o nodo correspondente a a **e diminuir o **valor de n em um

A implementação, é agora, um pouco mais complexa, dado que estamos a trabalhar com listas… ainda assim torna-se simples de entender:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

typedef struct node{
	int value;
	struct node *next_node;
} Node;

struct node * putNode(struct node *curnode,int value)
{
	struct node *newnode;

	newnode = (struct node *) calloc(1,sizeof(struct node));

	newnode->value = value;
	curnode->next_node = newnode;

	return newnode;
}
void deleteNode(struct node *topnode,int value)
{
	struct node *curnode = topnode,*nextnode;
	int deleted = 0;
	if (curnode == NULL) return;
	if (curnode->next_node == NULL && curnode->value == value) {
		curnode = NULL;
		return;
	}
	while(deleted != 1 || curnode != NULL)
	{
		nextnode = curnode->next_node;
		if (nextnode == NULL) return;
		if (nextnode->value == value)
		{
			curnode->next_node = nextnode->next_node;
			free(nextnode);
			deleted = 1;
		}
		curnode = curnode->next_node;
	}
}
struct node * getNode(struct node *topnode,int pos)
{
	struct node *curnode = topnode;
	int j;
	for (j=0;j<pos;j++)
	{
		if (curnode->next_node != NULL)
			curnode = curnode->next_node;
		else
			curnode = topnode;
	}

	return curnode;
}

int main(int argc, char **argv)
{

	int n;
	int i;
	int *numbers;
	int a,total;

	struct node *topnode,*curnode;

	n = (int) strtol(argv[1],NULL,10);
	numbers = (int *) calloc(n,sizeof(int));

	topnode = (struct node *) calloc(1,sizeof(struct node));
	topnode->value = 1;
	curnode = topnode;

	for (i = 2; i <= n; i++)
	{
		curnode = putNode(curnode,i);
	}

	curnode = topnode;

	srand(time(NULL));

	total = n;

	for (i=0;i<n;i++)
	{
		a = rand()%total;
		total--;
		curnode = getNode(topnode,a);
		numbers[i] = curnode->value;
		deleteNode(topnode,curnode->value);
	}

	return 0;
}

Apesar desta última também não ser a melhor abordagem. Dado que para o arranque do programa é necessário alocar memória para o dobro de números que se querem introduzir. É possível melhorar através de várias técnicas que proponho:

  • Usar as propriedades das listas para “marcar” um caminho aleatório, de modo a que seja possível seguir o caminho aleatório na lista e ter-se-á os números

  • Criar uma segunda lista que irá crescendo à medida que a primeira decresce

  • Experimentar também noutras linguagens

Para todo o caso, a diferença é notável, principalmente quando se aumenta n para valores grandes, exemplo:

Para 1000 números: omega% time ./randomSet_Simple 1000 ./randomSet_Simple 1000  0.02s **user 0.00s system 95% cpu 0.024 total omega% time ./randomSet_Stack 1000 ./randomSet_Stack 1000  0.01s** user 0.00s system 100% cpu 0.007 total Para 10000 números: omega% time ./randomSet_Simple 10000 ./randomSet_Simple 10000  3.97s user 0.00s system 99% cpu 3.974 total omega% time ./randomSet_Stack 10000 ./randomSet_Stack 10000  0.67s user 0.00s system 99% cpu 0.670 total Para 30000 números: omega% time ./randomSet_Simple 30000 ./randomSet_Simple 30000  30.62s user 0.00s system 99% cpu 30.647 total omega% time ./randomSet_Stack 30000 ./randomSet_Stack 30000  6.04s user 0.00s system 99% cpu 6.043 total

É interessante ver estes números e de facto, tenho curisosidade para compreender mais métodos de interpretar esta simples ideia.

Ano 2019, em revisão...

Com o fim do ano vêm **momentos de reflexão e balanço** do que foi o ano que passou. Escrevia o ano passado, no primeiro dia de janeiro:>...… Continue reading

A luz

Published on December 17, 2018

Eram uns dias de sol...

Published on November 16, 2018