100亿个数字的位图法快速排序

JAVA herman 1378浏览 0评论
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

前面一篇文章《100亿个数字的大文件如何快速找出最小的值?》中的排序结果消耗的时间相对来说比位图法排序更长。本章主要为大家介绍一下位图法排序。

位图法定义

 位图法就是bitmap的缩写。所谓bitmap,就是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在STL中有一个bitset容器,其实就是位图法,引用bitset介绍:

A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1,true or false, …).The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.

数据结构

unsigned int bit[N];
在这个数组里面,可以存储 N * sizeof(int) * 8个数据,但是最大的数只能是N * sizeof(int)  * 8 – 1。假如,我们要存储的数据范围为0-15,则我们只需要使得N=1,这样就可以把数据存进去。如下图:

位图的数据结构

数据为【5,1,7,15,0,4,6,10】,则存入这个结构中的情况为

位图法排序

了解了上面的定义和数据结构。我们在看看Jon Bentley的《编程珠玑》,刚看完第一章,觉得老外写的东西就是要比国内的生动很多! 第一章是开篇,要说的事情是:要把问题描述清楚。为了说明白这个事情,作者举了一个实例:怎样给一个磁盘文件排序? 这个问题问的很模糊是不是? 其实这个问题正确清楚的描述如下:

输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=10,000,000。输入文件中没有重复的整数,没有其他数据与该整数相关联(这句话不知道是想说什么问题..)。

输出: 按升序排列这些数,并写入磁盘。

约束:有 1MB多(不超过2MB) 的内存空间可用,有充足的硬盘空间。

好了,根据上面的基础,我们来完成上一篇中的排序。相关代码如下:

private BitSet bits;
 
public void perform(
        String largeFileName,
        int total,
        String destLargeFileName,
        Castor<Integer> castor,
        int readerBufferSize,
        int writerBufferSize,
        boolean asc) throws IOException {
 
    System.out.println("BitmapSort Started.");
    long start = System.currentTimeMillis();
    bits = new BitSet(total);
    InputPart<Integer> largeIn = PartFactory.createCharBufferedInputPart(largeFileName, readerBufferSize);
    OutputPart<Integer> largeOut = PartFactory.createCharBufferedOutputPart(destLargeFileName, writerBufferSize);
    largeOut.delete();
 
    Integer data;
    int off = 0;
    try {
        while (true) {
            data = largeIn.read();
            if (data == null)
                break;
            int v = data;
            set(v);
            off++;
        }
        largeIn.close();
        int size = bits.size();
        System.out.println(String.format("lines : %d ,bits : %d", off, size));
 
        if(asc) {
            for (int i = 0; i < size; i++) {
                if (get(i)) {
                    largeOut.write(i);
                }
            }
        }else {
            for (int i = size - 1; i >= 0; i--) {
                if (get(i)) {
                    largeOut.write(i);
                }
            }
        }
 
        largeOut.close();
        long stop = System.currentTimeMillis();
        long elapsed = stop - start;
        System.out.println(String.format("BitmapSort Completed.elapsed : %dms",elapsed));
    }finally {
        largeIn.close();
        largeOut.close();
    }
}
 
private void set(int i) {
    bits.set(i);
}
 
private boolean get(int v) {
    return bits.get(v);
}

跑完整个100亿的文件,只需要190秒,3分来钟.
以核心内存4663M/32大小的空间跑出这么个结果,而且大量时间在用于I/O,不错.

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » 100亿个数字的位图法快速排序