比赛说明：
比赛在四个学校开展，南理南航南农和矿大。
题目
查找文本差异
要求
origin和dest中分别包含1000w+条数据dest对数据进行了打乱操作，即origin和dest中相同数据行的顺序不相同- 程序运行的总内存消耗不能超过
30MB - 程序运行的总时间消耗不能超过
10分钟 origin中存在但dest中不存在的数据，取origin中的行号；dest中存在但origin中不存在的数据，取dest中的行号- 输出的行号数组按照升序排列
判定规则
- 总内存消耗超过
30MB，判定为不合格 - 总时间消耗超过
10分钟，判定为不合格
示例
假设 origin 文件内容为：
e630f353-01b3-4b2c-989c-6236b476140a
cc8626ef-c45b-4b9a-96b6-3206d8adc518
8c622fb7-8150-4487-91f2-6a860eb14feb
78c0fe67-b0ea-4fe5-9ef0-4157d956e3d2
假设 dest 文件内容为：
78c0fe67-b0ea-4fe5-9ef0-4157d956e3d2
14fbf539-a614-402c-8ab9-8e7438f3bd72
e630f353-01b3-4b2c-989c-6236b476140a
cc8626ef-c45b-4b9a-96b6-3206d8adc518
输出结果为：
[1, 2]
解决方案：
先分析本题的数据量。本题文件数据量两个文件大约在3000万条左右，比较符合海量数据的处理。同时对时间和内存的限定也十分的苛刻。
所以本题采用的方法是将大文件每行按hash值放入对应的小文件中，然后依次处理每个小文件。
步骤：
首先将两个大文件按hash值分别放入切割后的小文件,两个文件一共800mb，2800w行左右
while ((destLine=dest.readLine())!=null){
int code = hash(destLine)%200;
if (code<0)code=-code;//取绝对值
/**
* 追加文件需要在FileWriter第二个参数选择true
*/
BufferedWriter out = new BufferedWriter(new FileWriter("src/main/resources/file/"+code+".txt",true));
out.write(destLine);
out.write(","+String.valueOf(count)); //添加逗号是为了将行号加入，减少后面再去寻找行号的时间
out.write("\n");
out.flush();
count++;
}
while ((originLie=origin.readLine())!=null){
int code = hash(originLie)%200;
if (code<0)code=-code;//取绝对值
/**
* 追加文件需要在FileWriter第二个参数选择true
*/
BufferedWriter out = new BufferedWriter(new FileWriter("src/main/resources/file/"+code+".txt",true));
out.write(originLie);
out.write(","+count);
out.write("\n");
out.flush();
count++;
}
//写入第一个文件花费 16000ms
//写入两个大概33000ms
然后分别遍历这些小文件中的数据
String line=null;
List<String> list = new ArrayList<>();
for (int i=0;i<200;i++){
HashMap<String,String> hashMap = new HashMap<>();
BufferedReader bufferedReader = new BufferedReader(new FileReader("src/main/resources/file/"+i+".txt"));
while( (line = bufferedReader.readLine())!=null){
String[] a = line.split(",");
line = a[0];
String num = a[1];
//若HashMap中没有字符串，则将字符串和行号放入
//若后续出现重复，则将行号改为true
if (hashMap.containsKey(line)){
hashMap.replace(line,"true");
}
else {
hashMap.put(line,num);
}
}
Set<String> Key = hashMap.keySet();
//向list中添加行号
for (String key:Key){
if (!hashMap.get(key).equals("true")){
list.add(hashMap.get(key));
}
}
hashMap=null; //置空 等GC
}
然后便是将list转化为int类型数组输出
int [] result = new int[list.size()];
int index =0;
for (int i=0;i<list.size();i++){
String num = list.get(i);
result[index++] = Integer.parseInt(num);
}
处理结果：
时间花费6分钟
至此内存与时间的限制都满足了。
注意问题
hashMap内存的释放
全部代码:
package com.focustech.fpc.algorithm;
import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.stream.Stream;
import static java.util.Objects.hash;
/**
* 差异分析器实现类示例
* @author KeC
**/
public class DemoDifferenceAnalyser implements IDifferenceAnalyser{
@Override
public int[] diff() {
/**
* 将大文件分割成多份小文件
* 使用hashMap进行查看是否含有
* 用流来读取文件
* 难点在于在规定时间内使用规定内存
* 用hashMap可以节省时间
*/
try {
ArrayList<Integer> res = new ArrayList<>