Gerar Conjuntos de Números Aleatórios

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 eficiência é 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 #include #include #include 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 #include #include #include

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.