C Gráfico para comparação de algoritmos

MatheusCarvalho · 8 de setembro de 2021

Preciso fazer um relatório que faça uma comparação dos gráficos gerados contando o número de atribuições nos vetores pelo tamanho dos vetores.

Tenho que comparar os métodos bubble sort, insert sort e selection sort, para o intervalo de tamanho de vetores de 100 a 10.000 posições variando de 500 em 500 posições, usando : vetor ordenado, vetor desordenado e vetor inversamente ordenado.

Como posso fazer isso ?

O gráfico tem que ser assim :

arfneto · 8 de setembro de 2021

São 200 trocas, em 3 cenários.

É só uma planilha. Precisa mostrar um gráfico também? Ou pode ser só a tabela?

Faça o simples antes: gere as tabelas. Ou o mais simples ainda: gera uma só, para o vetor ordenado. E depois incremente.

Se precisa do grafico pode usar o Google Planilhas e ver o gráfico lá a partir da sua tabela. E aí simplesmente copie o visual.

Pode ser um bitmap 800x600 por exemplo. a altura é o total de trocas e pode ser proporcional ao tamanho do vetor, ou linear mas que não vai dizer muito. A largura é o tamanho e pode usar 200 pontos, que é o que tem.

Estou escrevendo sem pensar muito, confesso. Mas acho que é isso.

V!OLADOR · 9 de setembro de 2021

10 horas atrás, JacklaneNick disse:

Como posso fazer isso ?

Apesar que, aparentemente, a pergunta foi sobre como fazer gráficos, apenas por descargo de consciência, pergunta: você já tem todos os códigos necessários pra fazer os benchmarks? Ou seja, a dúvida é realmente apenas sobre como plotar um gráfico? Assumindo que a resposta seja "não tenho e a dúvida é como coletar os dados", e pra poupar tempo, algumas dicas:

1) Escreva os três algoritmos (buble, insert e selection) caso uma implementação especifica não tenha sido fornecida. Estes serão os kernels do teste.

2) Implemente um programa driver (com uma função main) pra cada kernel. Esse programa vai ser responsável por um loop principal incrementando o tamanho do vetor de teste, de 500 em 500.

3) Pra cada passo do loop, crie um vetor e preencha os elementos. No caso especifico do vetor desordenado você pode utilizar números aleatórios produzidos com as funções srand() e rand() da biblioteca stdlib.h.

4) Com o vetor devidamente preenchido, chame o kernel do teste.

5) Quando o teste terminar, escreva num arquivo de texto o tamanho do vetor e a quantidade que você tá monitorando (no caso, número de atribuições). Tipo, um par x, y.

6) Destrua o vetor e siga pro próximo passo do loop, em (3).

7) Quando terminar todo o teste, em todos os tamanhos, execute o driver mais algumas vezes (três, por exemplo). Os resultados podem ter mais significado estatístico coletando dados de três ou mais execuções. E o resultado final pode ser uma média de todas as execuções. Possivelmente, apenas relevante pro caso desordenado.

Basta repetir todo o processo pra cada tipo de ordenação. Dica: evite fazer todos os testes no mesmo driver pra que um bug qualquer e inesperado de um teste não contamine o próximo. Três testes? três programas independentes.

Pronto, dados coletados? basta fazer uns gráficos legais daqueles que a gente aprende no jardim de infância .

arfneto · 9 de setembro de 2021

Dias atrás eu postei um programa nesse tópico https://www.clubedohardware.com.br/forums/topic/1561085-funções-e-matrizes-isbn/?tab=comments#comment-8259805

Abaixo desse título
Então esse programa faz exatamente a mesma coisa: tem 3 funções para calcular no caso um dígito verificador, e para cada função mede o tempo que passou para rodar OS MESMOS DADOS com AS 3 FUNÇÕES. É a mesma coisa que quer fazer. E tem a entrada, a saída da execução e o código completo. Sugiro dar uma olhada lá.

A lógica:

A tabela para alimentar o gráfico

Aqui a tabela tem um texto pra sair no relatório, a função e o tempo. No seu caso talvez precise apenas do óbvio: a função e o número de trocas.

typedef struct
{
    const char* descricao;
    char      (*Funcao)(char[9]);
    clock_t     tempo;

}   Tabela;

Note que como vai usar sort o mais simples é usar uma função para cada algoritmo, mas claro só uma função de comparação. Sem surpresas porque não existe sort sem comparar, certo?

Exemplo: O protótipo de qsort de stdlib

Veja o protótipo de qsort() por exemplo, disponível em C :

    void qsort(
	void *base,   // o vetor
	size_t nitems,    // o tamanho
	size_t size,      // a funcao de comparacao
	int (*compar)(const void *, const void*)
    )

Toda rotina de sort usa isso desde os 80, em C, Pascal, C++, java ou qualquer outra. Eu já postei aqui funções de sort que usam isso, acho que no ano passado. Mas é trivial. Onde tem a comparação chama a função. Ela retorna 1 se o par está fora de ordem e aí o sort faz a troca.

Porque estou dizendo isso? Porque a comparação é que determina a troca e você pode contar aí as trocas, em um único lugar no programa todo mesmo que use 15 algoritmos de sort...

Não vou repetir tudo que escrevi lá, mas veja as funções e a criação da tabela:

char isbn_dv(char[9]);            // a funcao
char isbn_dv_oficial(char[9]);    // com os pesos oficiais
char isbn_dv_professor(char[9]);  // como seu professor gosta
char isbn_dv_mdr(char[9]);        // midori verison as posted

clock_t testa_funcao(unsigned, char (*)(char[9]));

typedef struct
{
    const char* descricao;
    char      (*Funcao)(char[9]);
    clock_t     tempo;

} Tabela;

int main(void)
{
    Tabela grade[4] = {
        [0].descricao = "oficial",
        [0].Funcao    = isbn_dv_oficial,
        [0].tempo     = 0,
        [1].descricao = "pesos 1..9",
        [1].Funcao    = isbn_dv,
        [1].tempo     = 0,
        [2].descricao = "aprovada pelo professor :)",
        [2].Funcao    = isbn_dv_professor,
        [2].tempo     = 0,
        [3].descricao = "@Midori",
        [3].Funcao    = isbn_dv_mdr,
        [3].tempo     = 0,
    };

É tudo o que precisa exceto chamar as funções e claro que isso está lá:

    printf(" ok!\nRodando as outras versões. versão oficial = 1.0X\n");
    for (int i = 1; i < 4; i += 1)
    {   srand(210904);
        grade[i].tempo = testa_funcao(N, grade[i].Funcao);
    }

No caso a saída é algo assim

    [Comparando as 4 funcoes]
    2000 (*1.000) testes com valores aleatorios, mesma serie

Rodando a versão oficial...  ok!
Rodando as outras versões. versão oficial = 1.0X
0.87X para versão pesos 1..9
1.09X para versão aprovada pelo professor :)
3.46X para versão @Midori

Isso não era um exercício. Eu queria mostrar o tempo das outras funções considerando a versão oficial como 1X.

Essa é a maneira comum de escrever isso. Um programa chama as funções e preenche a tabela.

O gráfico não tem nada a ver com isso e pode ser gerado ao final por outra função que recebe um ponteiro para a tabela e o nome do arquivo de saída. Ou mostra na tela.

MatheusCarvalho · 9 de setembro de 2021

10 horas atrás, V!OLADOR disse:

você já tem todos os códigos necessários pra fazer os benchmarks?

Não . Procurei mas não achei nenhum que tivesse esses algoritmos mais a função parar ver o tempo e quantas trocas foram feitas

1 hora atrás, arfneto disse:

No seu caso talvez precise apenas do óbvio: a função e o número de trocas.

Sim, mas não sei como construir essas funções

arfneto · 9 de setembro de 2021

59 minutos atrás, JacklaneNick disse:

Não . Procurei mas não achei nenhum que tivesse esses algoritmos mais a função parar ver o tempo e quantas trocas foram feitas

Sim, mas não sei como construir essas funções

Como assim? o sort?

tanto faz. Use a mesma função e faça o programa. Não perca tempo.

Não tem um livro? Seu curso não adota um livro?

E para esses algoritmos mais simples de sort tem em todo lugar exemplos em várias linguagens. Eu mesmo postei aqui uma versão completa de bubble_sort() com uma animação colorida por exemplo. Pode pesquisar no forum.

Por exemplo esse site aí ao lado em https://www.geeksforgeeks.org/bubble-sort/ tem todos esses em 7 linguagens. Todo mundo sabe isso então seu professor também.

E o resto é exatamente o programa que te mostrei e o gráfico...

Agora se te foi passado esse programa quer dizer que você já escreveu vários programas em C, certo?

Aqueles das listas de livros, dos carros, do maximo do vetor, os inevitáveis dos números primos... Ou não?

V!OLADOR · 9 de setembro de 2021

1 hora atrás, JacklaneNick disse:

Não

Eu imaginei.

1 hora atrás, JacklaneNick disse:

Procurei mas não achei nenhum que tivesse esses algoritmos mais a função parar ver o tempo e quantas trocas foram feitas

Creio que escrever as funções pessoalmente deva fazer parte do objetivo do exercício. Então, antes de falar de gráficos e benchmarks sua primeira tarefa é implementar os três algoritmos e testá-los. Felizmente, eles são bem simples e há uma zilhão de informações na internet. Aqui mesmo no fórum você vai encontrar inúmeros tópicos a respeito porque a gente gosta de reinventar a roda todo dia. Se você nunca usou um algoritmo desses, recomendo muito escrevê-lo pessoalmente. Não custa nada e é muito importante pro seu próprio aprendizado. Além do mais você vai ter propriedade na hora de interpretar os resultados do benchmark.

MatheusCarvalho · 9 de setembro de 2021

31 minutos atrás, V!OLADOR disse:

Creio que escrever as funções pessoalmente deva fazer parte do objetivo do exercício. Então, antes de falar de gráficos e benchmarks sua primeira tarefa é implementar os três algoritmos e testá-los. Felizmente, eles são bem simples e há uma zilhão de informações na internet. Aqui mesmo no fórum você vai encontrar inúmeros tópicos a respeito porque a gente gosta de reinventar a roda todo dia. Se você nunca usou um algoritmo desses, recomendo muito escrevê-lo pessoalmente. Não custa nada e é muito importante pro seu próprio aprendizado. Além do mais você vai ter propriedade na hora de interpretar os resultados do benchmark.

Eu consegui achar uma função que mede o tempo mas nenhum que retorne quantas trocas foram feitas e não sei fazer isso

44 minutos atrás, arfneto disse:

E para esses algoritmos mais simples de sort tem em todo lugar exemplos em várias linguagens. Eu mesmo postei aqui uma versão completa de bubble_sort() com uma animação colorida por exemplo. Pode pesquisar no forum.

Por exemplo esse site aí ao lado em https://www.geeksforgeeks.org/bubble-sort/ tem todos esses em 7 linguagens. Todo mundo sabe isso então seu professor também.

E o resto é exatamente o programa que te mostrei e o gráfico...

Agora se te foi passado esse programa quer dizer que você já escreveu vários programas em C, certo?

Aqueles das listas de livros, dos carros, do maximo do vetor, os inevitáveis dos números primos... Ou não?

Vou dar uma olhada

V!OLADOR · 9 de setembro de 2021

15 minutos atrás, JacklaneNick disse:

Eu consegui achar uma função que mede o tempo mas nenhum que retorne quantas trocas foram feitas e não sei fazer isso

Ué, você conseguiu uma versão que faz uma medida mais difícil (tempo) e não consegue adaptar pro caso mais simples? Fica uma impressão de que copiou e colou um código de algum lugar mas não o entende.

Ao entrar na função, declara um contador devidamente zerado:

uint32_t counter = 0;

Identifica onde a troca é feita e ali, imediatamente após, atualiza o contador:

++counter;

Quando a função terminar, retorna o contador pro driver do benchmark:

return counter;

Isso vai requerer adaptar a interface da função também, caso ela tenha sido escrita por outra pessoa. Não pergunte onde a troca ocorre, você deve ser capaz de identificar isso sozinha, faz parte do exercício.

MatheusCarvalho · 9 de setembro de 2021

1 minuto atrás, V!OLADOR disse:
Quando entrar na função declara um contador devidamente zerado:
uint32_t counter = 0;
Identifica onde a troca é feita e ali, imediatamente após, atualiza o contador:
++counter;
Quando a função terminar, retorna o contador pro driver do benchmark:
return counter;
Isso vai requerer adaptar a interface da função também, caso ela tenha sido escrita por outra pessoa. Não pergunte onde a troca ocorre, você deve ser capaz de identificar isso sozinha, faz parte do exercício.

Eu fiz isso e retornou um numero muito grande sendo que só eram 5 numeros

V!OLADOR · 9 de setembro de 2021

3 minutos atrás, JacklaneNick disse:

Eu fiz isso e retornou um numero muito grande sendo que só eram 5 numeros

Cheirinho de um contador ou não inicializado com zero no inicio da função ou sendo manipulado em mais de um lugar além da função em si. Faça um contador local que apenas exista dentro da função e seja sempre inicializado com zero.

Se ainda assim o erro persistir, certifique-se de que tá atualizando o contador no local correto dentro da função. Isso exige que você entenda o algoritmo.

MatheusCarvalho · 9 de setembro de 2021

// C program for implementation of Bubble sort
#include <stdio.h>

void swap(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

// A function to implement bubble sort
int bubbleSort(int arr[], int n)
{
int i, j;
int counter = 0;
for (i = 0; i < n-1; i++)	

	// Last i elements are already in place
	for (j = 0; j < n-i-1; j++)
		if (arr[j] > arr[j+1])
			swap(&arr[j], &arr[j+1]);
		counter++;
		return counter;
}

/* Function to print an array */
void printArray(int arr[], int size)
{
	int i;
	for (i=0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

// Driver program to test above functions
int main()
{
	int arr[] = {64, 34, 25, 12, 22, 11, 90};
	int n = sizeof(arr)/sizeof(arr[0]);
	int counter;
	bubbleSort(arr, n);
	printf ("Numero de trocas feitas %d\n" ,counter);
	printf("Sorted array: \n");
	printArray(arr, n);
	return 0;
}

@V!OLADORFiz exatamente o que você falou e o resultado foi esse. Onde está o erro ?

V!OLADOR · 9 de setembro de 2021

20 minutos atrás, JacklaneNick disse:

for (i = 0; i < n-1; i++)	

	// Last i elements are already in place
	for (j = 0; j < n-i-1; j++)
		if (arr[j] > arr[j+1])
			swap(&arr[j], &arr[j+1]);
		counter++;
		return counter;
}

Bom, veja que o contador não tá sendo atualizado dentro do bloco do if, como você gostaria. Então, o primeiro a fazer é usar { e } pra especificar um escopo no qual você faz a troca e atualiza o contador:

if (arr[j] > arr[j+1])
{
	swap(&arr[j], &arr[j+1]);
	counter++;
}

Segundo, ao retornar pra função main(), você tá imprimindo um contador não inicializado e, pior, que não recebeu uma copia do resultado guardado pelo contador interno da função bubleSort(). Então, na main() certifique-se de que

int counter = bubbleSort(arr, n);

MatheusCarvalho · 9 de setembro de 2021

13 minutos atrás, V!OLADOR disse:
Bom, veja que o contador não tá sendo atualizado dentro do bloco do if, como você gostaria. Então, o primeiro a fazer é usar { e } pra especificar um escopo no qual você faz a troca e atualiza o contador:
if (arr[j] > arr[j+1])
{
	swap(&arr[j], &arr[j+1]);
	counter++;
}
Segundo, ao retornar pra função main(), você tá imprimindo um contador não inicializado e, pior, que não recebeu o resultado do contador interno da função bubleSort(). Então, na main() certifique-se de que
counter = bubbleSort(arr, n);

Fiz isso e agora ele está retornando que foram 14 trocas, pelo vistou deu certo !

V!OLADOR · 9 de setembro de 2021

9 minutos atrás, JacklaneNick disse:

Fiz isso e agora ele só retorna 0

Certeza que fez? aposto que deixou escapar algo daquilo que eu disse.

MatheusCarvalho · 9 de setembro de 2021

agora, V!OLADOR disse:

Certeza que fez? aposto que deixou escapar algo do que eu disse.

Eu tinha dito isso antes... Depois voltei pra editar . Eu tinha colocado o "return counter; " dentro do if , me passei !

arfneto · 9 de setembro de 2021

45 minutos atrás, JacklaneNick disse:

Eu consegui achar uma função que mede o tempo mas nenhum que retorne quantas trocas foram feitas e não sei fazer isso

Não precisaria procurar muito já que o programa que eu te mostrei faz isso, em C, para 3 funções para 2 milhões de execuções. Falta só o loop aumentando de 500 em 500, as tais 200X que eu te expliquei no início.

E marcar o tempo não é assim um algoritmo: apenas uma conta: fim - inicio.

E eu te mostrei uma struct que é só preencher...

Quanto às comparações, apesar de eu já ter explicado onde vai contar a troca (quanto a comparação mostrar que está fora de ordem, claro, vou usar um amarelo num código:

pois é, onde compara. Onde troca se está fora de ordem. Ondem está chamando essa swap()....

Bem como copiou

V!OLADOR · 9 de setembro de 2021

1 minuto atrás, JacklaneNick disse:

Eu tinha dito isso antes... Depois voltei pra editar . Eu tinha colocado o "return counter; " dentro do if , me passei !

Alguém muito sábio disse certa vez: "o compilador tem sempre razão".

MatheusCarvalho · 9 de setembro de 2021

@V!OLADOR Só uma dúvida em relação ao gráfico, se é pra mostrar os vetores desordenados então eles não farão troca né ?

arfneto · 9 de setembro de 2021

15 minutos atrás, JacklaneNick disse:

@V!OLADOR Só uma dúvida em relação ao gráfico, se é pra mostrar os vetores desordenados então eles não farão troca né ?

Claro que farão trocas. Só não vão trocar se já estiver em ordem, essa é a razão de trocar.

MatheusCarvalho · 9 de setembro de 2021

1 minuto atrás, arfneto disse:

Claro que farão trocas. Só não vão trocar se já estiver em ordem, essa é a razão de trocar.

É porque está pedindo vetores ordenados que pelo o que eu entendo é pra mostrar em ordem crescente , vetores inversamente ordenados que é em ordem decrescente mas então o que seriam esses vetores desordenados ?

arfneto · 9 de setembro de 2021

29 minutos atrás, JacklaneNick disse:

É porque está pedindo vetores ordenados que pelo o que eu entendo é pra mostrar em ordem crescente , vetores inversamente ordenados que é em ordem decrescente mas então o que seriam esses vetores desordenados ?

Bem....

vetores ordenados são assim ordenados. Vetores inversamente ordenados são assim, inversamente ordenados. Todos os outros são assim, desordenados. Não sei o que dizer...

	int ordenado[] =              { 1,2,3 };
	int inversamente_ordenado[] = { 3,2,1 };

O que você precisa é só preencher uma tabela.

O caso é que se estiver ordenado o algoritmo não deve trocar nada, ao menos esses que estão na lista.

O pior caso é quanto estiver tudo ao contrário, certo? Nesse caso se imagina que vai fazer o maior número de trocas. E para poder comparar nos outros casos precisa repetir a série, como está no exemplo que te citei e expliquei.

É o que se espera que seu gráfico mostre, além dos tempos de execução. Isso estou imaginando, porque não está em sua descrição do problema eu acho...

MatheusCarvalho · 9 de setembro de 2021

22 minutos atrás, arfneto disse:

O caso é que se estiver ordenado o algoritmo não deve trocar nada,

Então... Eu tenho que fazer um gráfico que compare a troca de algoritmos ordenados sendo que eles não fazem trocas ? Meu professor deve está doido então

23 minutos atrás, arfneto disse:

O pior caso é quanto estiver tudo ao contrário, certo? Nesse caso se imagina que vai fazer o maior número de trocas. E para poder comparar nos outros casos precisa repetir a série, como está no exemplo que te citei e expliquei.

É o que se espera que seu gráfico mostre, além dos tempos de execução. Isso estou imaginando, porque não está em sua descrição do problema eu acho...

Só tenho que mostrar o tamanho do vetor e quantas trocas ele fez, estou fazendo os testes com os vetores desordenados por enquanto

arfneto · 9 de setembro de 2021

1 minuto atrás, JacklaneNick disse:

Então... Eu tenho que fazer um gráfico que compare a troca de algoritmos ordenados sendo que eles não fazem trocas ? Meu professor deve está doido então

Muitas vezes se faz isso pela razão simples: testar para o melhor caso. E se o algoritmo apresentar umas trocas? Você não ia gostar de saber?

2 minutos atrás, JacklaneNick disse:

Só tenho que mostrar o tamanho do vetor e quantas trocas ele fez, estou fazendo os testes com os vetores desordenados por enquanto

Não faz diferença. É só um vetor com os números. Mas claro que em geral o primeiro teste que se faz é com o vetor ordenado e o segundo com o vetor invertido. E com 2 ou 3 números.

MatheusCarvalho · 9 de setembro de 2021

1 minuto atrás, arfneto disse:

Muitas vezes se faz isso pela razão simples: testar para o melhor caso. E se o algoritmo apresentar umas trocas? Você não ia gostar de saber?

Pelo menos o bubble sort que é o que eu estou fazendo no momento não apresenta trocas com vetores ordenados