Skip to content

Instantly share code, notes, and snippets.

@aciceri
Created May 28, 2019 23:25
Show Gist options
  • Save aciceri/b1872e3c987d7b6653daff6534c95f05 to your computer and use it in GitHub Desktop.
Save aciceri/b1872e3c987d7b6653daff6534c95f05 to your computer and use it in GitHub Desktop.
Personale approccio alla memoizzazione in C usando i puntatori a funzione.
#include <stdio.h>
#include <stdlib.h>
/* Roba relativa alla gestione della memoizzazione, in teoria riutilizzabile per
* diverse funzioni */
#define LUNGHEZZA 1000
struct { //Memoria globale, cioe' vettore di coppie input/output
int in, out;
} memoria[LUNGHEZZA];
int lun = 0; //Numero di valori memoizzati finora
int memoizza(int (*f)(int), int n) { //Una specie di decoratore
for (int i = 0; i < lun; i++) //Cerco se ho gia' calcolato f(n)
if (memoria[i].in == n) return memoria[i].out; //In quel caso
int out = f(n); //Altrimenti
lun++;
memoria[lun-1].in = n;
memoria[lun-1].out = out;
return out;
}
int fib(int n) { //Definizione ricorsiva inefficiente di Fibonacci
return (n == 0 || n == 1) ? 1 : fib(n-2) + fib(n-1);
}
int fib2(int n) { //Versione memoizzata
return (n == 0 || n == 1) ? 1 : memoizza(fib2, n-2) + memoizza(fib2, n-1);
}
int main(int argc, char** argv) {
printf("%d\n", argv[1][0] == 'm' ? fib2(atoi(argv[2])) : fib(atoi(argv[2])));
return 0;
}
/* Esempio di utilizzo:
*
* Calcolo il 42esimo numero di Fibonacci usando la versione NON-memoizzata,
* sul mio pc ci mette quasi 2 secondi ->
* ./test n 42
*
* Stessa computazione con la versione memoizzata ->
* ./test m 42
* E' praticamente istantaneo, wow */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment