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

前面一篇文章《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，不错.

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