ArrayList去重常用的四种方式及性能对比(JMH性能分析)

x33g5p2x  于2022-02-14 转载在 Java  
字(4.0k)|赞(0)|评价(0)|浏览(738)

这里提供四种实用的ArrayList去重的方法,同时我会实用Oracle提供的性能测试工具JMH(Java Microbenchmark Harness,Java微基准测试套件)来测试一下这几种方法的性能。当然这里测试的是在系统性能充裕的情况下进行的,看一看谁更能压榨机器的性能。

当然,那种不常用的去重方式这里就不涉及了。

ArrayList去重常用方法

ArrayList去重常用方法分为四种,分别是 HashSet去重、LinkedHashSet去重、stream流单线程去重、stream流多线程去重。这里涉及到的数据结构先回顾一下:

ArrayList(有序不唯一):Object[],线程不安全,插入删除慢(数组移动),查询快(随机访问)。

HashSet(无序唯一):哈希表,基于HashMap实现,hashmap的key存储它的值。线程不安全。

LinkedHashSet(有序唯一):哈希表+链表(链表存储插入顺序),它是HashSet子类,内部只有构造函数。线程不安全。

HashSet & LinkedHashSet

// data
List<Integer> arrayList = new ArrayList<Integer>(){{add(3);add(2);add(4);add(2);add(3);add(5);add(4);add(5);}};
// HashSet去重
ArrayList<Integer> hashSetList = new ArrayList<>(new HashSet<>(arrayList));
// LinkedHashSet去重
ArrayList<Integer> linkedHashSetList = new ArrayList<>(new LinkedHashSet<>(arrayList));

打上断点查看一下数据

stream & parallelStream

List<Integer> arrayList = new ArrayList<Integer>(){{add(3);add(2);add(4);add(2);add(3);add(5);add(4);add(5);}};
// stream去重
List<Integer> streamList = arrayList.stream().distinct().collect(Collectors.toList());
// parallelStream去重
List<Integer> parallelStreamList = arrayList.parallelStream().distinct().collect(Collectors.toList());

打上断点查看数据

上面就是简单数据的去重操作方法。

JMH性能分析

使用 Oracle 官方提供的性能测试工具 JMH(Java Microbenchmark Harness,JAVA 微基准测试套件)来测试一下这 4种 去重方式的性能。

首先,我们先要引入 JMH 框架,在 pom.xml 文件中添加如下配置:

<!-- https://mvnrepository.com/artifact/org.openjdk.jmh/jmh-core -->
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-core</artifactId>
    <version>1.23</version>
</dependency>
<!-- https://mvnrepository.com/artifact/org.openjdk.jmh/jmh-generator-annprocess -->
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-generator-annprocess</artifactId>
    <version>1.23</version>
    <scope>provided</scope>
</dependency>

版本号我以及写好了,推荐使用最新版本。

下面编写测试代码,如下

@BenchmarkMode(Mode.AverageTime) // 测试完成时间
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热 2 轮,每次 1s
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)//测试 5 轮,每次 1s
@Fork(1) // fork 1 个线程
@State(Scope.Thread) // 每个测试线程一个实例
public class ArrayListDistinctTest {
    static List<Integer> arrayList = new ArrayList<Integer>(){{
        // 一共 2000000 条数据
        for (int i = 0; i < 1000000; i++) add(i);
        for (int i = 0; i < 1000000; i++) add(i);
    }};

    public static void main(String[] args) throws RunnerException {
        // 启动基准测试
        Options opt = new OptionsBuilder()
                .include(ArrayListDistinctTest.class.getSimpleName()) // 要导入的测试类
                .output("C:/Users/86177/Desktop/jmh-map.log") // 输出测试结果的文件
                .build();
        new Runner(opt).run(); // 执行测试
    }
    @Benchmark
    public void hashSet(){
        new ArrayList<>(new HashSet<>(arrayList));
    }

    @Benchmark
    public void linkedHashSet(){
        new ArrayList<>(new LinkedHashSet<>(arrayList));
    }

    @Benchmark
    public void stream(){
        arrayList.stream().distinct().collect(Collectors.toList());
    }

    @Benchmark
    public void parallelStream(){
        arrayList.parallelStream().distinct().collect(Collectors.toList());
    }
}

所有被添加了 @Benchmark 注解的方法都会被测试,执行main方法即可。而正如代码中所示,我测试了一共 2000000(两百万) 条数据,有一半是重复的。已经把测试文件打印到桌面,我这里就贴上性能对比那一块数据:

Benchmark                             Mode  Cnt          Score          Error  Units
ArrayListDistinctTest.hashSet         avgt    5   37251270.300 ± 10458771.326  ns/op
ArrayListDistinctTest.linkedHashSet   avgt    5   40382889.634 ± 11785155.916  ns/op
ArrayListDistinctTest.parallelStream  avgt    5  157258934.286 ± 34670245.903  ns/op
ArrayListDistinctTest.stream          avgt    5   38513055.914 ±  3839780.617  ns/op

其中 Units 为 ns/op 意思是执行完成时间(单位为纳秒),而 Score 列为平均执行时间, ± 符号表示误差。从以上结果可以看出,两个 Set 的性能相近,并且执行速度很快,接下来是 stream

注:以上结果基于测试环境:JDK 1.8 / Win10 16GB (2021H) / Idea 2022.3

结论

除了以上数据量比较大的情况外,我还测试了进1000的小数据量。HashSet和LinkedHashSet的性能还是非常让人满意的,而对于stream来说在数据量比较小的情况下性能并没有Set高(parallelStream性能不如stream,下面有简单分析)。建议使用HashSet和LinkedHashSet去重。

去重选择

基于以上,有ArrayList去重操作的时候,推荐使用LinkedHashSet。

去重操作说到底但还是基于集合的数据来说的,你看Set集合都不允许重复,当然是首先选它了。然后就是看一下需求,如HashSet去重后数据无序,LinkedHashSet去重后数据有序但是性能没有HashSet好。

Stream流选择的话有单线程的和多线程的流操作,这里的多线程操作流性能是要优于单线程操作的,需要判断一下当前操作有没有可能发生并发风险等。

注意一点:在计算机体系中,多线程操作未必一定优于多线程,单线程可能会优于多线程的原因通常是CPU切换操作线程造成的性能浪费,这当中会有一个线程休眠和线程唤醒操作。比如常用的Redis就设计成单线程。

相关文章

微信公众号

最新文章

更多