大数组元素差异比较下的removeAll和Map效率对比
考虑这样一个场景，对两个列表对象，listA 和 listB，比较二者差异，找出只在 listA 中出现的元素列表 onlyListA，找出只在 listB 中出现的元素列表 onlyListB。removeAll实现
很容易想到借助 removeAll 实现，代码如下。List listA = new ArrayList<>(); List listB = new ArrayList<>(); //仅在数组A中出现的元素 List onlyListA = new ArrayList<>(listA); onlyListA.removeAll(listB); //仅在数组B中出现的元素 List 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 listA = dataList(size); listA.add(＂onlyAElement＂); List listB = dataList(size + 3); long startTime = System.currentTimeMillis(); //仅在数组A中出现的元素 List onlyListA = new ArrayList<>(listA); onlyListA.removeAll(listB); //仅在数组B中出现的元素 List 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 dataList(int size) { List 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 listA = dataList(size); listA.add(＂onlyAElement＂); List listB = dataList(size + 3); long startTime = System.currentTimeMillis(); //仅在数组A中出现的元素 List onlyListA = tuple2._1;; //仅在数组B中出现的元素 List 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 元素类型 * @return Tuple2对象 onlyAList-只在数组A存在的元素 onlyBList-只在数组B存在的元素 */ public static Tuple2, List> getDiffListBtMapCompare(List listA, List listB) { ValidateUtils.validateNotNull(listA, ＂listA＂); ValidateUtils.validateNotNull(listB, ＂listB＂); List onlyAList = new ArrayList<>(); List 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 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://juejin.cn/post/7208099962911752247
