递归算法效率- Java

Question

我正在做一个编码项目，我对程序的速度有一个问题。该程序接受1到80之间的输入，该输入表示火柴杆的数量，并输出该火柴杆的数量可以构成多少个不同的数字。

例:数字1可以由2根火柴棒组成，数字2需要5根火柴棒

下面是程序的完整提示符：

​

​

这是我想出的计算所有可能输出的算法的代码，它对于输入的低端运行得相当好，尽管对于像80这样的大输入来说效率很低，需要花费几个小时来计算所有的可能性。我怎样才能把这个时间减少到最少呢？

N表示输入，Counter对象所做的全部工作就是跟踪创建的每个可能的数字

public static void digitCounter(int n, Counter count) {
    if (n < 2) {
        //ouput
    } else {
        if (count.getCount() == 0) {

            // If there are enough match sticks to form it
            // accounts for 0 only once
            if (n >= 7) {
                // counts 0
                count.setCount(10);
                // counts 1
                digitCounter(n - 2, count);
                // counts 2
                digitCounter(n - 5, count);
                // counts 3
                digitCounter(n - 5, count);
                // count 4
                digitCounter(n - 4, count);
                // counts 5
                digitCounter(n - 5, count);
                // counts 6
                digitCounter(n - 6, count);
                // counts 7
                digitCounter(n - 3, count);
                // counts 8
                digitCounter(n - 7, count);
                // counts 9
                digitCounter(n - 5, count);
            } else if (n == 6) {
                count.setCount(9);
                digitCounter(n - 2, count);
                digitCounter(n - 5, count);
                digitCounter(n - 5, count);
                digitCounter(n - 4, count);
                digitCounter(n - 5, count);
                digitCounter(n - 6, count);
                digitCounter(n - 3, count);
                digitCounter(n - 5, count);
            } else if (n == 5) {
                count.setCount(7);
                digitCounter(n - 2, count);
                digitCounter(n - 5, count);
                digitCounter(n - 5, count);
                digitCounter(n - 4, count);
                digitCounter(n - 5, count);
                digitCounter(n - 3, count);
                digitCounter(n - 5, count);
            } else if (n == 4) {
                count.setCount(3);
                digitCounter(n - 2, count);
                digitCounter(n - 4, count);
                digitCounter(n - 3, count);
            } else if (n == 3) {
                count.setCount(2);
                digitCounter(n - 2, count);
                digitCounter(n - 3, count);
            } else if (n == 2) {
                count.setCount(1);
                digitCounter(n - 2, count);
            }
        }

        // Accounts for every other number after 0 is accounted for so
        // numbers with leading 0's are not formed
        // Ex: 001 is illegal
        else {
            if (n >= 7) {
                count.setCount(count.getCount() + 10);
                digitCounter(n - 6, count);
                digitCounter(n - 2, count);
                digitCounter(n - 5, count);
                digitCounter(n - 5, count);
                digitCounter(n - 4, count);
                digitCounter(n - 5, count);
                digitCounter(n - 6, count);
                digitCounter(n - 3, count);
                digitCounter(n - 7, count);
                digitCounter(n - 5, count);
            } else if (n == 6) {
                count.setCount(count.getCount() + 9);
                digitCounter(n - 6, count);
                digitCounter(n - 2, count);
                digitCounter(n - 5, count);
                digitCounter(n - 5, count);
                digitCounter(n - 4, count);
                digitCounter(n - 5, count);
                digitCounter(n - 6, count);
                digitCounter(n - 3, count);
                digitCounter(n - 5, count);
            } else if (n == 5) {
                count.setCount(count.getCount() + 7);
                digitCounter(n - 2, count);
                digitCounter(n - 5, count);
                digitCounter(n - 5, count);
                digitCounter(n - 4, count);
                digitCounter(n - 5, count);
                digitCounter(n - 3, count);
                digitCounter(n - 5, count);
            } else if (n == 4) {
                count.setCount(count.getCount() + 3);
                digitCounter(n - 2, count);
                digitCounter(n - 4, count);
                digitCounter(n - 3, count);
            } else if (n == 3) {
                count.setCount(count.getCount() + 2);
                digitCounter(n - 2, count);
                digitCounter(n - 3, count);
            } else if (n == 2) {
                count.setCount(count.getCount() + 1);
                digitCounter(n - 2, count);
            }
        }
    }

Answer 1

如果您修改了设计，让digitCounter(n)返回n牙签可能形成的数字计数，然后将该值缓存到一个持久映射中，会怎么样？在进入digitCounter时，如果您已经计算过一次，请检查地图并返回缓存值。那么你仍然会有一个递归算法，但它不需要对相同的N进行重复的调用。

Answer 2

你可以用给定的匹配数乘以你得到的解的数目。您还可以缓存解决方案的数量，直到给定的数量。

public static long solutionsFor(int matchCount) {
    long[] counts = new long[matchCount+1];
    for(int i = 0; i <= matchCount; i++) {
       long count = ... calculate count based on previous values ...
       counts[i] = count;
    }
    return counts[matchCount];
}

性能增益是O(n)，对于返回long的最大问题，您可能会在几毫秒内得到答案。

Answer 3

你的问题是，一次digitCounter调用可能会产生多达10个对digitCounter的调用，这可能会产生更多对它的调用。因此，您首先要尝试优化的是减少关闭呼叫的数量。

@宣传册问：

在许多情况下，

会多次调用digitCounter(n-5，计数)。你希望第二次、第三次或第四次调用时结果会有所不同吗？

这应该是你要优化的第一条线索。每次调用digitCounter(n-5, count)时，添加到计数器的实际计数应该相同。所以我建议你让digit counter直接返回计数，然后自己加法。要表示是否计数为0，请添加一个标志，指示它是否是对digitCounter的最顶层调用。

使用n=10调用digitCounter。

对于count=0，您将在以下代码中结束(删除注释)

        if (n >= 7) {
            count.setCount(10);
            digitCounter(n - 2, count);
            digitCounter(n - 5, count);
            digitCounter(n - 5, count);
            digitCounter(n - 4, count);
            digitCounter(n - 5, count);
            digitCounter(n - 6, count);
            digitCounter(n - 3, count);
            digitCounter(n - 7, count);
            digitCounter(n - 5, count);
        } else if (n == 6) {

您的有效呼叫

1x digitCounter(n - 2, count);

1x digitCounter(n - 3, count);

1x digitCounter(n - 4, count);

4倍digitCounter(n - 5, count);

1x digitCounter(n - 6, count);

1x digitCounter(n - 7, count);

调用n= 10时为digitCounter(5, count);的digitCounter(n - 5, count);会导致对digitCounter的额外10次调用。因此，通过调用它一次而不是4次，您可以节省3x(1+10)=33次调用。

另一个优化是保存您执行的最后一个调用。您知道digitCounter(0)的结果是0。那么，为什么要尝试计算它呢？

        } else if (n == 2) {
            count.setCount(count.getCount() + 1);
            digitCounter(n - 2, count);
        }

可以重写为

        } else if (n == 2) {
            count.setCount(count.getCount() + 1);
            digitCounter(2 - 2, count);
        }

因此您可以删除调用digitCounter(2 - 2, count);，因为它不会影响您的结果。同样，digitCounter(1)的结果为0。因此，在优化了case n=3之后，我们又删除了2个不必要的调用。digitCounter(2)总是1。所以对于n=4，你可以删除3个不必要的调用，只需将计数器增加4而不是3。

您也可以用同样的方法优化n=5。digitCounter(3)始终为2。因此，您可以消除7个额外的调用，并将计数器增加10，而不是仅增加7。我让您自己优化case n=6。

这应该已经大大减少了递归调用。它可能看起来很小，但它很快就会积累起来。

下一个优化是缓存，就像@JVMATL建议的那样，你可以节省大量的大N。对digitCounter(n-2)的调用将导致对digitCounter((n-2) -2)的调用，这相当于digitCounter(n-4)。因此，您不需要再次计算该值，这将为大n(如n=80)带来巨大的节省。即使缓存可能对小n没有帮助，甚至可能增加运行时间(不管怎么说，谁关心毫秒)，但是大n(轻松达到秒/分钟)会有很大的收益。