这个现在非常常见的算法问题是在白板考试期间由监考人员提出的。我的工作是观察、倾听和客观判断给出的答案，但我无法控制这个问题，也无法与回答者互动。
给了五分钟的时间分析问题，考生可以写项目符号，伪代码(这在实际编写代码时是允许的，只要明确指出，以及将伪代码作为注释或TODO任务的人在弄清楚算法之前得到了加分)。
得到这个问题的人无法当场开始研究递归算法，所以监考人最终一步一步地把他带到了他的解决方案，在我看来这不是最优的(嗯，与我选择的解决方案不同)在代码优化方面很难客观地给某人打分)。
监考人:
public class Staircase {
public static int stairs;
public Staircase() {
int a = counting(stairs);
System.out.println(a);
}
static int counting(int n) {
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return counting(n - 1) + counting(n - 2) + counting(n - 3);
}
public static void main(String[] args) {
Staircase child;
long t1 = System.nanoTime();
for (int i = 0; i < 30; i++) {
stairs = i;
child = new Staircase();
}
System.out.println("Time:" + ((System.nanoTime() - t1)/1000000));
}
}
//
我的:
public class Steps {
public static int stairs;
int c2 = 0;
public Steps() {
int a = step2(0);
System.out.println(a);
}
public static void main(String[] args) {
Steps steps;
long t1 = System.nanoTime();
for (int i = 0; i < 30; i++) {
stairs = i;
steps = new Steps();
}
System.out.println("Time:" + ((System.nanoTime() - t1) / 1000000));
}
public int step2(int c) {
if (c + 1 < stairs) {
if (c + 2 <= stairs) {
if (c + 3 <= stairs) {
step2(c + 3);
}
step2(c + 2);
}
step2(c + 1);
} else {
c2++;
}
return c2;
}
}
输出:
监考人:时间:356
我的:时间:166
有人可以澄清哪种算法更好/更优化吗？我的算法的执行时间似乎不到一半，(但我正在引用和更新一个我认为相当无关紧要的额外整数)并且它允许设置任意开始和结束步骤，而无需首先现在它们的差异(尽管对于高于 n=40 的任何内容，您都需要一个 CPU 的野兽)。
我的问题:(随意忽略上面的例子)你如何正确地对类似的基于递归的问题(汉诺塔等)进行基准测试。你是只看时间，还是考虑其他因素(堆？)。
最佳答案
前言:您可以在不到一毫秒的时间内轻松执行此计算。详情如下...
哪一个更好”？
哪种算法“更好”的问题可能涉及执行时间，但也涉及其他方面，例如实现风格。Staircase 实现更短，更简洁，恕我直言，更具可读性。更重要的是:它不涉及 状态 。您在那里引入的 c2 变量破坏了纯函数递归实现的优点(和美感)。这可能很容易修复，尽管实现已经变得更类似于 Staircase 了。
衡量绩效
关于执行时间的问题:在 Java 中正确测量执行时间很棘手。
相关阅读:
为了正确可靠地测量执行时间，存在多种选择。除了像 VisualVM 这样的分析器，还有像 JMH 或 Caliper 这样的框架，但不可否认，使用它们可能需要一些努力。
对于非常基本的手动 Java Microbenchmark 的最简单形式，您必须考虑以下事项:
再次: 这些只是经验法则 ，仍然可能有意想不到的结果(请参阅上面的链接了解更多详情)。但是使用此策略，您通常会获得有关性能的良好指示，并且至少可以看到算法之间是否真的可能存在显着差异。
方法之间的差异
Staircase 实现和 Steps 实现没有太大区别。主要的概念区别是
Staircase 实现是从 向下计数 ，而 Steps 实现是在 向上计数 。实际影响性能的主要区别是 Base Case 的处理方式(请参阅 Wikipedia 上的 Recursion)。在您的实现中，您避免在不必要时递归调用该方法，代价是一些额外的
if 语句。 Staircase 实现对基本情况使用了一种非常通用的处理方式，只检查是否 n < 0 。可以考虑一种结合两种方法思想的“中间”解决方案:
class Staircase2
{
public static int counting(int n)
{
int result = 0;
if (n >= 1)
{
result += counting(n-1);
if (n >= 2)
{
result += counting(n-2);
if (n >= 3)
{
result += counting(n-3);
}
}
}
else
{
result += 1;
}
return result;
}
}
它仍然是没有状态的递归，并总结了中间结果，通过使用一些
if 查询避免了许多“无用”的调用。它已经明显快于原始 Staircase 实现，但仍然比 Steps 实现慢一点。为什么这两种解决方案都很慢
对于这两种实现，实际上没有什么要计算的。该方法由几个
if 语句和一些附加内容组成。这里最昂贵的事情实际上是递归本身，以及深度嵌套的调用树。这就是这里的关键点:这是一个调用 树 。想象一下它在给定数量的步骤中计算什么，作为“伪代码调用层次结构”:
compute(5)
compute(4)
compute(3)
compute(2)
compute(1)
compute(0)
compute(0)
compute(1)
compute(0)
compute(0)
compute(2)
compute(1)
compute(0)
compute(0)
compute(1)
compute(0)
compute(3)
compute(2)
compute(1)
compute(0)
compute(0)
compute(1)
compute(0)
compute(0)
compute(2)
compute(1)
compute(0)
compute(0)
可以想象，当数字变大时，这会呈指数增长。并且所有结果都经过数百、数千或数百万次的计算。这是可以避免的
快速解决方案
使计算更快的关键思想是使用 Dynamic Programming 。这基本上意味着存储中间结果以供以后检索，因此不必一次又一次地计算它们。
在这个例子中实现了它，它也比较了所有方法的执行时间:
import java.util.Arrays;
public class StaircaseSteps
{
public static void main(String[] args)
{
for (int i = 5; i < 33; i++)
{
runStaircase(i);
runSteps(i);
runDynamic(i);
}
}
private static void runStaircase(int max)
{
long before = System.nanoTime();
long sum = 0;
for (int i = 0; i < max; i++)
{
sum += Staircase.counting(i);
}
long after = System.nanoTime();
System.out.println("Staircase up to "+max+" gives "+sum+" time "+(after-before)/1e6);
}
private static void runSteps(int max)
{
long before = System.nanoTime();
long sum = 0;
for (int i = 0; i < max; i++)
{
sum += Steps.step(i);
}
long after = System.nanoTime();
System.out.println("Steps up to "+max+" gives "+sum+" time "+(after-before)/1e6);
}
private static void runDynamic(int max)
{
long before = System.nanoTime();
long sum = 0;
for (int i = 0; i < max; i++)
{
sum += StaircaseDynamicProgramming.counting(i);
}
long after = System.nanoTime();
System.out.println("Dynamic up to "+max+" gives "+sum+" time "+(after-before)/1e6);
}
}
class Staircase
{
public static int counting(int n)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else
return counting(n - 1) + counting(n - 2) + counting(n - 3);
}
}
class Steps
{
static int c2 = 0;
static int stairs;
public static int step(int c)
{
c2 = 0;
stairs = c;
return step2(0);
}
private static int step2(int c)
{
if (c + 1 < stairs)
{
if (c + 2 <= stairs)
{
if (c + 3 <= stairs)
{
step2(c + 3);
}
step2(c + 2);
}
step2(c + 1);
}
else
{
c2++;
}
return c2;
}
}
class StaircaseDynamicProgramming
{
public static int counting(int n)
{
int results[] = new int[n+1];
Arrays.fill(results, -1);
return counting(n, results);
}
private static int counting(int n, int results[])
{
int result = results[n];
if (result == -1)
{
result = 0;
if (n >= 1)
{
result += counting(n-1, results);
if (n >= 2)
{
result += counting(n-2, results);
if (n >= 3)
{
result += counting(n-3, results);
}
}
}
else
{
result += 1;
}
}
results[n] = result;
return result;
}
}
在我的电脑上的结果如下:
...
Staircase up to 29 gives 34850335 time 310.672814
Steps up to 29 gives 34850335 time 112.237711
Dynamic up to 29 gives 34850335 time 0.089785
Staircase up to 30 gives 64099760 time 578.072582
Steps up to 30 gives 64099760 time 204.264142
Dynamic up to 30 gives 64099760 time 0.091524
Staircase up to 31 gives 117897840 time 1050.152703
Steps up to 31 gives 117897840 time 381.293274
Dynamic up to 31 gives 117897840 time 0.084565
Staircase up to 32 gives 216847936 time 1929.43348
Steps up to 32 gives 216847936 time 699.066728
Dynamic up to 32 gives 216847936 time 0.089089
语句顺序的微小变化(“微优化”)可能会产生很小的影响，或产生显着的差异。但是使用完全不同的方法可以产生真正的不同。
关于递归爬楼梯拼图的 Java 基准测试，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25635713/