Java中大集合求交集的方法比较

2021-12-28 656

背景

项目中使用到List求交集，很容易想到collecion.retainAll()方法，但是在数据量比较大时，这个方法效率并不高。本文研究了几种常用的方法，以供大家参考。

方法

【首先】梳理下思路，List去重一般有几种方法。

『外层遍历+内层遍历』查找：

复杂度O(NM) ，一般使用contains()检查是否包含

『外层遍历+内层Hash』查找：

复杂度O(N)，一般将内层List转化为HashSet实现

『外层遍历+内层bitMap』查找：

复杂度O(N)，一般将内层List转化为字节映射实现

【其次】这里其实忽略了一个点，就是『单层遍历』中，检查 元素不包含 时，需要将这个元素移除（即remove方法）。remove时，也会导致性能问题。

这里面我们使用Java8中java.util.AbstractCollection#retainAll方法来验证下我们的思路。

// Java8 中 方法：java.util.AbstractCollection#retainAll
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<E> it = iterator();
    
    // 1. 外层遍历
    while (it.hasNext()) {
        
        // 2. 内层查找『是否包含』
        if (!c.contains(it.next())) {
        
            // 3. 不包含时，移除外层元素
            it.remove();
            modified = true;
        }
    }
    return modified;
}

这里用图总结下，求交集的流程：

实现

1.『外层遍历+内层遍历』查找：

java中常用2种遍历查找的List：ArrayList、LinkedList，在内外层中测试。

// 外层：ArrayList，内层：ArrayList
private void outArrayListInnerArrayList(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    ArrayList<Long> setA = new ArrayList<>(listA);
    ArrayList<Long> setB = new ArrayList<>(listB);
    setA.retainAll(setB);
    long end = System.currentTimeMillis();
    System.out.println("[ArrayList-ArrayList]RetainAll耗时：" + (end - begin));
}

// 外层：LinkedList，内层：ArrayList
private void outLinkedListInnerArrayList(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    LinkedList<Long> setA = new LinkedList<>(listA);
    ArrayList<Long> setB = new ArrayList<>(listB);
    setA.retainAll(setB);
    long end = System.currentTimeMillis();
    System.out.println("[LinkedList-ArrayList]RetainAll耗时：" + (end - begin));
}

// 外层：ArrayList，内层：LinkedList
private void outArrayListInnerLinkedList(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    LinkedList<Long> setA = new LinkedList<>(listA);
    ArrayList<Long> setB = new ArrayList<>(listB);
    setA.retainAll(setB);
    long end = System.currentTimeMillis();
    System.out.println("[LinkedList-ArrayList]RetainAll耗时：" + (end - begin));
}

// 外层：LinkedList，内层：LinkedList
private void outLinkedListInnerLinkedList(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    LinkedList<Long> setA = new LinkedList<>(listA);
    ArrayList<Long> setB = new ArrayList<>(listB);
    setA.retainAll(setB);
    long end = System.currentTimeMillis();
    System.out.println("[LinkedList-LinkedList]RetainAll耗时：" + (end - begin));
}

2.『外层遍历+内层Hash』查找：

java中常用HashSet，内层替换为HashSet查找。

// 外层：ArrayList，内层：HashSet
private void outArrayListInnerHashSet(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    ArrayList<Long> setA = new ArrayList<>(listA);
    HashSet<Long> setB = new HashSet<>(listB);
    setA.retainAll(setB);
    long end = System.currentTimeMillis();
    System.out.println("[ArrayList-HashSet]RetainAll耗时：" + (end - begin));
}

// 外层：LinkedList，内层：HashSet
private void outLinkedListInnerHashSet(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    LinkedList<Long> setA = new LinkedList<>(listA);
    HashSet<Long> setB = new HashSet<>(listB);
    setA.retainAll(setB);
    long end = System.currentTimeMillis();
    System.out.println("[LinkedList-HashSet]RetainAll耗时：" + (end - begin));
}

3.『外层遍历+内层bitMap』查找：

BitSet也称作BitMap，它是一种通用的快速数据结构，不幸的是它太费内存，所以通常我们使用压缩位图。RoaringBitmap是一种压缩位置，它提供更好的压缩效果，在某些情况下比其它压缩位图快好几百倍。

https://github.com/RoaringBitmap/RoaringBitmap

RoaringBitmap已经使用在很多知名的开源项目中：

Apache Spark
Apache Hive

Apache Tez
Apache Kylin

... ...

Roaringbitmap中在Long类型中，提供了2种实现Roaring64NavigableMap和Roaring64Bitmap。Roaring64NavigableMap基于红黑树实现，Roaring64Bitmap基于ART（The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases ）数据结构实现。

那么，外层使用ArrayList、LinkedList，内层使用Roaring64NavigableMap、Roaring64Bitmap。

// 外层：ArrayList，内层：Roaring64NavigableMap
private void outArrayListInnerRoaring64NavigableMap(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    ArrayList<Long> setA = new ArrayList<>(listA);
    Roaring64NavigableMap ansB = new Roaring64NavigableMap();
    listB.forEach(ansB::addLong);
    setA.removeIf(e -> !ansB.contains(e));
    long end = System.currentTimeMillis();
    System.out.println("[ArrayList-Roaring64NavigableMap]RetainAll耗时：" + (end - begin));
}

// 外层：LinkedList，内层：Roaring64NavigableMap
private void outLinkedListInnerRoaring64NavigableMap(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    LinkedList<Long> setA = new LinkedList<>(listA);
    Roaring64NavigableMap ansB = new Roaring64NavigableMap();
    listB.forEach(ansB::addLong);
    setA.removeIf(e -> !ansB.contains(e));
    long end = System.currentTimeMillis();
    System.out.println("[LinkedList-Roaring64NavigableMap]RetainAll耗时：" + (end - begin));
}


// 外层：ArrayList，内层：Roaring64Bitmap
private void outArrayListInnerRoaring64Bitmap(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    ArrayList<Long> setA = new ArrayList<>(listA);
    Roaring64NavigableMap ansB = new Roaring64NavigableMap();
    listB.forEach(ansB::addLong);
    setA.removeIf(e -> !ansB.contains(e));
    long end = System.currentTimeMillis();
    System.out.println("[ArrayList-Roaring64Bitmap]RetainAll耗时：" + (end - begin));
}

// 外层：LinkedList，内层：Roaring64Bitmap
private void outLinkedListInnerRoaring64Bitmap(List<Long> listA, List<Long> listB) {
    long begin = System.currentTimeMillis();
    LinkedList<Long> setA = new LinkedList<>(listA);
    Roaring64Bitmap ansB = new Roaring64Bitmap();
    listB.forEach(ansB::addLong);
    setA.removeIf(e -> !ansB.contains(e));
    long end = System.currentTimeMillis();
    System.out.println("[LinkedList-Roaring64Bitmap]RetainAll耗时：" + (end - begin));
}

测试结果

使用Mac Pro 2021 M1 + JDK8测试，100万级的数据太慢，实行中没有太大参考意义，有兴趣可以自行测试。

说明：由于受数据，以及电脑本身负载影响，测试结果可能不一致，仅做量级参考。

	查找方法（外层-内层）	1万(毫秒)	10万(毫秒)	20万(毫秒)	50万(毫秒)
『外层遍历+内层遍历』查找	ArrayList-ArrayList	67	5502	26280	264133
	LinkedList-ArrayList	63	5418	27961	272362
	LinkedList-ArrayList	57	5436	21330	260976
	LinkedList-LinkedList	59	5153	23251	252472
『外层遍历+内层Hash』查找	ArrayList-HashSet	8	46	75	102
『外层遍历+内层Hash』查找	LinkedList-HashSet	8	17	49	82
『外层遍历+内层bitMap』查找	ArrayList-Roaring64NavigableMap	91	265	719	876
	LinkedList-Roaring64NavigableMap	26	125	562	876
	ArrayList-Roaring64Bitmap	20	78	572	801
	LinkedList-Roaring64Bitmap	119	171	221	384

附录

pom.xml

<dependency>
  <groupId>org.roaringbitmap</groupId>
  <artifactId>RoaringBitmap</artifactId>
  <version>0.9.23</version>
</dependency>

完整测试代码

import org.apache.commons.lang.math.RandomUtils;
import org.junit.Test;
import org.roaringbitmap.longlong.Roaring64Bitmap;
import org.roaringbitmap.longlong.Roaring64NavigableMap;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class SetOperation {

    /**
     * 集合的运算方法用时测试
     */
    @Test
    public void setOperation() {
        int size = 50_0000;
        List<Long> listA = new ArrayList<>(size);
        List<Long> listB = new ArrayList<>(size);

        initData(size, listA, listB);

        //『外层遍历+内层遍历』查找
        System.out.println("1. 『外层遍历+内层遍历』查找");
        outArrayListInnerArrayList(new ArrayList<>(listA), new ArrayList<>(listB));
        outLinkedListInnerArrayList(new ArrayList<>(listA), new ArrayList<>(listB));
        outArrayListInnerLinkedList(new ArrayList<>(listA), new ArrayList<>(listB));
        outLinkedListInnerLinkedList(new ArrayList<>(listA), new ArrayList<>(listB));

        //『外层遍历+内层Hash』查找：
        System.out.println("2.『外层遍历+内层Hash』查找：");
        outArrayListInnerHashSet(new ArrayList<>(listA), new ArrayList<>(listB));
        outLinkedListInnerHashSet(new ArrayList<>(listA), new ArrayList<>(listB));

        //『外层遍历+内层bitMap』查找
        System.out.println("3.『外层遍历+内层bitMap』查找");
        outArrayListInnerRoaring64NavigableMap(new ArrayList<>(listA), new ArrayList<>(listB));
        outLinkedListInnerRoaring64NavigableMap(new ArrayList<>(listA), new ArrayList<>(listB));
        outArrayListInnerRoaring64Bitmap(new ArrayList<>(listA), new ArrayList<>(listB));
        outLinkedListInnerRoaring64Bitmap(new ArrayList<>(listA), new ArrayList<>(listB));
    }

    // 外层：ArrayList，内层：ArrayList
    private void outArrayListInnerArrayList(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        ArrayList<Long> setA = new ArrayList<>(listA);
        ArrayList<Long> setB = new ArrayList<>(listB);
        setA.retainAll(setB);
        long end = System.currentTimeMillis();
        System.out.println("[ArrayList-ArrayList]RetainAll耗时：" + (end - begin));
    }

    // 外层：LinkedList，内层：ArrayList
    private void outLinkedListInnerArrayList(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        LinkedList<Long> setA = new LinkedList<>(listA);
        ArrayList<Long> setB = new ArrayList<>(listB);
        setA.retainAll(setB);
        long end = System.currentTimeMillis();
        System.out.println("[LinkedList-ArrayList]RetainAll耗时：" + (end - begin));
    }

    // 外层：ArrayList，内层：LinkedList
    private void outArrayListInnerLinkedList(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        LinkedList<Long> setA = new LinkedList<>(listA);
        ArrayList<Long> setB = new ArrayList<>(listB);
        setA.retainAll(setB);
        long end = System.currentTimeMillis();
        System.out.println("[LinkedList-ArrayList]RetainAll耗时：" + (end - begin));
    }

    // 外层：LinkedList，内层：LinkedList
    private void outLinkedListInnerLinkedList(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        LinkedList<Long> setA = new LinkedList<>(listA);
        ArrayList<Long> setB = new ArrayList<>(listB);
        setA.retainAll(setB);
        long end = System.currentTimeMillis();
        System.out.println("[LinkedList-LinkedList]RetainAll耗时：" + (end - begin));
    }

    // 外层：ArrayList，内层：HashSet
    private void outArrayListInnerHashSet(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        ArrayList<Long> setA = new ArrayList<>(listA);
        HashSet<Long> setB = new HashSet<>(listB);
        setA.retainAll(setB);
        long end = System.currentTimeMillis();
        System.out.println("[ArrayList-HashSet]RetainAll耗时：" + (end - begin));
    }

    // 外层：LinkedList，内层：HashSet
    private void outLinkedListInnerHashSet(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        LinkedList<Long> setA = new LinkedList<>(listA);
        HashSet<Long> setB = new HashSet<>(listB);
        setA.retainAll(setB);
        long end = System.currentTimeMillis();
        System.out.println("[LinkedList-HashSet]RetainAll耗时：" + (end - begin));
    }


    // 外层：ArrayList，内层：Roaring64NavigableMap
    private void outArrayListInnerRoaring64NavigableMap(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        ArrayList<Long> setA = new ArrayList<>(listA);
        Roaring64NavigableMap ansB = new Roaring64NavigableMap();
        listB.forEach(ansB::addLong);
        setA.removeIf(e -> !ansB.contains(e));
        long end = System.currentTimeMillis();
        System.out.println("[ArrayList-Roaring64NavigableMap]RetainAll耗时：" + (end - begin));
    }

    // 外层：LinkedList，内层：Roaring64NavigableMap
    private void outLinkedListInnerRoaring64NavigableMap(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        LinkedList<Long> setA = new LinkedList<>(listA);
        Roaring64NavigableMap ansB = new Roaring64NavigableMap();
        listB.forEach(ansB::addLong);
        setA.removeIf(e -> !ansB.contains(e));
        long end = System.currentTimeMillis();
        System.out.println("[LinkedList-Roaring64NavigableMap]RetainAll耗时：" + (end - begin));
    }


    // 外层：ArrayList，内层：Roaring64Bitmap
    private void outArrayListInnerRoaring64Bitmap(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        ArrayList<Long> setA = new ArrayList<>(listA);
        Roaring64NavigableMap ansB = new Roaring64NavigableMap();
        listB.forEach(ansB::addLong);
        setA.removeIf(e -> !ansB.contains(e));
        long end = System.currentTimeMillis();
        System.out.println("[ArrayList-Roaring64Bitmap]RetainAll耗时：" + (end - begin));
    }

    // 外层：LinkedList，内层：Roaring64Bitmap
    private void outLinkedListInnerRoaring64Bitmap(List<Long> listA, List<Long> listB) {
        long begin = System.currentTimeMillis();
        LinkedList<Long> setA = new LinkedList<>(listA);
        Roaring64Bitmap ansB = new Roaring64Bitmap();
        listB.forEach(ansB::addLong);
        setA.removeIf(e -> !ansB.contains(e));
        long end = System.currentTimeMillis();
        System.out.println("[LinkedList-Roaring64Bitmap]RetainAll耗时：" + (end - begin));
    }

    private void initData(int size, List<Long> listA, List<Long> listB) {
        Random random = new Random();
        Random random2 = new Random();
        random.longs(size).forEach(e -> {
            listA.add(e);
            if (random2.nextFloat() > 0.5) {
                listB.add(e);
            } else {
                listB.add(RandomUtils.nextLong());
            }
        });
    }
}

微信关注我们

原文链接：https://my.oschina.net/cimu/blog/5382401

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

v01.02 百图画鸿蒙(双向链表) | 画出内核最重要结构体 | 一图一主干

2021-12-28

644

作者：adamzhoul，OpenYurt 成员打开 openYurt 的 README.md，在简单介绍之后就是 Getting started: yurtctl convert --provider [minikube|kubeadm|kind] // To convert an existing Kubernetes cluster to an OpenYurt cluster yurtctl revert // To uninstall and revert back to the original cluster settings 简单一行命令就可体验 OpenYurt 了，感觉非常方便。稍等！为什么是 convert/revert 而不是 install/uninstall ? 这个命令对集群做了什么？看来，在执行它之前有必要搞清楚它到底做了什么。 yurtctl convert 到底做了些什么？核心流程跟随 openYurt 源代码（详情请见文末相关链接），梳理了 convert 的核心流程：可见 1、2 并没有什么特别，只是常规的服务部署。 3，则是对原有 ...

2021-12-28

470

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。