花时间运行的递归函数

我对我的代码进行了剖析，发现我的程序花费了大约85％的时间来执行这个特定的递归函数。该函数旨在计算在给定初始位置（x，y）的情况下在马尔可夫链中达到一组状态的概率。花时间运行的递归函数

private static boolean condition(int n){ 
    int i = 0; 
    while (n >= i){ 
     if(n == i*4 || n == (i*4 - 1)) 
      return true; 
      i++; 
     } 
    return false; 
} 

public static double recursiveVal(int x, int y, double A, double B){ 

    if(x> 6 && (x- 2 >= y)){ return 1;} 
    if(y> 6 && (y- 2 >= x)){ return 0;} 
    if(x> 5 && y> 5 && x== y){ return (A*(1-B)/(1 -(A*B) - ((1-A)*(1-B))));} 

    if(condition(x+ y)){ 
     return (recursiveVal(x+1, y,A,B)*A + recursiveVal(x, y+1,A,B)*(1-A)); 
    } 
    else{ 
     return (recursiveVal(x+1, y,A,B)*(1-B) + recursiveVal(x,y+1,A,B)*B); 
    } 
}

有人告诉我99％的递归函数可以被while循环替换。尽管如此，我仍然遇到了麻烦。有谁知道我可以如何提高执行时间或将其重写为迭代循环？

感谢

来源

2010-12-10 Roger

@org，他已经接受了答案。我认为这可能是一个错误？ – jjnguy 2010-12-10 16:16:00

@jjnguy是刚刚注意到，可能是服务计划更新。 – 2010-12-10 16:17:23

@org，可能是。 – jjnguy 2010-12-10 16:18:08

你可以尝试使用一种叫做记忆化基本上将缓存递归调用先前计算的结果。

Wikipedia article on memoization。

作为便笺，我建议您重新格式化您的代码。这里是yoru代码的简化版本。

private static boolean condition(int n){ 
    for (int i = 0; i <= n; i++) 
     if(n == i*4 || n == (i * 4 - 1)) 
      return true; 
    return false; 
} 

public static double recursiveVal(int x, int y, double A, double B){ 

    if (x > 6 && (x - 2 >= y)) 
     return 1; 

    if (y > 6 && (y - 2 >= x)) 
     return 0; 

    if(x > 5 && y > 5 && x == y) 
     return A*(1-B)/(1 -(A*B) - ((1-A)*(1-B))); 

    double val1 = recursiveVal(x+1, y, A, B); 
    double val2 = recursiveVal(x, y+1, A, B); 

    return condition(x + y) 
     ? A * val1 + val2 * (1-A) 
     : (1-B) * val1 + B * val2; 
}

来源

2010-12-10 16:14:55 aioobe

谢谢。你是对的，这在眼睛上更容易 – Roger 2010-12-10 16:27:51

要将其转换为迭代形式，请注意您正在计算两个（离散）变量的函数。您可以使用表格来存储函数的值，并按特定顺序填写表格，以便在您需要时已经计算出所需的值。（在这种情况下，从较高值x和y）。

在这种情况下，边界的情况下（对应于原始的递归基座例）是：

f(7, y..5), f(8, 6) 
f(x..5, 7), f(6, 8) 
f(7, 7)

然后我们填写f(7, 6)和f(6, 7)，然后进行“向下” - 即 F（6 ，6），f（5,6）... f（x，6），f（6,5），f（5,5）... f（x，5）... f（x，y ）。

请注意，看起来像函数调用语法对应于表查找（它真的转换为数组语法）。

来源

2010-12-10 16:18:52 lijie

这就是memoization。看到aioobe的答案。 – Poindexter 2010-12-10 16:24:52

我一直认为memoization需要检查结果是否已被计算。表格填充以相反的使用顺序填充结果。两者都用于动态编程（对应于不同的进行方向 - 自下而上的结构[填表]或自顶向下的划分[记忆]）。虽然我可能是错的，也许memoization适用于两个方向。 – lijie 2010-12-10 16:31:44

如果要重构一个递归函数来迭代之一中的步骤如下：

1）确定递归的基本情况。基本情况到达时，会导致递归结束。每个递归必须有一个定义的基本情况。另外，每次递归调用都必须向基本情况进展（否则递归调用将无限次执行）。
2）实现一个循环，迭代直到达到基本情况。
3）朝基本案例迈进。将新参数发送到循环的顶部，而不是递归方法。如何试图了解它是什么做可以使代码更快

来源

2010-12-10 16:31:58 Cratylus

例/简单...

这种方法试图确定是否“n”是4的倍数或N + 1是4的倍数。这可以写得更短。

private static boolean condition(int n){ 
    return (n+1) & 3 <= 1; 
}

来源

2010-12-10 16:32:34

花时间运行的递归函数

回答

相关问题