Java List的remove()方法陷阱以及性能优化
Java List在进行remove()方法是通常容易踩坑,主要有一下几点
循环时:问题在于,删除某个元素后,因为删除元素后,后面的元素都往前移动了一位,而你的索引+1,所以实际访问的元素相对于删除的元素中间间隔了一位。
几种常见方法
1.使用for循环不进行额外处理时(错误)
//错误的方法 for(int i=0;i<list.size();i++) { if(list.get(i)%2==0) { list.remove(i); } }
2.使用foreach循环(错误)
for(Integer i:list) { if(i%2==0) { list.remove(i); } }
抛出异常:java.util.ConcurrentModificationException;
foreach的本质是使用迭代器实现,每次进入for (Integer i:list) 时,会调用ListItr.next()方法;
继而调用checkForComodification()方法, checkForComodification()方法对操作集合的次数进行了判断,如果当前对集合的操作次数与生成迭代器时不同,抛出异常
public E next() { checkForComodification(); if (!hasNext()) { throw new NoSuchElementException(); } lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } // checkForComodification()方法对集合遍历前被修改的次数与现在被修改的次数做出对比 final void checkForComodification() { if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
使用for循环,并且同时改变索引;(正确)
//正确 for(int i=0;i<list.size();i++) { if(list.get(i)%2==0) { list.remove(i); i--;//在元素被移除掉后,进行索引后移 } }
使用for循环,倒序进行;(正确)
//正确 for(int i=list.size()-1;i>=0;i--) { if(list.get(i)%2==0) { list.remove(i); } }
使用while循环,删除了元素,索引便不+1,在没删除元素时索引+1(正确)
//正确 int i=0; while(i<list.size()) { if(list.get(i)%2==0) { list.remove(i); }else { i++; } }
4.使用迭代器方法(正确,推荐)
只能使用迭代器的remove()方法,使用列表的remove()方法是错误的
//正确,并且推荐的方法 Iterator<Integer> itr = list.iterator(); while(itr.hasNext()) { if(itr.next()%2 ==0) itr.remove(); }
性能分析
下面来谈谈当数据量过大时候,需要删除的元素较多时,如何用迭代器进行性能的优化,对于ArrayList这几乎是致命的,从一个ArrayList中删除批量元素都是昂贵的时间复杂度为O(n²),那么接下来看看LinkeedList是否可行。LinkedList暴露了两个问题,一个:是每次的Get请求效率不高,而且,对于remove的调用同样低效,因为达到位置I的代价是昂贵的。
是每次的Get请求效率不高
需要先get元素,然后过滤元素。比较元素是否满足删除条件。
remove的调用同样低效
LinkedList的remove(index),方法是需要先遍历链表,先找到该index下的节点,再处理节点的前驱后继。
以上两个问题当遇到批量级别需要处理时时间复杂度直接上升到O(n²)
使用迭代器的方法删除元素
对于LinkedList,对该迭代器的remove()方法的调用只花费常数时间,因为在循环时该迭代器位于需要被删除的节点,因此是常数操作。对于一个ArrayList,即使该迭代器位于需要被删除的节点,其remove()方法依然是昂贵的,因为数组项必须移动。下面贴出示例代码以及运行结果
public class RemoveByIterator { public static void main(String[] args) { List<Integer> arrList1 = new ArrayList<>(); for(int i=0;i<100000;i++) { arrList1.add(i); } List<Integer> linList1 = new LinkedList<>(); for(int i=0;i<100000;i++) { linList1.add(i); } List<Integer> arrList2 = new ArrayList<>(); for(int i=0;i<100000;i++) { arrList2.add(i); } List<Integer> linList2 = new LinkedList<>(); for(int i=0;i<100000;i++) { linList2.add(i); } removeEvens(arrList1,"ArrayList"); removeEvens(linList1,"LinkedList"); removeEvensByIterator(arrList2,"ArrayList"); removeEvensByIterator(linList2,"LinkedList"); } public static void removeEvensByIterator(List<Integer> lst ,String name) {//利用迭代器remove偶数 long sTime = new Date().getTime(); Iterator<Integer> itr = lst.iterator(); while(itr.hasNext()) { if(itr.next()%2 ==0) itr.remove(); } System.out.println(name+"使用迭代器时间:"+(new Date().getTime()-sTime)+"毫秒"); } public static void removeEvens(List<Integer> list , String name) {//不使用迭代器remove偶数 long sTime = new Date().getTime(); int i=0; while(i<list.size()) { if(list.get(i)%2==0) { list.remove(i); }else { i++; } } System.out.println(name+"不使用迭代器的时间"+(new Date().getTime()-sTime)+"毫秒"); } }
原理 重点看一下LinkedList的迭代器
另一篇博客Iterator简介 LinkedList使用迭代器优化移除批量元素原理
调用方法:list.iterator();
重点看下remove方法
private class ListItr implements ListIterator<E> { //返回的节点 private Node<E> lastReturned; //下一个节点 private Node<E> next; //下一个节点索引 private int nextIndex; //修改次数 private int expectedModCount = modCount; ListItr(int index) { //根据传进来的数字设置next等属性,默认传0 next = (index == size) ? null : node(index); nextIndex = index; } //直接调用节点的后继指针 public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } //返回节点的前驱 public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } /** * 最重要的方法,在LinkedList中按一定规则移除大量元素时用这个方法 * 为什么会比list.remove效率高呢; */ public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } }
LinkedList 源码的remove(int index)的过程是
先逐一移动指针,再找到要移除的Node,最后再修改这个Node前驱后继等移除Node。如果有批量元素要按规则移除的话这么做时间复杂度O(n²)。但是使用迭代器是O(n)。
先看看list.remove(idnex)是怎么处理的
LinkedList是双向链表,这里示意图简单画个单链表
比如要移除链表中偶数元素,先循环调用get方法,指针逐渐后移获得元素,比如获得index = 1;指针后移两次才能获得元素。
当发现元素值为偶数是。使用idnex移除元素,如list.remove(1);链表先Node node(int index)返回该index下的元素,与get方法一样。然后再做前驱后继的修改。所以在remove之前相当于做了两次get请求。导致时间复杂度是O(n)。
继续移除下一个元素需要重新再走一遍链表(步骤忽略当index大于半数,链表倒序查找)
以上如果移除偶数指针做了6次移动。
删除2节点
get请求移动1次,remove(1)移动1次。
删除4节点
get请求移动2次,remove(2)移动2次。
迭代器的处理
迭代器的next指针执行一次一直向后移动的操作。一共只需要移动4次。当元素越多时这个差距会越明显。整体上移除批量元素是O(n),而使用list.remove(index)移除批量元素是O(n²)
到此这篇关于Java List的remove()方法陷阱以及性能优化的文章就介绍到这了,更多相关Java List的remove() 内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/wsdfym/article/details/90544839
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
Java8 实现stream将对象集合list中抽取属性集合转化为map或list
这篇文章主要介绍了Java8 实现stream将对象集合list中抽取属性集合转化为map或list的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-05- 这篇文章主要介绍了java8如何用Stream查List对象某属性是否有重复的操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-11
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了Java8处理List的双层循环问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-19
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了C# List 排序各种用法与比较的相关资料,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了使用list stream:任意对象List拼接字符串操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-09
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03