温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

使用BitMap怎么实现大数据排序去重

发布时间:2021-06-21 16:51:59 来源:亿速云 阅读:387 作者:Leah 栏目:大数据

今天就跟大家聊聊有关使用BitMap怎么实现大数据排序去重,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。

1、问题 问题提出:

M(如10亿)个int整数,只有其中N个数重复出现过,读取到内存中并将重复的整数删除。

2、解决方案 问题分析:

我们肯定会先想到在计算机内存中开辟M个int整型数据数组,来one bye one读取M个int类型数组, 然后在一一比对数值,最后将重复数据的去掉。当然这在处理小规模数据是可行的。

我们考虑大数据的情况:例如在java语言下,对10亿个int类型数据排重。

java中一个int类型在内存中占4byte。那么10亿个int类型数据共需要开辟10^9次方*4byte≈4GB的连续内存空间。以32位操作系统电脑为例,最大支持内存为4G,可用内存更是小于4G。所以上述方法在处理大数据时根本行不通。

思维转化:

既然我们不能为所有 int 类型的数据开辟 int 类型数组,那么可以采取更小的数据类型来读取缓存 int 类型数据。考虑到计算机内部处理的数据都是 01 序列的bit,那么我们是否可以用 1bit 来表示一个 int 类型数据。

位映射的引出:

使用较小的数据类型指代较大的数据类型。如上所说的问题,我们可以用1个 bit 来对应一个int 整数。假如对应的 int 类型的数据存在,就将其对应的 bit 赋值为1,否则,赋值为0(boolean类型)。java中 int 范围为 -2^31 到 2^31-1. 那么所有可能的数值组成的长度为2^32. 对应的 bit 长度也为 2^32. 那么可以用这样处理之后只需要开辟2^32 bit = 2^29 byte = 512M 大小的 内存空间 。显然,这样处理就能满足要求了,虽然对内存的消耗也不太小。

问题解决方案:

首先定义如下图的int - byte 映射关系,当然,映射关系可以自定义。但前提要保证你的数组上下标不能越界。

但如上定义的bit[]数组显然在计算机中是不存在的,所我们需要将其转化为 java 中的一个基本数据类型存储。显然,byte[] 是最好的选择。

将其转化为byte[] 数组方案:

自定义的映射关系表,每个bit对应一个 int 数值,将 int 的最大值,最小值与数组的最大最小索引相对应。从上图可以看出来 int 数值与bit索引相差 2^31次方。当然,你也可以定义其他的映射关系,只是注意不要发生数组越界的情况。

bit[]索引:由于最大值可能是2^32,故用long接收: long bitIndex = num + (1l << 31);

byte[]索引: int index = (int) (bitIndex / 8); ,在字节byte[index]中的具体位置: int innerIndex = (int) (bitIndex % 8);

更新值: dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));

` import java.util.Random;

/**

  • 问题:M(如10亿)个int整数,只有其中N个数重复出现过,读取到内存中并将重复的整数删除。<br/>

  • 使用位映射来进行海量数据的去重排序,原先一个元素用一个int现在只用一个bit, 内存占比4*8bit:1bit=32:1<br/>

  • 亦可用java语言提供的BitSet,不过其指定bit index的参数为int类型,因此在此例中将输入数转为bit index时对于较大的数会越界<br><br/> */ public class BigDataSort {

    private static final int CAPACITY = 1_000_000;// 数据容量

    public static void main(String[] args) {

     testMyFullBitMap();


    }

    public static void testMyFullBitMap() { MyFullBitMap ms = new MyFullBitMap();

     byte[] bytes = null;
    
     Random random = new Random();
     long startTime = System.currentTimeMillis();
     for (int i = 0; i < CAPACITY; i++) {
         int num = random.nextInt();
         // System.out.println("读取了第 " + (i + 1) + "\t个数: " + num);
         bytes = ms.setBit(num);
     }
     long endTime = System.currentTimeMillis();
     System.out.printf("存入%d个数,用时%dms\n", CAPACITY, endTime - startTime);
    
     startTime = System.currentTimeMillis();
     ms.output(bytes);
     endTime = System.currentTimeMillis();
     System.out.printf("取出%d个数,用时%dms\n", CAPACITY, endTime - startTime);


    } }

class MyFullBitMap { // 定义一个byte数组表示所有的int数据,一bit对应一个,共2^32b=2^29B=512MB private byte[] dataBytes = new byte[1 << 29];

/**
 * 读取数据,并将对应数数据的 到对应的bit中,并返回byte数组
 * 
 * [@param](https://my.oschina.net/u/2303379) num
 *            读取的数据
 * [@return](https://my.oschina.net/u/556800) byte数组 dataBytes
 */
public byte[] setBit(int num) {

    long bitIndex = num + (1l << 31); // 获取num数据对应bit数组(虚拟)的索引
    int index = (int) (bitIndex / 8); // bit数组(虚拟)在byte数组中的索引
    int innerIndex = (int) (bitIndex % 8); // bitIndex 在byte[]数组索引index 中的具体位置

    // System.out.println("byte[" + index + "] 中的索引:" + innerIndex);

    dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));
    return dataBytes;
}

/**
 * 输出数组中的数据
 * 
 * [@param](https://my.oschina.net/u/2303379) bytes
 *            byte数组
 */
public void output(byte[] bytes) {
    int count = 0;
    for (int i = 0; i < bytes.length; i++) {
        for (int j = 0; j < 8; j++) {
            if (((bytes[i]) & (1 << j)) != 0) {
                count++;
                int number = (int) ((((long) i * 8 + j) - (1l << 31)));
                // System.out.println("取出的第 " + count + "\t个数: " + number);
            }
        }
    }
}

}`

  1. Bit-map应用之快速去重   2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。   首先,根据“内存空间不足以容纳这2.5亿个整数”我们可以快速的联想到Bit-map。下边关键的问题就是怎么设计我们的Bit-map来表示这2.5亿个数字的状态了。其实这个问题很简单,一个数字的状态只有三种,分别为不存在,只有一个,有重复。因此,我们只需要2bits就可以对一个数字的状态进行存储了,假设我们设定一个数字不存在为00,存在一次01,存在两次及其以上为11。那我们大概需要存储空间几十兆左右。   接下来的任务就是遍历一次这2.5亿个数字,如果对应的状态位为00,则将其变为01;如果对应的状态位为01,则将其变为11;如果为11,,对应的转态位保持不变。   最后,我们将状态位为01的进行统计,就得到了不重复的数字个数,时间复杂度为O(n)。 转自:https://www.cnblogs.com/yale/p/9307363.html

看完上述内容,你们对使用BitMap怎么实现大数据排序去重有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注亿速云行业资讯频道,感谢大家的支持。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI