为什么list.size()> 0比Java中的list.isEmpty()慢？

Question

为什么list.size()>0比list.isEmpty()Java 慢？换句话说,为什么isEmpty()更好size()>0？

当我查看实现时ArrayList,看起来速度应该是相同的:

ArrayList.size()

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size() {
      return size;
    }

ArrayList.isEmpty()

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
        return size == 0;
     }

如果我们只是编写一个简单的程序来获取两种方法所需的时间,那么在所有情况下size()都需要更多的isEmpty()时间,为什么会这样呢？

这是我的TestCode;

import java.util.List;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        List l=new Vector();
        int i=0;
        for(i=0;i<10000;i++){
            l.add(new Integer(i).toString());
        }
        System.out.println(i);
        Long sTime=System.nanoTime();
        l.size();
        Long eTime=System.nanoTime();
        l.isEmpty();
        Long eeTime=System.nanoTime();
        System.out.println(eTime-sTime);
        System.out.println(eeTime-eTime);
    }
}

这里eTime-sTime>eeTime-eTime在所有情况下.为什么？

Answer 1

对于ArrayList,是的 - 你是正确的,操作(大致)同时进行.

对于列表的其他实现 - 例如天真链接列表* - 计算大小可能需要很长时间,而您实际上只关心它是否大于零.

因此,如果您完全知道该列表是一个实现ArrayList并且永远不会改变那么它并不重要; 但:

1. 无论如何,这都是糟糕的编程习惯,将自己束缚到特定的实现.
2. 如果事情发生变化几年后代码重组,测试将显示"它工作"但事情运行效率低于以前
3. 即使在最好的情况下,List仍然不会比这更快ArrayList,所以没有令人信服的理由使用前者.
4. size() == 0 更清楚地定义了您实际关心和测试的内容,因此使您的代码更容易理解.

(另外,我会在你的问题标题中修改NULL的用法;问题本身和这些操作与任何对象引用是否为空都无关.)

*我最初写isEmpty()在这里,暗示引用java.util.LinkedList,虽然该特定实现确实显式存储其长度,这使得size()成为O(1)操作.更天真的链表操作可能不会这样做,并且在更一般意义上,List的实现没有效率保证.

Answer 2

您的测试代码存在缺陷.

只需颠倒顺序,即先调用isEmpty,然后调整大小> 0秒,你就会得到相反的结果.这是由于类加载,缓存等.

Answer 3

对不起,但你的基准是有缺陷的.看看Java理论和实践:有缺陷的微基准的剖析,以获得关于如何处理基准的一般描述.

更新:对于适当的基准测试,您应该查看Japex.

Answer 4

.size（）必须查看整个列表，而.isEmpty（）可以停在第一个列表上。

显然依赖于实现，但是正如前面已经说过的，如果您不需要知道实际大小，为什么还要麻烦计算所有元素？

Answer 5

你说:

这里eTime-sTime>eeTime-eTime在所有情况下,为什么呢？

首先,这可能是因为你的测试代码.您无法同时测试调用l.size()和l.isEmpty()的速度,因为它们都查询相同的值.很可能调用l.size()已将列表的大小加载到cpu缓存中,因此调用l.isEmpty()的速度要快得多.

您可以尝试在两个单独的程序中调用l.size()几百万次和l.isEmpty()几百万次但理论上编译器可以优化掉所有这些调用,因为您实际上并没有执行任何操作结果.

在任何情况下,两者之间的性能差异可以忽略不计,特别是一旦进行比较,您需要做的是查看列表是否为空(l.size() == 0).生成的代码很可能看起来几乎完全相似.正如其他一些海报所指出的那样,在这种情况下,您希望优化可读性,而不是速度.

编辑:我自己测试过.这几乎是一个折腾.size()并且在长期运行中isEmpty()使用Vector了不同的结果,并没有始终如一地击败对方.当跑上跑ArrayList size()似乎更快,但不是很多.这很可能是因为访问Vector是同步的,因此在尝试对这些方法进行基准访问时,您真正看到的是同步开销,这可能非常敏感.

这里需要考虑的是,当你尝试优化一个方法调用时,执行时间会有几纳秒的差异,那么你做错了.首先获得基础知识,比如使用Long应该使用的s long.