位映射--解决大数据排序与排重问题

2020-12-12

字数统计: 1.7k字 | 阅读时长≈ 6分

位映射–解决大数据排序与排重问题

一、问题提出

M（比如有10亿）个int整数，只有其中N个数重复出现过，读取至内存中并将重复的整数删除。

二、问题分析

首先，我们肯定会想到在计算机内存中开辟M个int型数据数组，然后一个一个地读取M个int类型数组，然后一个一个进行比较其数值，最后将其重复的数据去掉。当然，这的确是一种方法，但是当M的值等于10亿时，像这么庞大的数据时，计算机是处理不过来的。

我们可以Java语言为例，在Java中一个int 类型在内存中占4 byte，那么10亿个int 类型的数据则需要开辟10亿 * 4byte 约等于 4GB的连续内存空间。如果我们的电脑是32位操作系统，最大支持内存为4G，但可用内存更是小于4G，所以，从这个理论层面上来讲，直接一个一个地去读取10亿个整型数据是不现实的，根本行不通的。但是，从现实层面来讲，我们知道我们的计算机的确能够去处理这10亿的数据排序与排重的，难道是我们的理论分析错了？？？其实不然，既然从现实的层面来讲，计算机是能够处理这10亿个数据的，说明计算机的内部肯定做了哪些变换，使得计算机面对这么庞大的数据集时能够很好的进行排序与排重的。

是的，在计算机内部的确做了一些转换，既然我们知道不能为所有的int 类型的数据开辟int 类型的数组，但是我们可以采用更小的数据类型来读取缓存的int 类型的数据。考虑到计算机内部处理的数据都是01序列的bit，那么我们就能够用1bit来表示一个int 类型的数据。这样就有了”位映射”这个概念，当我们用自己的电脑处理这么庞大的数据时，基本上都会采用这样的一种处理数据的思想，即将需要处理的数据转换为最小的处理单位bit来代替处理。

三、位映射的详细阐述

正如上述的问题分析，我们知道可以用一个bit来对应一个int整数。假如，在10亿个int类型数据中，每一个int类型的数据都使之对应位置的的bit赋值为1，比如，在这10亿个int类型的数据中，其中有个数的int值为98，则在bit的第98个位置标为1，以此类推，一一对应，如果存在两个或者多个98的这个数，则就能将其返回，实现排重的功能。

实现这样的一个一一映射的关系，就会发现我们只需要对应得bit长度为2的32次方，然后换算一下2的32次方bit等于2的29次方byte = 512M大小的内存空间，显然，通过这样的映射处理，再来对10亿个数据进行排序与排重就不是什么大问题了。下面是一张int - bit映射关系图。

但是，在Java语言，我们输入bit[] 数组时，代码是会报错的，因为在计算机中bit[] 数组是不存在的，所以我们将其转换为byte[] 数组，这是一个Java中的一个基本数据类型。

四、将int[] 数组转化为byte[] 数组方案

4.1 实现bit索引与int数值之间的映射关系

因为每一个bit对应一个int数值，一般习惯将映射关系设置为int的最大值、最小值与数组的最大最小索引相对应，如上图，int 数值与bit 索引相差2的31次方，故

1	long bitIndex = num + (1l << 31) //表示bit索引bitIndex与int数值num之间的关系，获取num数据对应bit数组的索引值

4.2 计算转化为byte[]数组的索引

由于上面定义的bitIndex索引是非负数，故就能够计算出byte数组的索引值

1	int index = (int)(bitIndex / 8); //获取int型的数值是属于byte数组中的哪一个组的

4.3 计算bitIndex在byte[]数组索引index中的具体位置

1	int innerIndex = (int)(bitIndex % 8); //获取在index中的具体位置

4.4 引入位运算将byte[] 数组索引index 的各个位按权值相加

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

五、读取byte[] 数组以及对其排序

5.1 读取byte[]数组

遍历数组，采取与之前映射关系的逆运算来还原数据

for(int i=0; i<bytes.length; i++){
  for(int j=0; j<8; j++){
    if(!(((bytes[i]) & (1 << j)) == 0)){
      int number = (int)((((long)i * 8 + j)-(1l << 31)));
    }
  }
}

5.2 完整源码

由于编译软件默认设置的JVM内存是128-400M左右，测试该程序是明显不够的，所以需要调节一下JVM的内存，否则，不管怎样运行，都会出现Exception in thread “main” java.lang.OutOfMemoryError: Java heap space…，但是现在的电脑都是64位的，因此该内存完全够用了，如果电脑还是32位的，则需要做以下的修改。

eclipse：选择run->run configuration->arguments,输入-Xms256M -Xmx1024M（-Xms代表jvm启动时分配的内存大小，-Xmx代表可最大分配多少内存）

Intellij IDEA：修改安装目录/IntelliJ IDEA 7.0/bin下idea.exe.vmoption文件 

    -Xms256M 
    -Xmx1024M

源码如下：

package com.company;

import java.util.Random;

public class BigDataSort {
    public static final  int CAPACITY = 1000; //数据的容量

    //定义一个byte数组缓存所有的数据
    private byte[] dataBytes = new byte[1 << 29];

    public static void main(String[] args) {
        BigDataSort ms = new BigDataSort();

        byte[] bytes = null;

        Random random =new Random();
        for(int i = 0; i < CAPACITY; i++){
            int num = random.nextInt();
            System.out.println("读取了第"+(i+1)+"\t个数"+num);
            bytes = ms.splitBigData(num);
        }
        System.out.println("");
        ms.output(bytes);
    }


    /*
    * 读取数据，并将对应数据对应到bit中，并返回byte数组中
    *
    * */

    private byte[] splitBigData(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;

    }


    /*
    * 输出数组中的数据
    *
    * */

    private 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);
                }
            }
        }
    }
}

本文作者： feng之锋
本文链接： http://example.com/2020/12/12/位映射-解决大数据排序与排重问题/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！