超大规模数据场景处理
在海量数据中,普通的数组、链表、Hash、树等等结构都无效了,因为内存空间放不下。而常规的递归、排序、回溯、贪心和动态规划等思想也无效了,因为执行都会超时,必须使用其他的方法。
以下是三种典型思路:
- 使用位存储,使用位存储最大的好处是占用的空间是简单存整数的1/8。例如一个40亿的整数数组,如果用整数存储需要16GB左右空间,而如果使用位存储,就可以只用0.5G空间。
- 如果文件实在太大,无法在内存中放下,则需要考虑将大文件分成若干小块,先处理每个块,最后再逐步得到想要的结果,这种方法也叫做外部排序。这样需要遍历全部序列至少两次,是典型的时间换空间的方法。
- 利用堆处理流数据。如果在超大数据中找第k大、第k小,k个最大、k个最小特别适合使用堆来处理。
以下用一个例子说明:
用4KB内存寻找重复元素
题目要求:给定一个数组,包含从1到N的整数,N最大为32000,数组可能还有重复值,且N的取值不定,若只有4KB的内存可用,该如何打印数组中所有重复元素。
分析:如果不管内存使用的要求,可以先创建要给大小为N的数组,然后将这些数据放进去,这题规定N最大为32000,如果全部存储到数组中,需要32000 * 4B = 128KB的空间,超过了题目的需求,所以得采取其他的方法来存放数据。
我们可以利用位图去存储超大数据。位图即比特数组,每一位对应一个整数,用32000位就能代表32000个整数,这样每个元素的大小由int大小变为bit大小。
利用位图,就可以遍历访问整个数组。如果发现数组元素是v,那么就将位置为v的位设置为1,碰到重复元素,就输出一下。
以下是代码示例:
public class FindDuplicatesIn32000 {
public void checkDuplicates(int[] array) {
BitSet bs = new BitSet(32000);
for (int i = 0; i < array.length; i++) {
int num = array[i];
int num0 = num - 1;
if (bs.get(num0)) {
System.out.println(num);
} else {
bs.set(num0);
}
}
}
class BitSet {
int[] bitset;
public BitSet(int size) {
this.bitset = new int[size >> 5];
}
boolean get(int pos) {
int wordNumber = (pos >> 5);
int bitNumber = (pos & 0x1F);
return (bitset[wordNumber] & (1 << bitNumber)) != 0;
}
void set(int pos) {
int wordNumber = (pos >> 5);
int bitNumber = (pos & 0x1F);
bitset[wordNumber] |= 1 << bitNumber;
}
}
}
初始化数组时,this.bitset = new int[size >> 5],这是做压缩处理,每32缩小为1个
set时,先获取pos除以32的整数部分得到pos位于数组的哪个索引上,再获取pos除以32的余数,得到pos的具体位置。
例如将34这个数往位图中存取,先34 >> 5 = 1,所以34是在bitset[1]上,然后34 & (11111) 等于 2 (00010),对应到bitset[1]中的第2位。所以如果遇到34,就将bitset[1]的第2位设置为1,表示34出现过。
bitset[0] 对应1-32,bitset[1] 对应33-64,以此类推,每一个bitset用32位表示32个int。