V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member  Sign In
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
persona5
V2EX  ›  程序员

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

  •  
  •   persona5 · Dec 16, 2020 · 2729 views
    This topic created in 1966 days ago, the information mentioned may be changed or developed.

    题目本身很简单,就是实现一个支持 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 replies    2020-12-18 10:45:35 +08:00
    chendy
        1
    chendy  
       Dec 16, 2020
    不用改,多提交几次,时间和内存消耗都不一样的
    毕竟是 java,不确定的东西比较多,除非先预热个几万次,否则运行时间也就图一乐
    momo1999
        2
    momo1999  
       Dec 16, 2020
    同样的代码,每次运行时间都不一样的。
    andrewpsy
        3
    andrewpsy  
       Dec 16, 2020
    楼上说的对。

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