Roaring64Bitmap实践

程序员文章站 2022-05-18 19:53:10

...

Roaring64Bitmap简介

数据结构及原理

RoaringBitmap针对Container的优化策略

maven依赖

测试一：优化前后，读写文本期间，序列化与反序列化的耗时

测试二：迭代还原出原来的数据耗时

测试三：测试contains, and, andNot, or方法

参考

Roaring64Bitmap简介

是bitmap的优化版，会根据插入的元素动态调整内存，不会出现因为数据少而占用大量内存的情况，并会做适当的压缩。

数据结构及原理

Roaring64Bitmap方法依赖于ART数据结构来保存键/值对。Key由最高48位元素组成，而值是16位Roaring容器
LongUtils类会将64位的长整形（long）拆分成高48位和低16位两部分来处理。

    public static byte[] highPart(long num) {
        byte[] high48 = new byte[]{(byte)((int)(num >>> 56 & 255L)), (byte)((int)(num >>> 48 & 255L)), (byte)((int)(num >>> 40 & 255L)), (byte)((int)(num >>> 32 & 255L)), (byte)((int)(num >>> 24 & 255L)), (byte)((int)(num >>> 16 & 255L))};
        return high48;
    }

    public static char lowPart(long num) {
        return (char)((int)num); // char 在java中是2个字节。java采用unicode，2个字节（16位）来表示一个字符
    }

三种Container

下面介绍到的是RoaringBitmap的核心，三种Container，Container只需要处理低16位的数据。

ArrayContainer

static final int DEFAULT_MAX_SIZE = 4096

short[] content;

结构很简单，只有一个short[] content，将16位value直接存储。

short[] content始终保持有序，方便使用二分查找，且不会存储重复数值。

因为这种Container存储数据没有任何压缩，因此只适合存储少量数据。

ArrayContainer占用的空间大小与存储的数据量为线性关系，每个short为2字节，因此存储了N个数据的ArrayContainer占用空间大致为2N字节。存储一个数据占用2字节，存储4096个数据占用8kb。

根据源码可以看出，常量DEFAULT_MAX_SIZE值为4096，当容量超过这个值的时候会将当前Container替换为BitmapContainer。

BitmapContainer

final long[] bitmap;

这种Container使用long[]存储位图数据。我们知道，每个Container处理16位整形的数据，也就是0~65535，因此根据位图的原理，需要65536个比特来存储数据，每个比特位用1来表示有，0来表示无。每个long有64位，因此需要1024个long来提供65536个比特。

因此，每个BitmapContainer在构建时就会初始化长度为1024的long[]。这就意味着，不管一个BitmapContainer中只存储了1个数据还是存储了65536个数据，占用的空间都是同样的8kb。

RunContainer

private short[] valueslength;

int nbrruns = 0;

RunContainer中的Run指的是行程长度压缩算法(Run Length Encoding)，对连续数据有比较好的压缩效果。

它的原理是，对于连续出现的数字，只记录初始数字和后续数量。即：

对于数列11，它会压缩为11,0；
对于数列11,12,13,14,15，它会压缩为11,4；
对于数列11,12,13,14,15,21,22，它会压缩为11,4,21,1；

源码中的short[] valueslength中存储的就是压缩后的数据。

这种压缩算法的性能和数据的连续性（紧凑性）关系极为密切，对于连续的100个short，它能从200字节压缩为4字节，但对于完全不连续的100个short，编码完之后反而会从200字节变为400字节。

如果要分析RunContainer的容量，我们可以做下面两种极端的假设：

最好情况，即只存在一个数据或只存在一串连续数字，那么只会存储2个short，占用4字节
最坏情况，0~65535的范围内填充所有的奇数位（或所有偶数位），需要存储65536个short，128kb

RoaringBitmap针对Container的优化策略

创建时：

创建包含单个值的Container时，选用ArrayContainer
创建包含一串连续值的Container时，比较ArrayContainer和RunContainer，选取空间占用较少的

转换：

针对ArrayContainer：

如果插入值后容量超过4096，则自动转换为BitmapContainer。因此正常使用的情况下不会出现容量超过4096的ArrayContainer。
调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。

针对BitmapContainer：

如果删除某值后容量低至4096，则会自动转换为ArrayContainer。因此正常使用的情况下不会出现容量小于4096的BitmapContainer。
调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。

针对RunContainer：

只有在调用runOptimize()方法才会发生转换，会分别和ArrayContainer、BitmapContainer比较空间占用大小，然后选择是否转换。

maven依赖

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

测试一：优化前后，读写文本期间，序列化与反序列化的耗时

import org.roaringbitmap.RoaringBitmap;
import org.roaringbitmap.longlong.Roaring64Bitmap;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;

public class SerializeToDiskExample {


    public static void main(String[] args) throws IOException {
        Roaring64Bitmap rb = new Roaring64Bitmap();
        for (long k = 0; k < 100000000; k++) {
            rb.add(k);
        }
        for (long k = 100000000; k < 300000000; k= k + 2) {
            rb.add(k);
        }
        long start = System.currentTimeMillis();
        String file1 = "D:\\工作\\bitmapwithoutruns.bin";
        try (DataOutputStream out = new DataOutputStream(new FileOutputStream(file1))) {
            rb.serialize(out);
        }
        System.out.println("序列化耗间：" + getCost(start) + "秒");
        start = System.currentTimeMillis();
        rb.runOptimize();
        System.out.println("优化压缩耗间：" + getCost(start) + "秒");
        start = System.currentTimeMillis();
        String file2 = "D:\\工作\\bitmapwithruns.bin";
        try (DataOutputStream out = new DataOutputStream(new FileOutputStream(file2))) {
            rb.serialize(out);
        }
        System.out.println("优化后，序列化耗间：" + getCost(start) + "秒");
        // verify
        Roaring64Bitmap rbtest = new Roaring64Bitmap();
        start = System.currentTimeMillis();
        try (DataInputStream in = new DataInputStream(new FileInputStream(file1))) {
            rbtest.deserialize(in);
        }
        System.out.println("读取文件，反序列化耗间：" + getCost(start) + "秒");
        start = System.currentTimeMillis();
        if(!rbtest.equals(rb)) throw new RuntimeException("bug!");
        try (DataInputStream in = new DataInputStream(new FileInputStream(file2))) {
            rbtest.deserialize(in);
        }
        System.out.println("优化后，读取文件，反序列化耗间：" + getCost(start) + "秒");
        if(!rbtest.equals(rb)) throw new RuntimeException("bug!");
        System.out.println("Serialized bitmaps to "+file1+" and "+file2);
    }

    public static long getCost(long start) {
        return (System.currentTimeMillis() - start) / 1000;
    }
}

测试结果：

序列化耗间：25秒
优化压缩耗间：0秒
优化后，序列化耗间：13秒
读取文件，反序列化耗间：7秒
优化后，读取文件，反序列化耗间：6秒

生成文件的大小如下图：
Roaring64Bitmap实践

测试二：迭代还原出原来的数据耗时

import org.roaringbitmap.longlong.LongIterator;
import org.roaringbitmap.longlong.Roaring64Bitmap;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;

public class SerializeToDiskExample {


    public static void main(String[] args) throws IOException {
        String file2 = "D:\\工作\\bitmapwithruns.bin";
        Roaring64Bitmap rbtest = new Roaring64Bitmap();
        try (DataInputStream in = new DataInputStream(new FileInputStream(file2))) {
            rbtest.deserialize(in);
        }
        long start = System.currentTimeMillis();
        int count = 0;
        // toArray方法只能处理数据个数不大于int最大值，否则会有问题
//        for (long number : rbtest.toArray()) {
//            count++;
//        }

        LongIterator it = rbtest.getLongIterator();
        long temp = 0L;
        while(it.hasNext()) {
           temp = it.next();
           count++;
        }
        System.out.println("迭代还原出原来的数据耗时：" +getCost(start) + "秒，数据个数为：" + count);
    }

    public static long getCost(long start) {
        return (System.currentTimeMillis() - start) / 1000;
    }
}

toArray方法代码如下：

public long[] toArray() {
        long cardinality = this.getLongCardinality();
        if (cardinality > 2147483647L) {
            throw new IllegalStateException("The cardinality does not fit in an array");
        } else {
            long[] array = new long[(int)cardinality];
            int pos = 0;

            for(LongIterator it = this.getLongIterator(); it.hasNext(); array[pos++] = it.next()) {
            }

            return array;
        }
    }

测试结果：

迭代还原出原来的数据耗时：6秒，数据个数为：200000000

测试三：测试contains, and, andNot, or方法

import org.roaringbitmap.longlong.LongIterator;
import org.roaringbitmap.longlong.Roaring64Bitmap;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;

public class SerializeToDiskExample {


    public static void main(String[] args) throws IOException {
        String file2 = "D:\\工作\\bitmapwithruns.bin";
        Roaring64Bitmap rbtest = new Roaring64Bitmap();
        try (DataInputStream in = new DataInputStream(new FileInputStream(file2))) {
            rbtest.deserialize(in);
        }
        long start = System.currentTimeMillis();
        System.out.println("contains耗时为O(1), 是否包含" + rbtest.contains(2L) + ", 耗时为：" + getCostMils(start) + "毫秒");
        Roaring64Bitmap rbAndNot = new Roaring64Bitmap();
        for (long k = 0; k < 100000000; k++) {
            rbAndNot.add(k);
        }

        start = System.currentTimeMillis();
        rbtest.andNot(rbAndNot);
        System.out.println("andNot方法的耗时为" + getCostMils(start) + "毫秒, 结果个数为：" + rbtest.getLongCardinality());

        Roaring64Bitmap rbOr = new Roaring64Bitmap();
        for (long k = 300000000; k < 400000000; k++) {
            rbOr.add(k);
        }
        rbtest.clear();
        try (DataInputStream in = new DataInputStream(new FileInputStream(file2))) {
            rbtest.deserialize(in);
        }

        start = System.currentTimeMillis();
        rbtest.or(rbOr);
        System.out.println("or方法的耗时为" + getCostMils(start) + "毫秒, 结果个数为：" + rbtest.getLongCardinality());

        rbtest.clear();
        try (DataInputStream in = new DataInputStream(new FileInputStream(file2))) {
            rbtest.deserialize(in);
        }

        Roaring64Bitmap rbAnd = new Roaring64Bitmap();
        for (long k = 300000000; k < 400000000; k++) {
            rbAnd.add(k);
        }

        start = System.currentTimeMillis();
        rbtest.and(rbAnd);
        System.out.println("and方法的耗时为" + getCostMils(start) + "毫秒, 结果个数为：" + rbtest.getLongCardinality());

    }

    public static long getCost(long start) {
        return (System.currentTimeMillis() - start) / 1000;
    }

    public static long getCostMils(long start) {
        return System.currentTimeMillis() - start;
    }

}

测试结果：

contains耗时为O(1), 是否包含true, 耗时为：1毫秒
andNot方法的耗时为18毫秒, 结果个数为：104055296
or方法的耗时为10毫秒, 结果个数为：300000000
and方法的耗时为2毫秒, 结果个数为：9093632

发现andNot 和 and方法得到的数据并不准确，进行Roaring64Bitmap和RoaringBitmap的对比测试

import org.roaringbitmap.RoaringBitmap;
import org.roaringbitmap.longlong.Roaring64Bitmap;
import java.io.IOException;

public class SerializeToDiskExample {


    public static void main(String[] args) throws IOException {

        Roaring64Bitmap rbAnd = new Roaring64Bitmap();
        for (long k = 10000; k < 20000; k++) {
            rbAnd.add(k);
        }

        Roaring64Bitmap rbAnd2 = new Roaring64Bitmap();
        for (long k = 15000; k < 20000; k++) {
            rbAnd2.add(k);
        }

        rbAnd.and(rbAnd2);
        System.out.println("roaring64Bitmap结果个数为：" + rbAnd.getLongCardinality());

        Roaring64Bitmap rbAnd3 = new Roaring64Bitmap();
        for (long k = 100000; k < 200000; k++) {
            rbAnd3.add(k);
        }

        Roaring64Bitmap rbAnd4 = new Roaring64Bitmap();
        for (long k = 150000; k < 200000; k++) {
            rbAnd4.add(k);
        }

        rbAnd3.and(rbAnd4);
        System.out.println("roaring64Bitmap结果个数为：" + rbAnd3.getLongCardinality());

        RoaringBitmap rbAnd5 = new RoaringBitmap();
        for (int k = 10000; k < 20000; k++) {
            rbAnd5.add(k);
        }

        RoaringBitmap rbAnd6 = new RoaringBitmap();
        for (int k = 15000; k < 20000; k++) {
            rbAnd6.add(k);
        }

        rbAnd5.and(rbAnd6);
        System.out.println("roaringBitmap结果个数为：" + rbAnd5.getLongCardinality());

        RoaringBitmap rbAnd7 = new RoaringBitmap();
        for (int k = 100000; k < 200000; k++) {
            rbAnd7.add(k);
        }

        RoaringBitmap rbAnd8 = new RoaringBitmap();
        for (int k = 150000; k < 200000; k++) {
            rbAnd8.add(k);
        }

        rbAnd7.and(rbAnd8);
        System.out.println("roaringBitmap结果个数为：" + rbAnd7.getLongCardinality());
    }
}

测试结果：

roaring64Bitmap结果个数为：5000
roaring64Bitmap结果个数为：68928
roaringBitmap结果个数为：5000
roaringBitmap结果个数为：50000

从结果中可以看出，Roaring64Bitmap的add方法并不可靠，已在github反馈这个问题，期待他们能够修复。

参考

github地址：https://github.com/RoaringBitmap/RoaringBitmap

算法介绍：https://cloud.tencent.com/developer/article/1136054

Roaring64Bitmap实践

Roaring64Bitmap简介

数据结构及原理

三种Container

ArrayContainer

BitmapContainer

RunContainer

RoaringBitmap针对Container的优化策略

maven依赖

测试一：优化前后，读写文本期间，序列化与反序列化的耗时

测试二：迭代还原出原来的数据耗时

测试三：测试contains, and, andNot, or方法

参考

深入学习TypeScript 、React、 Redux和Ant-Design的最佳实践

android 开发教程之日历项目实践(三)

android 开发教程之日历项目实践(一)

android 开发教程之日历项目实践(二)

Vue服务端渲染实践之Web应用首屏耗时最优化方案

mysql慢查询优化之从理论和实践说明limit的优点

Android 加载GIF图最佳实践方案

Android中AOP的应用实践之过滤重复点击

从长沙到南京，看“ACE交通引擎”落地实践的进程

人工智能赋能健康医疗:理论与实践、现实与挑战