7

我想优化这个函数，以便它可以快速输出输入值
（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] 中获取值。

4

1 回答 1

10

您需要构建函数的记忆版本。即包括一个缓存：

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将不得不分配（然后解除分配）cache. 这对调用者来说是一个不必要的头痛，因此您将 memoized 函数包装在一个包装器中，然后调用它P（就像您之前所做的那样）。下面的代码会执行此操作，但请记住它不会检查是否失败（在此处malloc阅读）：malloc 

#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. 使缓存成为一个static变量，以便它存在于对P
  2. 用于realloc在需要时动态调整缓存大小
  3. 不要free缓存在末尾P（因为会被重用）

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

This question and its answer谈论reallocing a 2D array。您应该能够将其扩展到您的 3D 版本。

完成此操作后，您可能需要考虑一个新问题：缓存永远不会被freed。所以它会保留分配的内存，直到程序退出。然后，您可能希望拥有一个全局缓存，而不是本地静态缓存，并free最终为其提供单独的功能。

于 2012-06-04T16:58:11.217 回答