Optimisation requise pour la fonction récursive

Question

Je veux optimiser cette fonction afin qu'elle puisse donner une sortie rapide pour les valeurs d'entrée.
(x = 300, y = 120, z = 10).
J'ai pensé à stocker les valeurs dans un tableau 3D après les calculs successifs, mais je n'ai pas réussi à le faire.

Aidez-nous. La récursion est trop difficile à comprendre !

double P(int x, int y, int z) {

    double final;
    if (x >= 0 && (y <= 0 || z <= 0))
        return  0;

    else if (x <= 0 && (y >= 0 || z >= 0) )
        return 1;

    else {     
        final = 0.1 * (P(x,y-1,z)
                       + P(x-1,y-1,z)
                       +  P(x-2,y-1,z)
                       +  P(x-3,y-1,z)
                       +  P(x-4,y-1,z)
                       +  P(x-5,y-1,z)
                       +  P(x-6,y-1,z)
                       +  P(x-1,y,z)
                       +  P(x-1,y,z)
                       +  P(x,y-1,z-1));
        return final;
    }
}

Afin de calculer P (300, 120, 10) la fonction doit calculer toutes les combinaisons possibles de x, y, z telles que 0 <= x <= 300 , 0 <= y <= 120 , 0 <= z <= 10 . J'ai pensé à créer d'abord un tableau 3D. Si le tableau respectif arr[x][y][z] est vide, j'appellerai la fonction, sinon je prendrai simplement la valeur de arr[x][y][z].

Answer 1

Vous devez construire un mémorisé version de votre fonction, c'est-à-dire inclure un cache :

double P_memoized (int x, int y, int z, double ***cache) {

    if (x >= 0 && (y <= 0 || z <= 0))
        return  0;

    else if (x <= 0 && (y >= 0 || z >= 0) )
        return 1;

    else {
        if (cache[x][y][z] < 0.0) /* Negative => uncached.  */
          cache[x][y][z] = 0.1 * (P_memoized(x,y-1,z, cache)
                                  +  P_memoized(x-1,y-1,z, cache)
                                  +  P_memoized(x-2,y-1,z, cache)
                                  +  P_memoized(x-3,y-1,z, cache)
                                  +  P_memoized(x-4,y-1,z, cache)
                                  +  P_memoized(x-5,y-1,z, cache)
                                  +  P_memoized(x-6,y-1,z, cache)
                                  +  P_memoized(x-1,y,z, cache)
                                  +  P_memoized(x-1,y,z, cache)
                                  +  P_memoized(x,y-1,z-1, cache));
        return cache[x][y][z];
    }
}

Mais un appel à P_memoized devra allouer (et plus tard désallouer) l'objet cache . C'est un mal de tête inutile pour l'appelant, donc vous enveloppez la fonction mémorisée dans un wrapper, et l'appelez P (comme vous l'avez fait précédemment). Le code ci-dessous fait cela, mais souvenez-vous de il ne vérifie pas si malloc échoué (Lire à propos de malloc aquí ):

#include <stdlib.h>
double P(int x, int y, int z) {

    double ***cache, final;
    int i, j, k;

    /* Create a cache.  */
    cache = malloc (sizeof (double **) * (x+1));
    for (i = 0; i <= x; i++)
      {
        cache[i] = malloc (sizeof (double *) * (y+1));
        for (j = 0; j <= y; j++)
          {
            cache[i][j] = malloc (sizeof (double) * (z+1));
            for (k = 0; k <= z; k++)
              cache[i][j][k] = -1.0; /* Negative => uncached.  */
          }
      }

    final = P_memoized (x, y, z, cache);

    /* Delete the cache.  */
    for (i = 0; i < x; i++)
      {
        for (j = 0; j < y; j++)
          free (cache[i][j]);
        free (cache[i]);
      }
    free (cache);
    return final;
}

Vous pouvez alors l'utiliser comme vous le faisiez auparavant, mais cette fois, c'est beaucoup plus rapide :

#include <stdio.h>
int main (void)
{
  printf ("%f\n", P (10, 5, 3));
  return 0;
}

Mise en cache fantaisie

Si vous voulez faire plusieurs appels à P puis en créant et en supprimant le cache à chaque fois n'est peut-être pas la meilleure idée. Dans ce cas, vous devriez envisager de faire ce qui suit :

1. Faire le cache a static variable afin qu'il survive aux appels à P
2. Utilisez realloc pour redimensionner dynamiquement le cache lorsque cela est nécessaire
3. Ne fais pas ça. free le cache à la fin de P (parce qu'il sera réutilisé)

Pourquoi faut-il redimensionner dynamiquement le cache ? Parce que, par exemple, le premier appel à P est fait avec x==10 . Ensuite, la fonction créera un cache qui a une largeur de 10. La prochaine fois, si P est appelé avec x==20 l'ancien cache n'est plus assez large. Mais les anciennes valeurs qu'il contient sont toujours utiles.

Cette question et sa réponse parler de realloc dans un réseau 2D. Vous devriez être capable d'étendre cela à votre version 3D.

Une fois que vous aurez fait cela, vous pourrez réfléchir à un nouveau problème : le cache ne reçoit jamais free d. Il conserve donc la mémoire allouée jusqu'à la sortie du programme. Dans ce cas, vous pourriez vouloir avoir un cache global, au lieu d'un cache statique local, et fournir une fonction séparée pour free à la fin.