Java Benchmark用于递归楼梯攀爬拼图

Question

在白板考试期间,监考人员要求这个非常常见的算法问题.我的工作是观察,倾听并客观地判断所给出的答案,但我既没有控制这个问题,也没有与回答的人互动.分析问题的时间有五分钟,候选人可以编写子弹笔记,伪代码(这在实际代码编写期间允许,只要明确指出,人们包括伪代码作为注释或TODO任务在搞清楚算法得到奖励积分之前).

• "一个孩子爬上楼梯,有n个台阶,可以一步一跳,两步或三步.实施一种方法来计算孩子跳楼梯的可能方式."

得到这个问题的人无法在现场开始使用递归算法,因此监考人员最终逐件引导他进入HIS解决方案,在我看来这不是最优的(好吧,与我选择的解决方案不同)在代码优化方面很难客观地评价某人.

宝洁:

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;
}
}

输出: Proctor:时间:356 矿:时间:166

有人可以澄清哪种算法更好/更优化？我的算法的执行时间似乎不到一半,(但我引用并更新了一个我认为相当无关紧要的额外整数)并且它允许设置任意的开始和结束步骤而不需要首先现在它们的区别(虽然对于高于n = 40的任何东西,你需要一个CPU的野兽).

我的问题:(随意忽略上面的例子)你如何正确地对基于类似递归的问题(河内塔等)进行基准测试.你只是看时间,还是考虑其他事情(堆？).

Answer 1

预告片:您可以​​在不到一毫秒的时间内轻松完成此计算.细节如下......

哪一个更好"？

哪个算法"更好"的问题可以指执行时间,也可以指其他事情,如实现风格.

在Staircase实现更短,更简洁,恕我直言,更具可读性.更重要的是:它不涉及一个国家.c2你在那里引入的变量破坏了纯函数递归实现的优点(和美).这可以很容易地修复,尽管实现已经变得更加类似于那个Staircase.

测量性能

关于执行时间的问题:正确地测量Java中的执行时间是棘手的.

相关阅读:

• 如何在Java中编写正确的微基准测试？
• Java理论与实践:有缺陷的微基准的剖析
• HotSpot Internals

为了正确可靠地测量执行时间,存在几种选择.除了像VisualVM这样的分析器之外,还有像JMH或Caliper这样的框架,但不可否认,使用它们可能需要付出一些努力.

对于最简单的基本手动Java Microbenchmark形式,您必须考虑以下事项:

• 多次运行算法,让JIT有机会参与进来
• 交替运行算法,而不是一个接一个地运行
• 随着输入大小的增加运行算法
• 以某种方式保存并打印计算结果,以防止计算被优化掉
• 在基准测试期间不要向控制台打印任何内容
• 考虑垃圾收集器(GC)可能会导致时序失真

再说一遍:这些只是经验法则,可能仍有意想不到的结果(有关详细信息,请参阅上面的链接).但是这种策略,你通常获得有关性能的良好指示,并且至少可以看它是否可能是因为真的是算法之间显著的差异.

方法之间的差异

在Staircase实施和Steps执行都不是很不同的.

主要的概念不同的是,Staircase实现计数下降,而Steps实现计数了.

实际影响性能的主要区别在于如何处理基本案例(请参阅维基百科上的递归).在您的实现中,您可以避免在不需要时以递归方式调用该方法,但会以一些其他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)

可以想象,当数量变大时,这会呈指数增长.并且所有结果都计算了数百,数千或数百万次.这可以避免

快速解决方案

使计算更快的关键思想是使用动态编程.这基本上意味着存储中间结果以供以后检索,因此不必一次又一次地计算它们.

它在这个例子中实现,它还比较了所有方法的执行时间:

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

陈述顺序的微小变化("微观优化")可能会产生很小的影响,或产生明显的差异.但使用完全不同的方法可以产生真正的不同.