Análise de desempenho de um código iterativo e recursivo para percorrer uma árvore binária

analise-percorrer-arvore.ipynb

dados.csv

iterativo.c

#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;
}

Makefile

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

numeros.py

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)

recursivo.c

#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;
}

requirements.txt

matplotlib==3.6.1
pandas==1.5.1
scipy==1.9.3

run.sh

#!/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