大数组元素差异removeAll与Map效率源码对比分析

本文小编为大家详细介绍“大数组元素差异removeAll与Map效率源码对比分析”，内容详细，步骤清晰，细节处理妥当，希望这篇“大数组元素差异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) + " 毫秒");     }        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);        }                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 实现。

读到这里，这篇“大数组元素差异removeAll与Map效率源码对比分析”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注编程网行业资讯频道。