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() 內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- java中LinkedList使用迭代器優化移除批量元素原理
- Java List的remove()方法踩坑
- Java集合中的fail-fast(快速失敗)機制詳解
- 為什麼在foreach循環中JAVA集合不能添加或刪除元素
- Java面試必備之ArrayList陷阱解析