大數組元素差異removeAll與Map效率對比
正文
考慮這樣一個場景,對兩個列表對象,listA
和 listB
,比較二者差異,找出隻在 listA
中出現的元素列表 onlyListA
,找出隻在 listB
中出現的元素列表 onlyListB
。
removeAll實現
很容易想到借助 removeAll
實現,代碼如下。
List<String> listA = new ArrayList<>(); List<String> listB = new ArrayList<>(); //僅在數組A中出現的元素 List<String> onlyListA = new ArrayList<>(listA); onlyListA.removeAll(listB); //僅在數組B中出現的元素 List<String> onlyListB = new ArrayList<>(listB); onlyListB.removeAll(listA);
當數組元素較少時,借助 removeAll
實現並沒有任何問題。不過在數組元素較大時,removeAll
方法耗時會較大。執行如下測試方法,對數組元素個數為1000,1W,10W,100W 的場景進行測試。
public class ListDiffTest { public static void main(String[] args) { testRemoveAllCostTime(1000); testRemoveAllCostTime(10000); testRemoveAllCostTime(100000); testRemoveAllCostTime(1000000); } public static void testRemoveAllCostTime(int size) { List<String> listA = dataList(size); listA.add("onlyAElement"); List<String> listB = dataList(size + 3); long startTime = System.currentTimeMillis(); //僅在數組A中出現的元素 List<String> onlyListA = new ArrayList<>(listA); onlyListA.removeAll(listB); //僅在數組B中出現的元素 List<String> onlyListB = new ArrayList<>(listB); onlyListB.removeAll(listA); System.out.println("僅在集合A中出現的元素:" + onlyListA); System.out.println("僅在集合B中出現的元素:" + onlyListB); System.out.println("元素個數 = " + size + "時,比對耗時:" + (System.currentTimeMillis() - startTime) + " 毫秒"); } private static List<String> dataList(int size) { List<String> dataList = new ArrayList<>(); for (int i = 0; i < size; i++) { dataList.add("" + i); } return dataList; } }
測試結果如下
僅在集合A中出現的元素:[onlyAElement]
僅在集合B中出現的元素:[1000, 1001, 1002]
元素個數 = 1000時,比對耗時:19 毫秒
元素個數 = 10000時,比對耗時:299 毫秒 #1W
元素個數 = 100000時,比對耗時:24848 毫秒 #10W
元素個數 = 1000000時,比對耗時:3607607 毫秒 #100W 約60m
可以看到,當數組元素達到百萬級時,耗時將達60min上下。
借助Map實現
此處給出一種優化方式,借助 Map
計數,將 List 集合中的元素作為 Map 的 key,元素出現的次數作為 Map 的 value。代碼實現如下。
import io.vavr.Tuple2; public class ListDiffTest { public static void main(String[] args) { testDifferListByMapCostTime(1000); testDifferListByMapCostTime(10000); testDifferListByMapCostTime(100000); testDifferListByMapCostTime(1000000); } public static void testDifferListByMapCostTime(int size) { List<String> listA = dataList(size); listA.add("onlyAElement"); List<String> listB = dataList(size + 3); long startTime = System.currentTimeMillis(); //僅在數組A中出現的元素 List<String> onlyListA = tuple2._1;; //僅在數組B中出現的元素 List<String> onlyListB = tuple2._2; System.out.println("僅在集合A中出現的元素:" + onlyListA); System.out.println("僅在集合B中出現的元素:" + onlyListB); System.out.println("元素個數 = " + size + "時,比對耗時:" + (System.currentTimeMillis() - startTime) + " 毫秒"); } /** * 通過Map計數方式 比較兩個數組之間的差異 * * @param listA 數組A * @param listB 數組B * @param <E> 元素類型 * @return Tuple2對象 onlyAList-隻在數組A存在的元素 onlyBList-隻在數組B存在的元素 */ public static <E> Tuple2<List<E>, List<E>> getDiffListBtMapCompare(List<E> listA, List<E> listB) { ValidateUtils.validateNotNull(listA, "listA"); ValidateUtils.validateNotNull(listB, "listB"); List<E> onlyAList = new ArrayList<>(); List<E> onlyBList = new ArrayList<>(); if (CollectionUtils.isEmpty(listA)) { return Tuple.of(onlyAList, listB); } else if (CollectionUtils.isEmpty(listB)) { return Tuple.of(listA, onlyBList); } /** * listA中元素 初始化計數 = 1 * listB中元素 初始化計數 = -2 * 遍歷累加後 * 相同元素 計數 = 2 * 僅A中出現元素 計數 = 1 * 僅A中出現元素 計數 = -1 */ Map<E, Integer> countMap = new HashMap<>(Math.max(listA.size(), listB.size())); for (E eleA : listA) { countMap.put(eleA, 1); } for (E eleB : listB) { countMap.put(eleB, 1 + countMap.getOrDefault(eleB, -2)); } countMap.forEach((k, v) -> { //獲取不同元素集合 if (v == 1) { onlyAList.add(k); } else if (v == -1) { onlyBList.add(k); } }); return Tuple.of(onlyAList, onlyBList); } }
測試結果如下
僅在集合A中出現的元素:[onlyAElement]
僅在集合B中出現的元素:[1000, 1002, 1001]
元素個數 = 1000時,比對耗時:8 毫秒
元素個數 = 10000時,比對耗時:19 毫秒 #1W
元素個數 = 100000時,比對耗時:28 毫秒 #10W
元素個數 = 1000000時,比對耗時:96 毫秒 #100W
元素個數 = 10000000時,比對耗時:5320 毫秒 #1000W
removeAll耗時分析
最後,來分析下為什麼在大數組元素比較時,removeAll
性能較差。
removeAll
方法中,先進行判空,然後調用batchRemove()
方法
public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); }
batchRemove()
方法中,使用 for 循環對集合進行遍歷。第 1 層循環需要執行listA.size()
次。循環體中調用瞭contains()
方法來確定集合 B 是否含有該元素。
private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }
contains()
方法的實現如下,內部又調用瞭indexOf()
方法。indexOf()
方法內部又進行瞭一層 for 循環遍歷。
public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }
- 至此,可以看到,按照平均每次遍歷要進行
list.size() / 2
次計算,假設集合 A 的元素個數為 m,集合 B 的元素個數為 n,則兩重 for 循環下,會執行m*n/2
次。對於兩個千萬量級的數組,將執行 100 億次計算!!!
由此給出一個結論,對於大數組元素差異比較,不建議使用 removeAll
,可以借助 Map 實現。
參考 https://www.jb51.net/article/261737.htm
以上就是大數組元素差異removeAll與Map效率對比的詳細內容,更多關於removeAll Map效率對比的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- Java找出兩個大數據量List集合中的不同元素的方法總結
- 一篇文章帶你瞭解Java泛型的super和extends
- Java中ArrayList集合的常用方法大全
- 如何將Object類轉換為實體類
- 關於ArrayList的動態擴容機制解讀