存储超过内存大小的数据

　　问题是这样的：如何存储5亿个正整数，并对这些数据进行排重。
　　直接用一个长度为5亿的int型数组存起来？这显然是不可能的，让我们来计算一下：
　　一个int型数据占用4byte，5亿个正整数也就是1.6*10^10bit，约为16G，16G的数据全存在内存里，内存显然不够用。那么，如何才能缩小占用空间呢？
　　再回到问题上看看，问题要求对数据进行排重，在用int存储的情况下，这5亿个数据的范围也就是0-2^31，排重的结果不过就是0到2^31的每一个数值都最多只有一个数存在。约定用1表示有这个数，0表示没有这个数，如此一来就可以用一个bit来表示一个数了。
　　解决方法如下：建立一个长度为2^28的byte型数组，数组中每一个byte每一位的1或0就代表了数据的存在与否。
　　在这个题目中，可以认为，我们是从数据流中接收到5亿个数据的。每收到一个数据，就判断它在byte数组中是否存在，若不存在，这把代表这个数据的那一位由0改为1。

　　代码如下：

//创建一个长度为2^28的byte数组
	byte bytes[] = new byte[(int)Math.pow(2, 28)];
	int i;//表示数组的第几位
	int j;//表示一个byte数据的第几位
	int b;//bytes[i]无符号转化后的int数值
	int a;//bytes[i]的第j为数值
	
	/**
	 * 保存出输入流中读到的数据
	 * @param x	从输入流中获得的正整数
	 */
	public void paichong(int x){
			i = x/8;//一个byte可以存8个数
			j = x%8;
			this.isExist(x);//判断该数是否已经出现过
			if(a==0){//若没有出现过，这把这一位改为1
				if(j==7){//若为最高为，直接加2^7最高会变成1，但是其他位也会发生变化
					bytes[i] -= 2*bytes[i];
				}else bytes[i] += (int)Math.pow(2, j); 
			}
	}

	/**
	 * 判断x是否曾经出现过
	 * @param x
	 */
	private void isExist(int x) {
		b = bytes[i];
		if(bytes[i]<0){
			b = (int)(-bytes[i])+128;
		}else b = bytes[i];
		//类似四位数的位数获得方法
		a = b/(int)Math.pow(2, j)%(int)Math.pow(2, 7-j);
	}
　　}

评论

2 楼 lazyee 2013-10-27  

yfzsj 写道

byte bytes[] = new byte[(int)Math.pow(2, 28)]; 
这里就已经堆举出了啊。

不好意思，才看到……
堆举出是指？？

1 楼 yfzsj 2013-10-14  

byte bytes[] = new byte[(int)Math.pow(2, 28)]; 
这里就已经堆举出了啊。