最近两周学习研究了有关大数据的解决办法，下面就M个int（数据量很大，大于内存）排重进行浅层分析。做这种大数据的问题，我们要真正的动脑筋去想解决办法，在可行的条件下最好自己去实践一下，否则也只能是纸上谈兵。
对几亿个int型数据进行排重，我们的电脑内存空间都是有限的【以1G内存为例，我们最多存2^30B，也就是是2^28个int（1GB=1024MB，1MB=1024KB，1KB=1024B）】想要把数据都装入数组中，那显然是装不下的~~那么怎么样才可行呢？
下面分析一下解决办法：
方法一：
将大数据分为若干部分，在每个小部分里面先进行一次排序（从大到小），每次从每个部分中取出各自最大的那个，再在其中选出最大存入文件，在拿若干个数据进行比较，选出第二大的，若与前一个元素相同，则舍去，不同则写入文件。这样依次进行下去，遍历完所有的数据也就完成了排重的工作。
但是这个方法需要扫描数据两遍，比较费事，在时间花销上应该是很大的。
那么有没有其他更好的方法呢？
方法二：
1个int—>4个Byte—>32个bit
试想想，我们可不可以在1个int里存入32个数据的相关信息呢？这样的话，是不是将占用的内存降低到1/32了呢？
将一个int表示为32位的01字符串，如果对应位置的数据存在就把bit设为1，不存在就为0。
假设有数据“5”，那么就把第5个位置的0改成1
将01串转换成int存入数组里就可以了
下面看一下我写的方法，比较简单
package Eliminate;
/**
* 一组int很多，排重
* @author Administrator
* 最多有2^32(2147483647])个int数字，用一个bit来表示，最多用2^27大小的数组来表示
*/
public class Eliminate {
/**
* 将一个32位的字符串转成一个整数
*
* @param s
* @return
*/
public int stringTOint(String s) {
int a=(int) (((int) s.charAt(0) - 48) * (2147483647+1));
int b=(int)((int) s.charAt(1) - 48) * 1073741824 + ((int) s.charAt(2) - 48)* 536870912
+ ((int) s.charAt(3) - 48) * 268435456+ ((int) s.charAt(4) - 48) * 134217728
+ ((int) s.charAt(5) - 48) * 67108864 + ((int) s.charAt(6) - 48) * 33554432
+ ((int) s.charAt(7) - 48) * 16777216 + ((int) s.charAt(8) - 48) * 8388608;
int c=(int)((int) s.charAt(9) - 48) * 4194304 + ((int) s.charAt(10) - 48)*2097152
+ ((int) s.charAt(11) - 48) * 1048576 + ((int) s.charAt(12) - 48)*524288
+ ((int) s.charAt(13) - 48) * 262144+ ((int) s.charAt(14) - 48) * 131072
+ ((int) s.charAt(15) - 48) * 65536 + ((int) s.charAt(16) - 48) * 32768
+ ((int) s.charAt(17) - 48)*16384+ ((int) s.charAt(18) - 48) * 8192
+ ((int) s.charAt(19) - 48)*4096 + ((int) s.charAt(20) - 48) * 2048
+ ((int) s.charAt(21) - 48) * 1024 + ((int) s.charAt(22) - 48) * 512
+ ((int) s.charAt(23) - 48) * 256 + ((int) s.charAt(24) - 48)* 128
+ ((int) s.charAt(25) - 48) * 64 + ((int) s.charAt(26) - 48)* 32
+ ((int) s.charAt(27) - 48) * 16+ ((int) s.charAt(28) - 48) * 8
+ ((int) s.charAt(29) - 48) * 4+ ((int) s.charAt(30) - 48) * 2
+ ((int) s.charAt(31) - 48);
return a+b+c;
}
/**
* 将int型转化为32位的bit
*/
public String intTOstring(int index){
String str=Integer.toBinaryString(index);
int strlength=str.length();
if(strlength<32){
for(int i=0;i<32-strlength;i++){
str="0"+str;
}
}
return str;
}
/**
* 打印最终排重结果输出
* @param args
*/
public void print(int src[]){
int number;
int count=0;
//将src数组中的数据还原成01字符串，找出相应位置的下标
//循环src数组
for(int i=1;i<src.length;i++){
String s=intTOstring(src[i]);
System.out.println(s);
for(int j=0;j<s.length();j++){
if(s.charAt(j)=='1'){
number=(i-1)*32+j;
count++;
System.out.print(number+" ");
}
}
System.out.println();
}
System.out.println("排重后的数据有"+count+"个");
}
}
测试代码：
package Eliminate;
import java.util.Random;
public class Test {
private static int SrcSize=80000;//最多用2^27大小的数组来表示
private static int M =1000000;//数据量
private static int [] src=new int [SrcSize];
private static Random r=new Random();
/**
* 主函数
* @param args
*/
public static void main(String args[]){
Long BeginTime=System.currentTimeMillis();
Eliminate e=new Eliminate();
int temp;//随机数
int number;//商
int index;//数组下标
int mod;//余数
int x;
for(int i=0;i<M;i++){
temp=r.nextInt(2000000);
System.out.print(temp+" ");
System.out.println();
number=temp/32;//取商
index=number+1;
mod=temp%32;//取余
//将int型转化为32位的bit
String str=e.intTOstring(src[index]);
//修改mod处的bit值
String newStr=new String();
for(int j=0;j<32;j++){
char c=str.charAt(j);
if(j==mod){
newStr=newStr+1;
}else{
newStr=newStr+c;
}
}
//将修改后的字符串转化为int，放回数组
x=e.stringTOint(newStr);
src[index]=x;
}
e.print(src);
Long EndTime=System.currentTimeMillis();
System.out.println("排重时间为："+(EndTime-BeginTime));
}
}
由于时间问题，没有对很庞大的数据进行测试。这里的数据量为100万，数组大小为8万
测试结果：
排重后的数据有786678个
排重时间为：9344
个人认为排重速度还是不错的~~是不是很有效哟~~
下面进行了一个小数据的测试，证明方法的有效和正确性：
测试结果：
随机产生数据50个：
83 62 85 29 98 21 22 36 84 13 50 33 90 39 17 26 90 52 15 56 54 85 19 48 75 46 93 36 52 14 8 44 68 36 24 22 63 30 54 18 28 95 92 98 92 67 36 49 63 51
00000000100001110111011010101110
8 13 14 15 17 18 19 21 22 24 26 28 29 30
01001001000010101111101010000011
33 36 39 44 46 48 49 50 51 52 54 56 62 63
00011000000100000001110000101101
67 68 75 83 84 85 90 92 93 95
00100000000000000000000000000000
98
排重后的数据有39个
排重时间为：15
以上就是M个int（数据量很大，大于内存）排重的分析及解决方案，大数据问题还有很多很多，还需要进一步的分析研究~~应该会很有趣哟~~
分享到：
相关推荐
- 要求将这个序列分割为 m 个连续的子序列（每段子序列中的数在原序列中必须连续排列）。 - 目标是最小化这些子序列的和的最大值。 #### 输入输出格式 **输入**: - 第一行包含两个整数 n 和 m，分别表示序列的长度...
- **排列**：是指从n个不同元素中任取m（m≤n）个元素按照一定的顺序排成一列。 - **组合**：是指从n个不同元素中任取m（m≤n）个元素并成一组，不考虑其顺序。 - **重复**：允许同一元素多次出现在排列或组合中。 -...
但是，分支定界法在已经排好序的序列中查找，因此查找到的第一个解即为最优解，理论上来说，时间效率会高于回溯法。 回溯法代码 以下是回溯法的代码实现： ```cpp #include #include #include #include #...
- `int *m`: 指向数组最后一个元素的指针。 #### 循环逻辑分析 ```c for(; p ; p++, m--) { t = *p; *p = *m; *m = t; } ``` 该循环执行过程如下： 1. 初始化时，`p`指向数组起始位置，`n`指向数组中间位置，`m`...
int f(int m, int n) { if (m ) return 0; if (n == 0) return 1; return f(m, n - 1) + f(m - 1, n); } ``` **时间复杂度分析**： 递归解法的时间复杂度为 O(2^(m+n))，这可能非常低效。为了提高效率，可以...
通过以上分析可以看出，这两个问题都属于典型的组合优化问题，它们不仅在理论上有深入的研究价值，在实际应用中也有广泛的用途，如电子设计自动化(EDA)领域中的电路板布局优化，以及安防监控系统中的摄像头布点等。
protected int[] sort(int[] m) { int intLength = m.Length; for (int i = 0; i < intLength; i++) { for (int j = 0; j < intLength - i - 1; j++) { int a = m[j]; int b = m[j + 1]; if (a > b) { m[j] =...
1.17 Status fib(int k,int m,int &f) //求 k 阶斐波那契序列的第 m 项的值 f 这道题目要求编写一个函数来计算 k 阶斐波那契序列的第 m 项的值。解决方案使用迭代法，通过保存已经计算出来的结果来避免重复计算。这...
int m = 10; // 数组长度 printf(" 判定给定数组是否已排好序 \n"); printf("请输入数组：\n"); for (i = 0; i < m; i++) scanf_s("%d", &b[i]); // 输入数组 printf("\n"); for (i = 0; i < m - 1; i++) {...
private static void merge(int[] num, int l, int m, int n, int[] num1) { System.out.print("l=" + l + "m=" + m + "n=" + n); System.out.println(); int i, j, k; i = l; j = m + 1; k = l; while (i ...
接着，指定一个整数m作为计数步长，游戏规则是从第一个人（即编号为1的人）开始，按顺时针方向报数，每数到第m个人就将此人移除出圆圈，然后从下一个人继续开始计数，直到只剩下最后一个人为止。 #### 二、问题分析...
- 输入两个整数`n`和`m`。 - 读取`n`个整数，并只保留那些大于或等于`m`的整数。 - 对这些整数进行快速排序。 - 输出排序后的结果。 #### 代码详解 - `#include<iostream>`：引入标准输入输出库。 - `using ...
排列是指从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列的方法数。组合则是指从n个不同元素中取出m个元素，不考虑元素的顺序的方法数。在Java中实现这两种操作通常涉及到递归或者回溯算法。 描述中...
接下来，从被淘汰者的下一个人重新开始报数，数到m的人继续出局，如此循环直至所有人被淘汰为止。 #### 二、实现思路 本例中采用单向循环链表来模拟这一过程。单向循环链表是一种特殊的数据结构，每个节点包含一个...
程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除， 则表明此数不是素数，反之是素数。 public class lianxi02 { public static void main(String[] args) { int count = 0; for(int i=...