Personale approccio alla memoizzazione in C usando i puntatori a funzione.

test.c

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