使用数组来缩短递归二项式分布算法的执行时间

作为一名初级程序员，我最近买了Robert Sedgewick/Kevin Wayne的《Algorithm - Forth Edition》一书，我真的很欣赏每一章末尾的exerices。然而，有一个练习(看起来很简单(让我发疯，因为我找不到解决方案。

你必须采用这种递归算法，该算法找到在 n 次试验中获得恰好 k 次成功的概率，其中 p 是一个事件的成功概率。给出的算法基于递归二项分布论坛。

public static double binomial(int n, int k, double p) {
    if (n == 0 && k == 0)
        return 1.0;
    else if (n < 0 || k < 0)
        return 0.0;
    return (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);
}

本练习的目标是通过将计算值保存在数组中来加快此算法的速度。我已经通过使用另一种获取二项分布 [p(x( = nCr * p^k * (1 - p(^(n - k(] 的方法使这个算法变得相当快，该方法使用迭代方法来查找阶乘。但是，我不明白在这种情况下如何使用数组来缩短执行时间。

任何帮助将不胜感激！

。在有人问之前，这不是家庭作业！

这本书试图教你一种叫做记忆的特殊编程技术，一种更广泛的技术，称为动态编程。当然，在现实生活中，知道一个封闭式的解决方案要好得多，但在解决这个练习的背景下就不行了。

无论如何，这个想法是传递一个 2D 数组作为你的第四个参数，最初用 NaN s 填充它，并在计算任何东西之前检查数组中给定的 n 和k组合是否有解决方案。如果有，请退回;如果没有，则递归计算它，存储在数组中，然后才返回它。

这里的递归算法最终会一遍又一遍地调用特定条件。例如：

例如，通过记住值 (1， 2( 的结果，并在再次使用这些参数调用时立即返回该值，可以提高效率。使用番石榴的Table，这看起来像：

public static double binomial(int n, int k, double p, Table<Integer, Integer, Double> memo) {
    if(memo.contains(n, k))
        return memo.get(n, k);
    double result;
    if (n == 0 && k == 0)
        result = 1.0;
    else if (n < 0 || k < 0)
        result = 0.0;
    else 
        result = (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);
    memo.put(n, k, result);
    return result;
}

有点晚了，但对于那些正在寻找完整解决方案的人来说，下面是我的。首先，我建议其他人阅读这里给出的答案：https://stackoverflow.com/a/6165124/4636721 理解动态编程，记忆和制表的含义

无论如何，关于我的解决方案，所以基本上我们有给定的方法：

// Not efficient at all
private static double binomial(int N, int k, double p)
{
    if (N == 0 && k == 0)
    {
        return 1.0;
    }
    else if ((N < 0) || (k < 0))
    {
        return 0.0;
    }
    else
    {
        return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
    }
}

是的，这真的很慢...递归调用的数量有点大(大约 ~N^2(

是的，您可以使用记忆方法，该方法基本上就像其他人已经说过的那样，基本上是以前计算过的缓存值。对于某些人来说，记忆意味着保留递归策略并检查我们需要的值是否已计算，如果不是程序必须计算并缓存它，则实现起来非常容易：

private static double binomialTopDown(int N, int k, double p)
{
    double[][] cache = new double[N + 1][k + 1];
    for (int i = 0; i < (N + 1); i++)
    {
         Arrays.fill(cache[i], Double.NaN);
    }
    return binomialTopDown(N, k, p, cache);
}
// More efficient
private static double binomialTopDown(int N, int k, double p, double[][] cache)
{
    if ((N == 0) && (k == 0))
    {
        return 1.0;
    }
    else if ((N < 0) || (k < 0))
    {
        return 0.0;
    }
    else if (Double.isNaN(cache[N][k]))
    {
        cache[N][k] = (1.0 - p) * binomialTopDown(N - 1, k, p, cache) + p * binomialTopDown(N - 1, k - 1, p, cache);
    }
    return cache[N][k];
}

诀窍实际上是使用自下而上的方法(也称为制表(以更有效的方式对计算进行排序。这通常是通过使用上述算法的迭代版本来实现的。

// Much more efficient
private static double binomialBottomUp(int N, int k, double p)
{
    /*
    double[][] cache = new double[N + 1][k + 1];
    cache[0][0] = 1.0;
    for (int i = 1; i <= N; i++)
    {
        cache[i][0] = Math.pow(1.0 - p, i);
        for (int j = 1; j <= k; j++)
        {
            cache[i][j] =  p * cache[i - 1][j - 1] + (1.0 - p) * cache[i - 1][j];
        }
    }
    return cache[N][k];
    */
    // Optimization using less memory, swapping two arrays
    double[][] cache = new double[2][k + 1];
    double[] previous = cache[0];
    double[] current = cache[1];
    double[] temp;
    previous[0] = 1.0;
    for (int i = 1; i <= N; i++)
    {
        current[0] = Math.pow(1.0 - p, i);
        for (int j = 1; j <= k; j++)
        {
            current[j] =  p * previous[j - 1] + (1.0 - p) * previous[j];
        }
        temp = current;
        current = previous;
        previous = temp;
    }
    return previous[k];
}

这是使用动态编程和自下而上方法的最有效方法。

希望这有帮助。

相关内容

最新更新

热门标签：