V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
Deardrops
V2EX  ›  Go 编程语言

Leetcode 求二叉树的最大深度问题,为什么这两种解法耗时会相差两倍?

  •  1
     
  •   Deardrops ·
    deardrops · 2018-12-08 12:25:18 +08:00 · 3883 次点击
    这是一个创建于 2213 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目:给定一个二叉树,找出其最大深度。 语言:Golang

    解法①:

    // 16ms, beat 12.46%
    func maxDepth(root *TreeNode) int {
    	if root == nil {
    		return 0
    	}
    	leftDepth := maxDepth(root.Left)
    	rightDepth := maxDepth(root.Right)
    	if leftDepth > rightDepth {
    		return leftDepth + 1
    	} else {
    		return rightDepth + 1
    	}
    }
    

    解法②:

    // 8ms, beat 100%
    func maxDepth(root *TreeNode) int {
    	if root != nil {
    		leftDepth := maxDepth(root.Left)
    		rightDepth := maxDepth(root.Right)
    		if leftDepth > rightDepth {
    			return 1+leftDepth
    		}
    		return 1+rightDepth
    	}
    	return 0
    }
    

    实际提交到 leetcode 上,前者耗时 16ms,后者耗时 8ms。

    初学 Golang,请问这两段代码为什么执行时间会差两倍?

    14 条回复    2018-12-08 19:02:02 +08:00
    Jex
        1
    Jex  
       2018-12-08 12:33:47 +08:00   ❤️ 4
    要先学会正确的性能测试方法
    notreami
        2
    notreami  
       2018-12-08 12:47:57 +08:00   ❤️ 1
    第一个解法,我这边运行是 8ms
    做第一个题的时候,就发现同样的代码,执行结果耗时有差异,猜测可能是 gc,或者资源排队等问题。
    lhx2008
        3
    lhx2008  
       2018-12-08 12:55:51 +08:00 via Android   ❤️ 1
    leetcode 的隔离很差,波动大也很正常
    Deardrops
        4
    Deardrops  
    OP
       2018-12-08 12:56:39 +08:00
    @notreami 感谢解答,还以为代码里有什么高深莫测的东西。
    kaitian521
        5
    kaitian521  
       2018-12-08 13:20:47 +08:00
    c
    kaitian521
        6
    kaitian521  
       2018-12-08 13:22:16 +08:00
    试一下 maxDepth(root.Left)>maxDepth(root.Right)? 1+maxDepth(root.Left): 1+maxDepth(root.Right);
    msg7086
        7
    msg7086  
       2018-12-08 13:23:07 +08:00
    你自己拿个秒表,掐两次,然后想想为什么其中一次会是另一次时间的两三倍,就知道原因了。
    QK8wAUi0yXBY1pT7
        8
    QK8wAUi0yXBY1pT7  
       2018-12-08 13:39:30 +08:00
    你自己同一个解法不同时间再提交,也可能差两倍
    azuki
        9
    azuki  
       2018-12-08 15:22:46 +08:00 via Android
    @hxd 对的。
    onepunch
        10
    onepunch  
       2018-12-08 15:35:07 +08:00
    运行一万次的时间 / 10000 是每次运行的时间 [手动狗头]
    zzj0311
        11
    zzj0311  
       2018-12-08 16:28:47 +08:00 via Android
    leetcode 时间并不能作为性能测试的依据,特别是几个 ms 的那种
    gqw121314
        12
    gqw121314  
       2018-12-08 17:18:23 +08:00
    我相同的代码重复提交了 3 次,每次时间都不一样。。。
    akira
        13
    akira  
       2018-12-08 18:34:35 +08:00
    以 ms 为单位的性能统计,±50ms 很正常的
    bubuhere
        14
    bubuhere  
       2018-12-08 19:02:02 +08:00 via iPhone
    leetcode 给出的时间没有太大参考性
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2551 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 10:29 · PVG 18:29 · LAX 02:29 · JFK 05:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.