LinkedList.contains执行速度 [英] LinkedList.contains execution speed

问题描述

为什么了Methode LinkedList.contains（）快速的运行速度比这样实现：

Why Methode LinkedList.contains() runs quickly than such implementation:

for (String s : list) 
   if (s.equals(element))
     return true;
return false;

我不认为这之间有很大的差异，以实现（我认为搜索对象不归零），同样的iterator和等于操作

I don't see great difference between this to implementations(i consider that search objects aren't nulls), same iterator and equals operation

推荐答案

让我们来看看<一href="http://www.google.com/$c$csearch/p?hl=en#av_p04Hv9fs/src/share/classes/java/util/LinkedList.java&l=193">the来源$ C ​​$ C （OpenJDK的版本） java.util.LinkedList中的

Let's have a look at the source code (OpenJDK version) of java.util.LinkedList

public boolean contains(Object o) {
    return indexOf(o) != -1;
}
public int indexOf(Object o) {
    int index = 0;
    if (o==null) {
        /* snipped */ 
    } else {
        for (Entry e = header.next; e != header; e = e.next) {
            if (o.equals(e.element))
                return index;
            index++;
        }
    }
    return -1;
}

正如你所看到的，这是一个线性搜索，就像换每个解决方案，所以它不是渐近速度更快。这将会是有趣的，看看你的号码是如何成长与较长的列表，但它可能是一个常数因子慢。

As you can see, this is a linear search, just like the for-each solution, so it's NOT asymptotically faster. It'd be interesting to see how your numbers grow with longer lists, but it's likely to be a constant factor slower.

这其中的原因是，这个的indexOf 适用于内部结构，使用直接字段访问迭代，而不是该换每个使用一个迭代器＆LT; E＆GT; ，其方法也必须另外检查是否有像 ConcurrentModificationException的等

The reason for that would be that this indexOf works on the internal structure, using direct field access to iterate, as opposed to the for-each which uses an Iterator<E>, whose methods must also additionally check for things like ConcurrentModificationException etc.

让我们回到源头，你会发现，电子由迭代器和LT返回下一个（）方法; E＆GT; 的的LinkedList 如下：

Going back to the source, you will find that the E next() method returned by the Iterator<E> of a LinkedList is the following:

private class ListItr implements ListIterator<E> {
   //...
   public E next() {
      checkForComodification();
      if (nextIndex == size)
      throw new NoSuchElementException();

      lastReturned = next;
      next = next.next;
      nextIndex++;
      return lastReturned.element;
  }
  final void checkForComodification() {
      if (modCount != expectedModCount)
         throw new ConcurrentModificationException();
  }

这是大大高于 E = e.next忙; 在 LinkedList.contains ！该迭代器（）的的LinkedList 实际上是一个<一href="http://java.sun.com/javase/6/docs/api/java/util/ListIterator.html"><$c$c>ListIterator,它具有更丰富的功能。他们不需要在你for-each循环，但不幸的是你无论如何也要支付费用。且不说那些防守检查 ConcurrentModificationException的必须执行，即使是不会有任何的修改，而你迭代它的列表中。

This is considerably "busier" than the e = e.next; in LinkedList.contains! The iterator() of a LinkedList is actually a ListIterator, which has richer features. They aren't needed in your for-each loop, but unfortunately you have to pay for them anyway. Not to mention all those defensive checks for ConcurrentModificationException must be performed, even if there isn't going to be any modification to the list while you're iterating it.

所以，是的，迭代一个的LinkedList 为使用客户端的for-each（或更直接地利用其迭代器（）/的ListIterator（） ）比的LinkedList 本身在内部做更昂贵。这是可以预料的，这也就是为什么包含首先提供。

So yes, iterating a LinkedList as a client using a for-each (or more straightforwardly, using its iterator()/listIterator()) is more expensive than what the LinkedList itself can do internally. This is to be expected, which is why contains is provided in the first place.

工作在内部给的LinkedList 巨大的优势，因为：

Working internally gives LinkedList tremendous advantage because:

• 在这可以减少在防守检查角落，因为它知道，它没有违反任何不变量
• 它可以拍摄快捷键和其内部重新presentations工作

那么，你可以学习一下？ 熟悉的API 看看已经提供的功能！;他们很可能会比，如果你已经复制它们作为一个客户更快。

So what can you learn from this? Familiarize yourself with the API! See what functionalities are already provided; they're likely to be faster than if you've had to duplicate them as a client.

这篇关于LinkedList.contains执行速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！