大量整形数据排重问题分析

本文介绍如何给非常多的整形数据排重。

    首先我先解释一下排重的意思：
  排重就是给一串数有顺序的重新排列，并且去掉重复的数字。

　　我们知道java编程中一个整形数据为4个字节，最大整数为2^32-1，所以不同整数的个数最大就有2^32个（这里不考虑负数），从0~2^32-1，那么这样你可以算一下假设用一个整形数组来存储这些数那么它所占的内存是比较大的。可能大于java虚拟机所拥有的内存空间。那么我们是否能用比较小的空间来存储这些数据呢。
　　
　　
    想法思路

     一个整形数据有32位每个位为0或者1，那么我们要是用它他的每一个位来表示一个整形数据，那么我们可以将我们所需的空间，最大就能缩小为原来的1/32。那么怎么用位来表示不同的整数呢。我们可以这样来向，有一个整形数组。它的第一个元素是一个整形数据，那么这个整形数据我们就用来表示0到31这32个整数，要是整形数据对应的01串上某个位置为1那么这个位置代表的整数就表示存在，同理数组中的第二个元素就能表示32到63这32个整数，依次列推。比如：
　　 00000000 00000000 00000000 00000011 就表示30和31被存在这个整数中，因为01串的第30和31位为1，该01串对应的整数是3=1+2。

　　 按照上面的思路，那么我们要来存储所有不同的整数，就只要开一个2^27长度的int型数组。这样就可以降低所使用的内存空间的大小了。
　　
　　
　　 同样的要是我们开一个byte数组来存储整数那么一个byte为8个，可以用来存储8个整数。可以开一个2^29长度的byte数组来存储所有不同的整数。
　　
　　 下面以用byte数据来存储从小到大排列数据为例的源代码。

package M数排重;

import java.util.Random;

public class Test {
	   byte[] bytearray=new byte[100];;
	/**
	 * 主函数
	 * @author lixiongzhi
	 */
	public static void main(String[] args) {
		Test test=new Test();
		Random random=new Random();
		for(int i=0;i<20;i++){
			int n=random.nextInt(50);
			System.out.print(n+" ");
			test.setBit(n);
		}

		System.out.println();
		test.print(test.bytearray);
		
	}
	
	/**
	 * 2的n次方
	 * @param n
	 * @return
	 */
	private int N(int n){
		int result=1;
		for(int i=0;i<n;i++){
			result*=2;
		}
		return result;
	}
	/**
	 * 整数n对应的bit并设为1
	 */
	private void setBit(int n){
		//对应的byte数组下标
		int index=n/8;
		//byte[index]对应的第mod个bit
		int mod=n%8;
		//获取byte[index]转换成的01串
		String str=byteToString(bytearray[index]);
		//将str的第mod位设为1
		System.out.print(str+"  ");
		str=setCharat(str, mod);
		System.out.print(str+" ");
		byte newbyte=StringToByte(str);
		System.out.println(newbyte);
		bytearray[index]=newbyte;
	}
	/**
	 * 将一个01串转化成byte
	 */
	private byte StringToByte(String str){
		byte result=0;
		for(int i=0;i<8;i++){
			if(str.charAt(i)==(char)49){
				result+=N(7-i);
			}
			
		}
		return result;
	}
	/**
	 * 将一个byte转换成01串
	 * @return
	 */
	private String byteToString(byte n){
		String str="";
		for(int i=0;i<8;i++){
			str+=n%2;
			n/=2;
		}
		//将str倒序排
		String str2="";
		for(int i=7;i>=0;i--){
			str2+=str.charAt(i);
		}
		return str2;
	}
	//设置str第index+1位为1的函数
	private String setCharat(String str,int index){
		if(str.charAt(index)!="1".charAt(0)){
			String str2="";
			for(int i=0;i<str.length();i++){
				if(i==index){
					str2+=1;
				}else{
					str2+=str.charAt(i);
				}
			}
			return str2;
		}
		return str;
	}
	/**
	 * 排重后输出
	 * @param array
	 */
	private void print(byte array[]){
		for(int i=0;i<array.length;i++){
			if(array[i]!=0){
				for(int j=0;j<byteToString(array[i]).length();j++){
					if(byteToString(array[i]).charAt(j)==(char)(49)){
						int k=8*i+j;
						System.out.print(k+" ");
					}
				}
			}
		}
	}
}

看输出结果：
20 00000000  00001000 8
48 00000000  10000000 -128
17 00001000  01001000 72
11 00000000  00010000 16
38 00000000  00000010 2
11 00010000  00010000 16
8  00010000  10010000 -112
23 01001000  01001001 73
24 00000000  10000000 -128
27 -0000000  -0010000 16
3  00000000  00010000 16
16 01001001  11001001 -55
46 00000000  00000010 2
2  00010000  00110000 48
24 00010000  10010000 -112
8  1-1-0000  1-1-0000 -96
4  00110000  00111000 56
13 -1-00000  -1-00100 68
32 00000010  10000010 -126
0  00111000  10111000 -72

   排重后结果为：
3 9 13 18 20 22 24 26 33 35 37 46

   第一列01串代表从byte数组中取出的byte转换成的01串，第二列代表加入整数后变成的01串。如第一行 20 00000000 00001000 8  是从byte中取出的bytebytearray[20/8]这个byte转换成01串为00000000  存入20时第20%8位即第4+1位变成1 最后的8代表存入20后的01串再转换成的byte。

   很明显这样的运行结果并不符合我们上面的分析。

原因：　　
  当我们将8个01串转换成一个byte时出现了负数的情况。

上网查下：java byte是做为最小的数字来处理的，它的值域被定义为-128~127，也就是signed byte，它的最高位被用来代表正负了1代表负，0代表正这样我们的错误原因也就被找出来了。而上面按照我们的思路byte范围应该是在0~255才对。既然byte最大整数只能代表127，那么我们就用7个01串来表示就好，将上面程序略作修改即可。

package M数排重;

import java.util.Random;

public class Test {
	   byte[] bytearray=new byte[100];;
	/**
	 * 主函数
	 * @author lixiongzhi
	 */
	public static void main(String[] args) {
		Test test=new Test();
		Random random=new Random();
		for(int i=0;i<200;i++){
			int n=random.nextInt(50);
			System.out.print(n+" ");
			test.setBit(n);
		}

		System.out.println();
		test.print(test.bytearray);
		
	}
	
	/**
	 * 2的n次方
	 * @param n
	 * @return
	 */
	private int N(int n){
		int result=1;
		for(int i=0;i<n;i++){
			result*=2;
		}
		return result;
	}
	/**
	 * 整数n对应的bit并设为1
	 */
	private void setBit(int n){
		//对应的byte数组下标
		int index=n/7;
		//byte[index]对应的第mod个bit
		int mod=n%7;
		//获取byte[index]转换成的01串
		String str=byteToString(bytearray[index]);
		//将str的第mod位设为1
		System.out.print(str+"  ");
		str=setCharat(str, mod);
		System.out.print(str+" ");
		byte newbyte=StringToByte(str);
		System.out.println(newbyte);
		bytearray[index]=newbyte;
	}
	/**
	 * 将一个01串转化成byte
	 */
	private byte StringToByte(String str){
		byte result=0;
		for(int i=0;i<7;i++){
			if(str.charAt(i)==(char)49){
				result+=N(6-i);
			}
			
		}
		return result;
	}
	/**
	 * 将一个byte转换成01串
	 * @return
	 */
	private String byteToString(byte n){
		String str="";
		for(int i=0;i<7;i++){
			str+=n%2;
			n/=2;
		}
		//将str倒序排
		String str2="";
		for(int i=6;i>=0;i--){
			str2+=str.charAt(i);
		}
		return str2;
	}
	//设置str第index+1位为1的函数
	private String setCharat(String str,int index){
		if(str.charAt(index)!="1".charAt(0)){
			String str2="";
			for(int i=0;i<str.length();i++){
				if(i==index){
					str2+=1;
				}else{
					str2+=str.charAt(i);
				}
			}
			return str2;
		}
		return str;
	}
	/**
	 * 排重后输出
	 * @param array
	 */
	private void print(byte array[]){
		System.out.println("排重后结果为：");
		for(int i=0;i<array.length;i++){
			if(array[i]!=0){
				for(int j=0;j<byteToString(array[i]).length();j++){
					if(byteToString(array[i]).charAt(j)==(char)(49)){
						int k=7*i+j;
						System.out.print(k+" ");
					}
				}
			}
		}
	}
}

再看输出结果：
4  0000000  0000100 4
25 0000000  0000100 4
15 0000000  0100000 32
33 0000000  0000010 2
6  0000100  0000101 5
28 0000010  1000010 66
12 0000000  0000010 2
5  0000101  0000111 7
30 1000010  1010010 82
11 0000010  0000110 6
49 0000000  1000000 64
22 0000100  0100100 36
6  0000111  0000111 7
2  0000111  0010111 23
39 0000000  0000100 4
24 0100100  0101100 44
38 0000100  0001100 12
25 0101100  0101100 44
27 0101100  0101101 45
27 0101101  0101101 45

  排重后结果为：
2 4 5 6 11 12 15 22 24 25 27 28 30 33 38 39 49

  很明显结果是正确的。

  我们可以让随机数在0到49的范围内产生产生非常多比如1000个。这样可以比较明显的看出结果。
  也可猜测一下排后结果就是0到49.（这不是绝对的）

  下面是代码运行的结果：

  排重后结果为：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

  和我们的猜测一样。
因为在0到49随机产生1000个数，包含0到49所有的50个数据的可能性是非常大的。