overdestiny.com's labs

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#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.