Skip to content

Instantly share code, notes, and snippets.

@eduardoklosowski
Last active October 26, 2022 03:01
Show Gist options
  • Save eduardoklosowski/e7656d38bb93927734a147ca1ca3e250 to your computer and use it in GitHub Desktop.
Save eduardoklosowski/e7656d38bb93927734a147ca1ca3e250 to your computer and use it in GitHub Desktop.
Análise de desempenho de um código iterativo e recursivo para percorrer uma árvore binária
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
codigo tempo memoria
iterativo 1.03 32644
recursivo 0.99 32744
iterativo 0.98 32724
recursivo 0.99 32660
iterativo 0.97 32752
recursivo 0.97 32696
iterativo 0.96 32652
recursivo 0.96 32640
iterativo 0.98 32640
recursivo 0.98 32744
iterativo 0.97 32656
recursivo 0.97 32640
iterativo 0.97 32644
recursivo 0.97 32744
iterativo 0.98 32712
recursivo 0.97 32656
iterativo 0.99 32640
recursivo 0.99 32640
iterativo 0.99 32696
recursivo 0.96 32752
iterativo 0.97 32696
recursivo 0.97 32652
iterativo 0.96 32640
recursivo 0.96 32716
iterativo 0.96 32732
recursivo 0.97 32712
iterativo 0.97 32752
recursivo 0.97 32688
iterativo 0.96 32656
recursivo 0.96 32712
iterativo 0.97 32640
recursivo 0.95 32652
iterativo 0.97 32728
recursivo 0.95 32632
iterativo 0.97 32716
recursivo 0.97 32744
iterativo 0.98 32744
recursivo 0.97 32652
iterativo 0.97 32716
recursivo 0.97 32656
iterativo 0.99 32712
recursivo 0.99 32752
iterativo 0.99 32640
recursivo 0.99 32640
iterativo 1.00 32716
recursivo 1.00 32644
iterativo 0.99 32652
recursivo 0.98 32640
iterativo 0.98 32656
recursivo 0.97 32636
iterativo 0.98 32712
recursivo 0.98 32648
iterativo 0.97 32696
recursivo 0.98 32640
iterativo 0.99 32688
recursivo 0.97 32652
iterativo 0.99 32716
recursivo 0.99 32644
iterativo 0.98 32744
recursivo 0.97 32672
iterativo 0.97 32736
recursivo 0.96 32644
iterativo 0.98 32752
recursivo 0.98 32716
iterativo 0.98 32744
recursivo 0.98 32652
iterativo 0.99 32728
recursivo 0.98 32712
iterativo 0.97 32728
recursivo 0.97 32656
iterativo 0.97 32716
recursivo 0.96 32640
iterativo 0.97 32640
recursivo 0.97 32712
iterativo 0.97 32640
recursivo 0.96 32712
iterativo 0.97 32640
recursivo 0.96 32716
iterativo 0.96 32652
recursivo 0.96 32640
iterativo 0.96 32724
recursivo 0.96 32716
iterativo 0.97 32640
recursivo 0.96 32712
iterativo 0.98 32744
recursivo 0.98 32716
iterativo 0.98 32728
recursivo 0.98 32644
iterativo 0.99 32640
recursivo 0.99 32640
iterativo 0.99 32712
recursivo 0.97 32636
iterativo 0.97 32744
recursivo 0.98 32652
iterativo 0.97 32752
recursivo 0.97 32720
iterativo 0.98 32752
recursivo 0.98 32724
iterativo 0.98 32644
recursivo 0.98 32712
iterativo 0.98 32644
recursivo 0.97 32752
iterativo 0.98 32724
recursivo 0.97 32656
iterativo 0.98 32748
recursivo 0.97 32712
iterativo 0.98 32704
recursivo 0.98 32640
iterativo 0.98 32752
recursivo 0.98 32752
iterativo 0.98 32752
recursivo 0.96 32688
iterativo 0.97 32632
recursivo 0.96 32724
iterativo 0.96 32728
recursivo 0.96 32756
iterativo 0.97 32632
recursivo 0.96 32684
iterativo 0.97 32640
recursivo 0.96 32716
iterativo 0.96 32728
recursivo 0.96 32688
iterativo 0.96 32752
recursivo 0.96 32756
iterativo 0.96 32652
recursivo 0.96 32688
iterativo 0.96 32644
recursivo 0.97 32752
iterativo 0.99 32744
recursivo 0.99 32652
iterativo 1.03 32632
recursivo 0.98 32688
iterativo 0.99 32728
recursivo 0.98 32640
iterativo 1.00 32752
recursivo 0.98 32712
iterativo 0.98 32640
recursivo 0.97 32744
iterativo 0.99 32656
recursivo 0.99 32632
iterativo 0.99 32640
recursivo 0.97 32728
iterativo 0.97 32712
recursivo 0.97 32692
iterativo 0.98 32696
recursivo 0.97 32632
iterativo 0.98 32672
recursivo 0.99 32656
iterativo 0.98 32728
recursivo 0.97 32640
iterativo 0.99 32656
recursivo 0.99 32644
iterativo 1.00 32724
recursivo 0.99 32736
iterativo 1.00 32632
recursivo 0.99 32712
iterativo 1.00 32640
recursivo 0.99 32696
iterativo 1.00 32724
recursivo 1.00 32640
iterativo 1.00 32712
recursivo 0.99 32640
iterativo 0.99 32716
recursivo 0.97 32712
iterativo 0.99 32708
recursivo 0.97 32660
iterativo 0.99 32724
recursivo 0.98 32728
iterativo 0.99 32752
recursivo 0.97 32752
iterativo 0.98 32700
recursivo 0.97 32712
iterativo 0.98 32640
recursivo 0.99 32640
iterativo 1.00 32752
recursivo 0.99 32752
iterativo 0.99 32716
recursivo 0.97 32632
iterativo 0.97 32644
recursivo 0.96 32712
iterativo 0.97 32728
recursivo 0.96 32640
iterativo 0.96 32688
recursivo 0.96 32644
iterativo 0.96 32640
recursivo 0.96 32640
iterativo 0.97 32688
recursivo 0.96 32728
iterativo 0.97 32640
recursivo 0.96 32632
iterativo 0.97 32756
recursivo 0.96 32732
iterativo 0.96 32716
recursivo 0.96 32644
iterativo 0.98 32744
recursivo 0.96 32728
iterativo 0.97 32712
recursivo 0.97 32724
iterativo 0.99 32708
recursivo 0.99 32632
#include <stdio.h>
#include <stdlib.h>
struct No {
int valor;
struct No *esquerda, *direita;
};
struct No* No_new(int valor) {
struct No *no = (struct No*) malloc(sizeof(struct No));
if (!no) {
printf("Erro ao alocar nó\n");
exit(1);
}
no->valor = valor;
no->esquerda = NULL;
no->direita = NULL;
return no;
}
void No_add(struct No *self, int valor) {
if (valor < self->valor) {
if (self->esquerda) {
No_add(self->esquerda, valor);
} else {
self->esquerda = No_new(valor);
}
} else {
if (self->direita) {
No_add(self->direita, valor);
} else {
self->direita = No_new(valor);
}
}
}
struct No_print_stack_item {
struct No *no;
int etapa;
};
void No_print(struct No *self) {
int stack_pointer = 0;
struct No_print_stack_item stack[100];
stack[stack_pointer].no = self;
stack[stack_pointer].etapa = 0;
while (stack_pointer >= 0) {
struct No_print_stack_item *item = &stack[stack_pointer];
if (item->etapa == 0) {
item->etapa = 1;
if (item->no->esquerda) {
++stack_pointer;
stack[stack_pointer].no = item->no->esquerda;
stack[stack_pointer].etapa = 0;
}
} else {
printf(" %d", item->no->valor);
if (item->no->direita) {
item->no = item->no->direita;
item->etapa = 0;
} else {
--stack_pointer;
}
}
}
}
int main() {
FILE *file = fopen("numeros.txt", "r");
if (!file) {
printf("Erro ao abrir arquivo\n");
exit(1);
}
int valor;
if (fscanf(file, "%d", &valor) != 1) {
printf("Erro ao ler número\n");
exit(1);
}
struct No *no = No_new(valor);
while (fscanf(file, "%d", &valor) == 1) {
No_add(no, valor);
}
No_print(no);
printf("\n");
return 0;
}
CC=gcc
CFLAGS=-O3
.PHONY: all clean
all: dados.csv
numeros.txt: numeros.py
python3 $<
dados.csv: run.sh numeros.txt iterativo recursivo
bash $<
clean:
rm -rf numeros.txt iterativo recursivo dados.csv
from random import shuffle
n = list(range(1_000_000))
shuffle(n)
with open('numeros.txt', 'w') as f:
print('\n'.join(str(i) for i in n), file=f)
#include <stdio.h>
#include <stdlib.h>
struct No {
int valor;
struct No *esquerda, *direita;
};
struct No* No_new(int valor) {
struct No *no = (struct No*) malloc(sizeof(struct No));
if (!no) {
printf("Erro ao alocar nó\n");
exit(1);
}
no->valor = valor;
no->esquerda = NULL;
no->direita = NULL;
return no;
}
void No_add(struct No *self, int valor) {
if (valor < self->valor) {
if (self->esquerda) {
No_add(self->esquerda, valor);
} else {
self->esquerda = No_new(valor);
}
} else {
if (self->direita) {
No_add(self->direita, valor);
} else {
self->direita = No_new(valor);
}
}
}
void No_print(struct No *self) {
if (self->esquerda) No_print(self->esquerda);
printf(" %d", self->valor);
if (self->direita) No_print(self->direita);
}
int main() {
FILE *file = fopen("numeros.txt", "r");
if (!file) {
printf("Erro ao abrir arquivo\n");
exit(1);
}
int valor;
if (fscanf(file, "%d", &valor) != 1) {
printf("Erro ao ler número\n");
exit(1);
}
struct No *no = No_new(valor);
while (fscanf(file, "%d", &valor) == 1) {
No_add(no, valor);
}
No_print(no);
printf("\n");
return 0;
}
matplotlib==3.6.1
pandas==1.5.1
scipy==1.9.3
#!/bin/bash
EXECUCOES=100
(
echo 'codigo,tempo,memoria'
for e in $(seq 1 $EXECUCOES); do
for codigo in iterativo recursivo; do
/usr/bin/time -f "$codigo,%e,%M" "./$codigo" > /dev/null
done
done
) |& tee dados.csv
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment