焦点科技编程挑战赛2022题解(关于海量数据的处理)
2023-03-31 10:43:01 时间
比赛说明：
比赛在四个学校开展，南理南航南农和矿大。
题目
查找文本差异
要求
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("
");
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("
");
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<>();
int cnt = 0;
File file=new File("src/main/resources/dest");
String fileDestName=file.getName();
long fileDestSize=file.length();
File file1 = new File("src/main/resources/origin");
String fileOriginName = file1.getName();
long fileOriginSize = file1.length();
//缓冲流 =================================================
InputStream inputDest = this.getClass().getClassLoader().getResourceAsStream("dest");
InputStreamReader destReader= new InputStreamReader(inputDest);
BufferedReader dest = new BufferedReader(destReader);
InputStream inputOrigin = this.getClass().getClassLoader().getResourceAsStream("origin");
InputStreamReader originReader= new InputStreamReader(inputOrigin);
BufferedReader origin = new BufferedReader(originReader);
//========================================================
/**
* 分割文件 两个大文件分割成400份小文件
* 本次操作为创建400个文件
*/
for(int i=0;i<200;i++){
File file2 = new File("src/main/resources/file/"+i+".txt");
if (file2.exists()) file2.delete();
if (!file2.exists()) file2.createNewFile();
}
String destLine,originLie;
/*
根据哈希值将文件中的行数放到400个文件中，
哈希值相同的会被放到一个文件里
*/
long timeStart1 = System.currentTimeMillis();
int count = 0;
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("
");
out.flush();
count++;
}
System.out.println("第一次写文件需要花费：");
System.out.println(System.currentTimeMillis()-timeStart1);
long timeStart2 = System.currentTimeMillis();
count = 0;
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("
");
out.flush();
count++;
}
/**
* 读写操作约耗时5min
*/
System.out.println("第二次写文件需要花费");
System.out.println(System.currentTimeMillis()-timeStart2);
/**
* 接下来遍历200个文件
*/
String line=null;
List<String> list = new ArrayList<>();
// HashMap<String,String> numMap = new HashMap<>();
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];
if (hashMap.containsKey(line)){
hashMap.replace(line,"true");
}
else {
hashMap.put(line,num);
}
}
Set<String> Key = hashMap.keySet();
for (String key:Key){
if (!hashMap.get(key).equals("true")){
list.add(hashMap.get(key));
}
}
hashMap=null; //置空 等GC
}
dest.close();
origin.close();
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);
}
Arrays.sort(result);
System.out.println(result);
return result;
} catch (IOException ex) {
ex.printStackTrace();
}
return new int[0];
}
}
改进
使用单线程读文件，多线程写文件。
创建一个ToFile类 继承Thread类
多线程写文件时碰到的问题
java.io.IOException: Stream closed
这是因为在线程启动后，主线程没有等子线程结束并接着运行,主线程关闭了子线程的文件流。
需要在子线程启动后加
测试结果：
多线程处理后时间减少了两分钟左右。
多线程全部代码:
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{
final static int fileCutNum = 100;
@Override
public int[] diff() {
/**
* 将大文件分割成多份小文件
* 使用hashMap进行查看是否含有
* 用流来读取文件
* 难点在于在规定时间内使用规定内存
* 用hashMap可以节省时间
*/
try {
ArrayList<Integer> res = new ArrayList<>();
int cnt = 0;
File file=new File("src/main/resources/dest");
String fileDestName=file.getName();
long fileDestSize=file.length();
File file1 = new File("src/main/resources/origin");
String fileOriginName = file1.getName();
long fileOriginSize = file1.length();
//缓冲流 =================================================
InputStream inputDest = this.getClass().getClassLoader().getResourceAsStream("dest");
InputStreamReader destReader= new InputStreamReader(inputDest);
BufferedReader dest = new BufferedReader(destReader);
InputStream inputOrigin = this.getClass().getClassLoader().getResourceAsStream("origin");
InputStreamReader originReader= new InputStreamReader(inputOrigin);
BufferedReader origin = new BufferedReader(originReader);
//========================================================
/**
* 分割文件 两个大文件分割成400份小文件
* 本次操作为创建400个文件
*/
for(int i=0;i<fileCutNum;i++){
File file2 = new File("src/main/resources/file/"+i+".txt");
if (file2.exists()) file2.delete();
if (!file2.exists()) file2.createNewFile();
}
// String destLine,originLie;
/*
根据哈希值将文件中的行数放到400个文件中，
哈希值相同的会被放到一个文件里
*/
long timeStart1 = System.currentTimeMillis();
ToFile threadOne = new ToFile(dest);
ToFile threadTwo = new ToFile(origin);
threadOne.start();
threadTwo.start();
threadOne.join();
threadTwo.join();
Thread.sleep(100);
System.out.println("多线程写文件共需要花费：");
System.out.println(System.currentTimeMillis()-timeStart1);
/**
* 接下来遍历多个文件
*/
long startTime = System.currentTimeMillis();
String line=null;
List<String> list = new ArrayList<>();
for (int i=0;i<fileCutNum;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];
if (hashMap.containsKey(line)){
hashMap.replace(line,"true");
}
else {
hashMap.put(line,num);
}
}
Set<String> Key = hashMap.keySet();
for (String key:Key){
if (!hashMap.get(key).equals("true")){
list.add(hashMap.get(key));
}
}
hashMap=null; //置空 等GC
}
dest.close();
origin.close();
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);
}
Arrays.sort(result);
System.out.println("处理数据所需时间");
System.out.println(System.currentTimeMillis()-startTime);
System.out.println("======");
for (int i=0;i< result.length;i++){
System.out.println("处理得到的数据：");
System.out.println(result[i]);
}
System.out.println("======");
return result;
} catch (IOException ex) {
ex.printStackTrace();
} catch (InterruptedException e) {
e.printStackTrace();
}
return new int[0];
}
}
class ToFile extends Thread{
private BufferedReader dest;
public ToFile(BufferedReader bufferedReader){
dest = bufferedReader;
}
@Override
public synchronized void run(){
final int fileCutNum = 100;
try {
String destLine;
int count = 0;
while ((destLine=dest.readLine())!=null){
int code = hash(destLine)%fileCutNum;
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("
");
out.flush();
count++;
}
}catch (Exception e){
System.out.println(e.getMessage());
e.printStackTrace();
}
}
}
若内存不够可以调整文件切割数量，数量越大所需的内存越少，但是响应文件处理时间会增多。
数据集链接：https://www.aliyundrive.com/s/HSNYbfJbsWV
提取码s66l
github地址：https://github.com/KeeyC/2022-Java
相关文章
- 深入理解Spark：核心思想与源码分析. 3.7 创建和启动DAGScheduler
- 深入理解Spark：核心思想与源码分析. 3.8 TaskScheduler的启动
- 深入理解Spark：核心思想与源码分析. 3.10 创建和启动ExecutorAllocationManager
- 深入理解Spark：核心思想与源码分析. 3.11 ContextCleaner的创建与启动
- 深入理解Spark：核心思想与源码分析. 3.12 Spark环境更新
- 深入理解Spark：核心思想与源码分析. 3.13 创建DAGSchedulerSource和BlockManagerSource
- 开卷有益，工程师进阶推荐的十本书
- Linux集群和自动化维导读
- 4位神级大牛说“别神化程序员了，编程不需要天赋和激情！”
- 深入理解Spark：核心思想与源码分析. 3.14 将SparkContext标记为激活
- Java RESTful Web Service实战（第2版） 导读
- 清华张长水教授：系统了解图像识别与机器学习
- Java RESTful Web Service实战（第2版） 1.4 Jersey项目概要
- Java RESTful Web Service实战（第2版） 1.5 快速实现Java REST服务
- Java RESTful Web Service实战（第2版） 1.6 快速了解Java REST服务
- Java RESTful Web Service实战（第2版） 1.8 REST调试工具
- Java RESTful Web Service实战（第2版） 1.9 本章小结
- Java RESTful Web Service实战（第2版） 2.2 资源定位
- Java RESTful Web Service实战（第2版） 2.4 连通性
- Java RESTful Web Service实战（第2版） 2.7 本章小结