大数组元素差异比较下的removeAll和Map效率对比

比眉伴天荒 2023-09-26 18:26 34阅读 0赞

考虑这样一个场景，对两个列表对象，`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` 性能较差。

1.  `removeAll` 方法中，先进行判空，然后调用 `batchRemove()` 方法

public boolean removeAll(Collection<?> c) {
            Objects.requireNonNull(c);
            return batchRemove(c, false);
        }
    复制代码

1.  `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;
        }
    复制代码

1.  `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;
        }
    复制代码

1.  至此，可以看到，按照平均每次遍历要进行 `list.size() / 2` 次计算，假设集合 A 的元素个数为 m，集合 B 的元素个数为 n，则两重 for 循环下，会执行 `m*n/2`次。对于两个千万量级的数组，将执行 100 亿次计算！！！

**由此给出一个结论，对于大数组元素差异比较，不建议使用 `removeAll`，可以借助 Map 实现。**