c - 需要递归函数的优化

Question

我想优化这个函数，让它可以快速输出输入值
(x = 300，y = 120，z = 10)。
我想在连续计算后将值存储在 3D 数组中，但无法实现。

请帮忙。递归太难懂了!

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

为了计算P (300, 120, 10)该函数必须计算 x、y、z 的所有可能组合，使得 0 <= x <= 300 , 0 <= y <= 120 , 0 <= z <= 10 .我想到首先创建一个 3D 数组。如果相应的 arr[x][y][z] 为空，我将调用该函数，否则我将只从 arr[x][y][z] 中获取值。

Answer 1

您需要构建一个 memoized你的函数的版本。即包括一个缓存:

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

但是 P_memoized 的调用者必须分配(并在稍后取消分配)缓存。这对调用者来说是不必要的麻烦，因此您将内存函数包装在包装器中，并将其命名为 P(就像您之前所做的那样)。下面的代码执行此操作，但记住它不会检查 malloc 是否失败(阅读关于 malloc here 的信息):

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

然后你就可以像以前一样使用它了，只是这一次，它要快得多:

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

花式缓存

如果您想多次调用 P，那么每次都创建和删除 cache 可能不是最好的主意。那么您应该考虑执行以下操作:

1. 制作缓存a static variable这样它就存在于对 P
的调用中
2. Use realloc在需要时动态调整缓存大小
3. 不要free P 末尾的缓存(因为它会被重用)

为什么需要动态调整缓存大小？因为，比方说，对 P 的第一次调用是使用 x==10 进行的。然后该函数将创建一个宽度为 10 的缓存。下一次，如果使用 x==20 调用 P，则旧缓存不再足够宽。但其中包含的旧值仍然有用。

This question and its answer讨论 realloc 二维数组。您应该能够将其扩展到您的 3D 版本。

执行此操作后，您可能需要考虑一个新问题:缓存永远不会空闲。因此它会保留分配的内存直到程序退出。那么您可能想要一个全局缓存，而不是一个本地静态缓存，并提供一个单独的函数以在最后释放它。