0. Thanks
- 海量數(shù)據(jù)處理 - 10億個(gè)數(shù)中找出最大的10000個(gè)數(shù)（top K問(wèn)題）
- 從1億個(gè)數(shù)字中取出最大的100個(gè)數(shù)字- 位圖排序（空間換時(shí)間）
1. 概述
有這樣的一道題目教翩，給出一定范圍的1億個(gè)數(shù)據(jù)（N=<數(shù)據(jù)<=M）呛谜，要求給他從小到大排序
顯然這個(gè)涉及到超大數(shù)據(jù)的排序鳍徽。一般有兩個(gè)套路：一個(gè)用堆排序婶芭，一個(gè)是用位圖排序贪磺。這里說(shuō)
一下位圖排序赋朦。
2. 原理
位圖排序其實(shí)是用數(shù)據(jù)的下標(biāo)作映射到對(duì)應(yīng)的數(shù)據(jù)拧略。假如現(xiàn)在有一個(gè)待排序的數(shù)據(jù)：
int[] a = {4,7,2,5,3};
我們需要先知道這些數(shù)據(jù)的取值范圍芦岂，我們看到數(shù)據(jù)是<8，那么我們初始化8個(gè)bit位的數(shù)組：
并把他們初始化為零辑鲤。每一個(gè)bit位的取值是0盔腔，或者1。
然后把每一個(gè)的待排序的數(shù)字取出來(lái)月褥，根據(jù)數(shù)字的大小把bit數(shù)組的對(duì)應(yīng)下標(biāo)的bit置為1.
到最后會(huì)變成這樣：
然后弛随，我們從第0未bit開(kāi)始打印非0位的下標(biāo)，也就是:23457宁赤，也就排好序了舀透。
3. Java來(lái)實(shí)現(xiàn)一下
基本的數(shù)據(jù)類型是沒(méi)有bit，最小是byte决左，所以我們先實(shí)現(xiàn)一個(gè)bit數(shù)組這樣的一個(gè)數(shù)據(jù)結(jié)構(gòu)：
/**
* 這里愕够，先實(shí)現(xiàn)一個(gè)位數(shù)組的數(shù)據(jù)結(jié)構(gòu)
*/
public static class BitArr {
private int bitLength = 0;
private byte[] bytes;
public byte[] getBytes() {
return bytes;
}
/**
* 構(gòu)建多少位的位數(shù)組
* @param bitLength 位長(zhǎng)
*/
public BitArr(int bitLength) {
this.bitLength = bitLength;
bytes = new byte[(int) Math.ceil((double) bitLength/7)];
}
/**
* 標(biāo)記某一個(gè)位
* 設(shè)置為1
* @param position 位
*/
public void mark(int position) {
if (position>bitLength)
return;
int arrIndex = position/7;
int bitIndex = position%7;
bytes[arrIndex] |= (1 << (6-bitIndex));
}
public void cleanMark(int position) {
if (position>bitLength)
return;
int arrIndex = position/7;
int bitIndex = position%7;
bytes[arrIndex] &= ~(1 << (6-bitIndex));
}
public void printAllBit() {
for (byte aByte : bytes) {
System.out.print(BitArr.Byte2String(aByte));
}
System.out.println();
}
/**
* 打印除符號(hào)位的bit
* @param nByte
* @return
*/
private static String Byte2String(byte nByte){
StringBuilder nStr=new StringBuilder();
for(int i=6;i>=0;i--) {
int j=(int)nByte & (int)(Math.pow(2, (double)i));
if(j>0){
nStr.append("1");
}else {
nStr.append("0");
}
}
return nStr.toString();
}
}
再基于此實(shí)現(xiàn)算法：
public static int[] bitmapSort(int[] arr, int theMax) {
if (arr==null || arr.length==0)
return null;
BitArr bitArr = new BitArr(theMax+1);
for (int anArr : arr) {
bitArr.mark(anArr);
}
int[] result = new int[arr.length];
byte[] bytes = bitArr.getBytes();
int index = 0;
for (int i = 0; i < bytes.length; i++) {
for (int j = 0; j < 7; j++) {
byte temp = (byte) (1<<6-j);
byte b = (byte) (bytes[i] & temp);
if ( b == temp) {
result[index++] = i*7 + j;
}
}
}
return result;
}
來(lái)個(gè)驗(yàn)證：
public static void main(String[] args) {
int[] a = {4,7,2,5,14,3,8,12};
int[] end = bitmapSort(a, 14);
for (int x : end) {
System.out.print(x+",");
}
}
//輸出
2,3,4,5,7,8,12,14,
有幾個(gè)地方需要注意：
- java里面沒(méi)有無(wú)符號(hào)的類型走贪，所以我們只能用byte的前7位
上面寫的Java實(shí)現(xiàn)，其實(shí)還有幾個(gè)問(wèn)題：
- 如果我們一開(kāi)始并不知道惑芭，這堆待排序數(shù)據(jù)的取值范圍怎么辦坠狡？也許可以采取動(dòng)態(tài)擴(kuò)充數(shù)組
- 如果待排序的數(shù)據(jù)有小于0的數(shù)據(jù)呢？
4.總結(jié)
位圖算法遂跟，其需要一次遍歷整個(gè)數(shù)據(jù)逃沿，假如有N個(gè)數(shù)據(jù)，就只是需要遍歷N次幻锁，所以時(shí)間復(fù)雜度
是 O(N)凯亮。但是，其需要額外地開(kāi)辟內(nèi)存空間哄尔，有N個(gè)數(shù)據(jù)假消，就需要多開(kāi)辟N bit位的數(shù)據(jù)，
額外需要：N/8/1024/1024 MB 的空間岭接。假如是一億個(gè)數(shù)據(jù)富拗，那么大概要：11.92MB。
