V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
persona5
V2EX  ›  程序员

LeetCode 刷题疑惑,为什么不使用 final 修饰会提升效率?

  •  
  •   persona5 · 2020-12-16 09:59:52 +08:00 · 2285 次点击
    这是一个创建于 1430 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目本身很简单,就是实现一个支持 peek 操作的迭代器。

    Peeking Iterator

    Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

    Example:

    Assume that the iterator is initialized to the beginning of the list: [1,2,3].
    
    Call next() gets you 1, the first element in the list.
    Now you call peek() and it returns 2, the next element. Calling next() after that still return 2. 
    You call next() the final time and it returns 3, the last element. 
    Calling hasNext() after that should return false.
    

    我的实现:

    class PeekingIterator implements Iterator<Integer> {
        private final Iterator<Integer> iterator;
        private Integer value;
    
        public PeekingIterator(Iterator<Integer> iterator) {
            this.iterator = iterator;
            this.value = null;
        }
    
        public Integer peek() {
            if (value != null) return value;
            value = iterator.next();
            return value;
        }
    
        @Override
        public boolean hasNext() {
            return value != null || iterator.hasNext();
        }
    
        @Override
        public Integer next() {
            Integer temp;
            if (value != null) {
                temp = value;
                value = null;
            } else {
                temp = iterator.next();
            }
            return temp;
        }
    }
    

    Runtime 是 93.72%


    iterator 去掉 final 修饰,value 不在 Constructor 中赋值 null,Runtime 就变为 100.00% 了。

    public class PeekingIterator implements Iterator<Integer> {
    
        private Iterator<Integer> iterator;
        private Integer value = null;
    
        public PeekingIterator(Iterator<Integer> iterator) {
            this.iterator = iterator;
        }
    
        ......
    }
    
    6 条回复    2020-12-18 10:45:35 +08:00
    chendy
        1
    chendy  
       2020-12-16 10:42:07 +08:00
    不用改,多提交几次,时间和内存消耗都不一样的
    毕竟是 java,不确定的东西比较多,除非先预热个几万次,否则运行时间也就图一乐
    shuax
        2
    shuax  
       2020-12-16 10:47:34 +08:00
    同样的代码,每次运行时间都不一样的。
    andrewpsy
        3
    andrewpsy  
       2020-12-16 10:52:52 +08:00
    楼上说的对。

    记得有一题贪心整的话时间复杂度是 m+n 但是用二分法是 mlog(n),然后我两个解法都写了在程序入口用 m 和 n 运算一下来决定是用贪心还是二分。我提交了可能有二三十次,完全看不出优势,连规律都摸不清😂
    pkupyx
        4
    pkupyx  
       2020-12-17 11:26:49 +08:00
    大概编译后运行时的瞎检查的代码量会变多吧
    Philippa
        5
    Philippa  
       2020-12-17 18:59:08 +08:00 via iPhone
    算法的核心是复杂度,而不是机器性能的波动和语言本身的奇技淫巧。有些人在 leetcode 上使用一些奇怪的毫无道理的技巧来获得更高的排名其实毫无意义。
    raaaaaar
        6
    raaaaaar  
       2020-12-18 10:45:35 +08:00 via Android
    @andrewpsy #3 我们一般说的时间复杂度都是最差的时间复杂度,要数据量足够大时才能明显体现出来,如果数据量不大,那不遵守那个比较规律很正常
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4554 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 04:02 · PVG 12:02 · LAX 20:02 · JFK 23:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.