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

2020-12-16 09:59:52 +08:00
 persona5

题目本身很简单,就是实现一个支持 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;
    }

    ......
}
2302 次点击
所在节点    程序员
6 条回复
chendy
2020-12-16 10:42:07 +08:00
不用改,多提交几次,时间和内存消耗都不一样的
毕竟是 java,不确定的东西比较多,除非先预热个几万次,否则运行时间也就图一乐
shuax
2020-12-16 10:47:34 +08:00
同样的代码,每次运行时间都不一样的。
andrewpsy
2020-12-16 10:52:52 +08:00
楼上说的对。

记得有一题贪心整的话时间复杂度是 m+n 但是用二分法是 mlog(n),然后我两个解法都写了在程序入口用 m 和 n 运算一下来决定是用贪心还是二分。我提交了可能有二三十次,完全看不出优势,连规律都摸不清😂
pkupyx
2020-12-17 11:26:49 +08:00
大概编译后运行时的瞎检查的代码量会变多吧
Philippa
2020-12-17 18:59:08 +08:00
算法的核心是复杂度,而不是机器性能的波动和语言本身的奇技淫巧。有些人在 leetcode 上使用一些奇怪的毫无道理的技巧来获得更高的排名其实毫无意义。
raaaaaar
2020-12-18 10:45:35 +08:00
@andrewpsy #3 我们一般说的时间复杂度都是最差的时间复杂度,要数据量足够大时才能明显体现出来,如果数据量不大,那不遵守那个比较规律很正常

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/735872

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX