位映射对大数据排重与排序

利用位映射原理对大数据排重

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

 

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

            

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

 

java中一个 int 类型在内存中占4 byte。那么10亿个int类型数据共需要开辟10 ^ 9次方 *4 byte ≈ 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次方。当然，你也可以定义其他的映射关系，只是注意不要发生数组越界的情况。由于最大值可能是2^32,故用long接收。

long bitIndex = num + (1l << 31);

 

计算在转化为byte[]数组的索引，由于上面定义的bitIndex 索引是非负数，故无需引入位运算去符号。

 int index = (int) (bitIndex / 8); 

 

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

 int innerIndex = (int) (bitIndex % 8);

 

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

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

 

这样就解决了整个大数据读取排重的问题。

 

那么怎么将其读取出来呢？怎么对数据进行排序？

 

那就只需要按照byte[]数组进行一一对应到 int 类型数据上即可。

以下代码升序输出为例。

 

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

 

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

                }

            }

        } 

 }

 

 

由于编译软件默认设置的JVM内存是128—400M左右，测试此程序明显是不够的，所以需要调节一下分配给JVM的内存。否则，不管怎样运行，都会出现Exception in thread "main" java.lang.OutOfMemoryError: Java heap space...

 

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

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

    -Xms256M 
    -Xmx1024M 
  
    

 

 

源代码：

 

package com.MassSort20131103;

import java.util.Random;


/**
 * Created with IntelliJ IDEA.
 * User: YangKang
 * Date: 13-11-3
 * Time:上午11:32
 * To change this template use File | Settings | File Templates.
 */
public class BigDataSort {

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

    // 定义一个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数组
     * @param num 读取的数据
     * @return byte数组  dataBytes
     */
    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;
    }

    /**
     * 输出数组中的数据
     * @param bytes byte数组
     */
    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);
                }
            }
        }
    }
}

 

 

 

评论

9 楼 chenzehe 2013-11-06  

mark支持下

8 楼 什么世道 2013-11-06  

fourfireliu 写道

youtl 写道

将这么大的数据读到内存中，是不合理的。删除重复数据可以借鉴压缩的原理。
建一个对象{int first,int num},为了节约空间，用int[2]存储就行。然后用有序二叉树保存起来。比如[5,3]表示5,6,7三个数。
当你从文件中读出一个int，就在二叉树中查找是否存在当前数字，如果有的话就去掉，如果没有的话，再判断是否能跟上界以及下界压缩保存，不能的话，才需要将它存储起来。

它这个一样可以分段存文件最后考虑压缩 不见得非要2叉树

分段排序存文件可能是一个比较理想的方式，占用内存可以非常少。时间上全部读入内存可能快一点。在时间和空间上找个平衡吧。

7 楼 fourfireliu 2013-11-06  

youtl 写道

将这么大的数据读到内存中，是不合理的。删除重复数据可以借鉴压缩的原理。
建一个对象{int first,int num},为了节约空间，用int[2]存储就行。然后用有序二叉树保存起来。比如[5,3]表示5,6,7三个数。
当你从文件中读出一个int，就在二叉树中查找是否存在当前数字，如果有的话就去掉，如果没有的话，再判断是否能跟上界以及下界压缩保存，不能的话，才需要将它存储起来。

它这个一样可以分段存文件最后考虑压缩 不见得非要2叉树

6 楼 fourfireliu 2013-11-06  

我记得这是编程珠矶里的例子 不过lz把它用java实现了

5 楼 youtl 2013-11-06  

不好意思，没有代码。如果要保存在磁盘中，可以从树中读取，也就是说数据是根据树的结果去生成。
其实int[2]的压缩方式还是压缩率不够高的，如果是long类型的话，也不见得吃的消。如有必要还可以引入byte[2]数组之类的，沿着这条路进行下去，总有办法解决long的排序问题，只是代码估计就复杂了。但你用的方法，就只能解决int类型的。而且jvm内存占用也不低，jvm是没办法使用电脑所有内存的。
还有一个有效的方法，是对数字进行分段加载，将未处理的数字，用硬盘先存储起来。

4 楼 9344187 2013-11-06  

youtl 写道

将这么大的数据读到内存中，是不合理的。删除重复数据可以借鉴压缩的原理。
建一个对象{int first,int num},为了节约空间，用int[2]存储就行。然后用有序二叉树保存起来。比如[5,3]表示5,6,7三个数。
当你从文件中读出一个int，就在二叉树中查找是否存在当前数字，如果有的话就去掉，如果没有的话，再判断是否能跟上界以及下界压缩保存，不能的话，才需要将它存储起来。

请问采用二叉树的方式，怎样让数据保存在磁盘中呢？有相应的代码参考一下吗？

3 楼 zhangyan19870108 2013-11-05  

lz思路很好

2 楼 zhangyan19870108 2013-11-05  

1 楼 youtl 2013-11-05  

将这么大的数据读到内存中，是不合理的。删除重复数据可以借鉴压缩的原理。
建一个对象{int first,int num},为了节约空间，用int[2]存储就行。然后用有序二叉树保存起来。比如[5,3]表示5,6,7三个数。
当你从文件中读出一个int，就在二叉树中查找是否存在当前数字，如果有的话就去掉，如果没有的话，再判断是否能跟上界以及下界压缩保存，不能的话，才需要将它存储起来。