gpt4 book ai didi

java - LinkedList.contains 执行速度

转载 作者:搜寻专家 更新时间:2023-11-01 01:09:24 25 4
gpt4 key购买 nike

为什么 Methode LinkedList.contains() 比这样的实现运行得更快:

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

我没有看到这与实现(我认为搜索对象不是空值)、相同的迭代器和等于操作之间有很大区别

最佳答案

我们来看看the source code (OpenJDK 版本)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;
}

如您所见,这是一个线性搜索,就像 for-each 解决方案一样,因此它不会渐进地更快。看看您的数字如何随着更长的列表而增长会很有趣,但这可能是一个较慢的常数因素。

原因是这个 indexOf在内部结构上工作,使用直接字段访问进行迭代,而不是使用 Iterator<E> 的 for-each ,其方法还必须另外检查 ConcurrentModificationException 之类的内容等

回到源头,你会发现E next() Iterator<E> 返回的方法的 LinkedList是以下内容:

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 ! iterator()LinkedList实际上是一个 ListIterator , 具有更丰富的特征。在您的 for-each 循环中不需要它们,但不幸的是您无论如何都必须为它们付费。更不用说所有那些针对 ConcurrentModificationException 的防御性检查了必须执行,即使在迭代列表时不会对列表进行任何修改。


结论

所以是的,迭代一个 LinkedList作为使用 for-each 的客户端(或者更直接地说,使用它的 iterator()/listIterator() )比 LinkedList 更昂贵自己内部可以做。这是可以预料的,这就是为什么 contains首先提供。

内部工作给出 LinkedList巨大的优势,因为:

  • 它可以在防御性检查中偷工减料,因为它知道它没有违反任何不变量
  • 它可以走捷径并使用其内部表示

那么你能从中学到什么? 熟悉 API! 查看已经提供了哪些功能;它们可能比您必须将它们复制为客户端更快。

关于java - LinkedList.contains 执行速度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2804250/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com