本文最后更新于 963 天前,其中的信息可能已经有所发展或是发生改变。
思路
刚开始我以为这题的考点是如何快速读取文件(因为这是公司多线程学习分享后布置的作业),我就用多线程来解题。后来出题人跟我说:200m测试数据时我的程序OOM了,我才醒悟这题的考点不是快速读取文件,而是大文件排序。
这题挺有意思的,解题运用了多路归并,有个巧妙的地方估计只有实操才知道——复用流。
题目
查找第K小/大数据
每个法官都有不同的办案能力,假设每个案子的难易程度都一样。现在到年底了,各个领导关注的点可能不太一样。
- 领导A:想要知道每家院办案能力最强的和办案能力最弱的法官。
- 领导B:想要知道每家院办案能力第二强的和办案能力第二弱的法官。
- 领导K:想要知道每家院办案能力第K强的和办案能力第K弱的法官。
由于目前管理比较混乱,法官的办案情况存在若干个文件中,每个文件中有若干条记录,文件中每行存储一个法官的办案数,其中包括:法院ID、用户ID(32位UUID)和办案数,每个数据中间用一个空格隔开,例如:
- 2400 UUID 2
其中法官的工作量可能是相同的。
现在需要设计一个程序从这些文件中找到每家法院第K小/大工作量的法官,输出结果具体要求如下:
-
输出结果按照法院ID进行排序,从小到大
-
工作量相同的按照用户ID进行排序,从小到大
-
K的取值范围
- 1 <= K
- 针对每家法院,K = min(K,n) ,其中n为该法院的用户数。
- 举个栗子:如果最后法院2400的用户数为100,传入K的值为101,则当前法院的需要查找的K = 100 = min(101,100)
-
实现指定方法
findKthNumbers
/** * description: 查找第K小/大数据 <br/> * @date 20-6-18 */ public class KthNumbers implements IKthNumbers { /** * 查找第K小/大数据 * * @param dir 数据文件存放路径<br/> * 文件个数不定,文件内容格式如下:<br/> * 2400 69890e27cd5a47b38093b520f0eb454b 26 <br/> * 2401 a6fd9d728a814cbcb240b520f0eb454b 32 <br/> * 2400 751628a92f264995a268b520f0eb454b 33 <br/> * 1908 48e102e47a704c87aee3b520f0eb454b 13 <br/> * ...... * @param k 第K小/大 * @return 查找的结果集<br/> * 输出结果按照法院ID进行排序,从小到大<br/> * 工作量相同的按照用户ID进行排序,从小到大<br/> * 输出格式如下:<br/> * 2400 <br/> * 69890e27cd5a47b38093b520f0eb454b 26 <br/> * 751628a92f264995a268b520f0eb454b 33 */ @Override public String findKthNumbers(String dir, int k) { return null; } }
输出格式,第一行法院ID,第二行工作量第K小的用户ID和工作量(以空格分割),第三行工作连第K大的用户ID和工作量(以空格分割),如下:
2400 69890e27cd5a47b38093b520f0eb454b 26 751628a92f264995a268b520f0eb454b 33 ......
-
按公司要求的代码模板,代码质量优,逻辑清晰,注释中编程思路详细
-
环境要求
- 不能使用第三方库
- 不能使用数据库
- jdk1.8
-
评定标准
- 程序的正确性,能输出正确答案,性能良好 ,70%
- 程序设计合理,结构清晰,代码质量优 30%
-
奖励
- 神秘大奖一份
代码
@Data
public class FileAndReader {
private File file;
private BufferedReader reader;
private String currentRow;
public FileAndReader(File file) {
this.file = file;
try {
reader = new BufferedReader(new FileReader(file));
currentRow = reader.readLine();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
public String readNextLine() {
try {
currentRow=reader.readLine();
if (currentRow == null) {
reader.close();
}
} catch (IOException e) {
e.printStackTrace();
}
return currentRow;
}
}
@Data
public class FileAndWriter {
private File file;
private BufferedWriter writer;
private Long rows;
public FileAndWriter(File file) {
this.file = file;
try {
writer = new BufferedWriter(new FileWriter(file));
} catch (IOException e) {
e.printStackTrace();
}
rows=0L;
}
public void write(String str){
rows++;
try {
writer.write(str);
} catch (IOException e) {
e.printStackTrace();
}
}
}
public class KthNumbers implements IKthNumbers {
/** 换行符 */
public static final String WRAP = "\r\n";
/** 拆分的小文件最大行数 */
public static final int MAX_ROW = 10_000;
public static String PATH;
private Map<String, FileAndWriter> corpFiles = new HashMap<>();
public String findKthNumbers(String dir, int k) {
long allTimeStart = System.currentTimeMillis();
PATH = dir;
final File slipFile = new File(PATH + "/slip");
final File cropFile = new File(PATH + "/crop");
final File sortedFile = new File(PATH + "/sorted");
deleteFile(cropFile);
deleteFile(slipFile);
deleteFile(sortedFile);
cropFile.mkdirs();
slipFile.mkdirs();
sortedFile.mkdir();
final File file = new File(dir);
// 根据法院拆分文件
if (file.isDirectory()) {
final long start = System.currentTimeMillis();
for (File singleFile : file.listFiles()) {
if (singleFile.isFile()) {
slipWithCorp(singleFile);
}
}
corpFiles.forEach((k2, v) -> {
try {
v.getWriter().close();
} catch (IOException e) {
e.printStackTrace();
}
});
final long endTime = System.currentTimeMillis();
System.out.printf("根据法院拆分文件耗时:【%s】毫秒%n", endTime - start);
}
// 拆分为小文件
final long startTimeOfSlipFile = System.currentTimeMillis();
corpFiles.forEach((k1, v) -> slipWithMaxRow(v.getFile()));
final long endTimeOfSlipFile = System.currentTimeMillis();
System.out.printf("拆分单个法院文件为小文件耗时:【%s】毫秒%n", endTimeOfSlipFile - startTimeOfSlipFile);
// 排序所有小文件
long startTime = System.currentTimeMillis();
Arrays.stream(slipFile.listFiles()).forEach(e -> {
Arrays.stream(e.listFiles()).forEach(this::sortFile);
});
long endTime = System.currentTimeMillis();
System.out.printf("排序所有小文件耗时:【%s】毫秒%n", endTime - startTime);
// 合并所有小文件
final long startTimeOfMearge = System.currentTimeMillis();
Arrays.stream(slipFile.listFiles()).forEach(e -> {
meargeSortFile(e, new File(PATH + "/sorted/" + e.getName() + ".txt"));
});
final long endTimeOfMearge = System.currentTimeMillis();
System.out.printf("合并所有小文件耗时:【%s】毫秒%n", endTimeOfMearge - startTimeOfMearge);
// 计算目标行
final Map<String, Pair<Long, Long>> targetLine = new HashMap<>();
corpFiles.forEach((k4, v) -> {
Long first;
Long last;
if (v.getRows() < k) {
first = 1L;
last = v.getRows();
} else {
first = k - 1L;
last = v.getRows() - k;
}
targetLine.put(k4, new Pair<>(first, last));
});
// 获取目标字符串
final StringBuilder builder = new StringBuilder();
final long getResultStart = System.currentTimeMillis();
Arrays.stream(sortedFile.listFiles()).forEach(e -> {
try (final BufferedReader reader = new BufferedReader(new FileReader(e))) {
String temp;
Long count = 1L;
final String corp = e.getName().split("\\.")[0];
final Pair<Long, Long> pair = targetLine.get(corp);
String first = "";
String last = "";
while ((temp = reader.readLine()) != null) {
if (count.equals(pair.getKey())) {
first = temp;
} else if (count.equals(pair.getValue())) {
last = temp;
}
count++;
}
builder.append(corp).append(WRAP)
.append(first.substring(2)).append(" ")
.append(first.substring(0, 2).startsWith("0") ? first.substring(1, 2) : first.substring(0, 2))
.append(WRAP)
.append(last.substring(2)).append(" ")
.append(last.substring(0, 2).startsWith("0") ? last.substring(1, 2) : last.substring(0, 2))
.append(WRAP);
} catch (FileNotFoundException fileNotFoundException) {
fileNotFoundException.printStackTrace();
} catch (IOException ioException) {
ioException.printStackTrace();
}
});
final long getResultEnd = System.currentTimeMillis();
System.out.printf("读取文件获取结果耗时:【%s】毫秒%n", getResultEnd - getResultStart);
long allTimeEnd = System.currentTimeMillis();
System.out.printf("总耗时:【%s】毫秒%n", allTimeEnd - allTimeStart);
return builder.toString();
}
/**
* description: 递归删除文件
* version: 1.0
* date: 2021/3/17 11:47
* author: 余游洋
*
* @param file
* @return void
*/
private void deleteFile(File file) {
if (file.exists()) {
if (file.isDirectory()) {
File[] files = file.listFiles();
for (int i = 0; i < files.length; i++) {
deleteFile(files[i]);
}
} else {
file.delete();
}
}
}
/**
* description: 根据法院编号拆分文件
* version: 1.0
* date: 2021/3/17 11:48
* author: 余游洋
*
* @param file
* @return void
*/
public void slipWithCorp(File file) {
try (final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream(file)))) {
String temp;
while ((temp = bufferedReader.readLine()) != null) {
final String[] s = temp.split(" ");
final FileAndWriter corpFile = corpFiles.computeIfAbsent(s[0], e -> {
File newCorpFile = new File(PATH + "/crop/" + e + ".txt");
try {
newCorpFile.createNewFile();
} catch (IOException ioException) {
ioException.printStackTrace();
}
return new FileAndWriter(newCorpFile);
});
corpFile.write((s[2].length() == 2 ? s[2] : "0" + s[2]) + s[1] + WRAP);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* description: 拆分为指定行数的小文件
* version: 1.0
* date: 2021/3/17 11:48
* author: 余游洋
*
* @param file
* @return void
*/
public void slipWithMaxRow(File file) {
final String slipDir = PATH + "/slip/" + file.getName().split("\\.")[0];
new File(slipDir).mkdirs();
int fileCount = 0;
File slipFile = getSlipFile(slipDir, fileCount);
BufferedWriter writer = null;
try (
BufferedReader reader = new BufferedReader(new FileReader(file));
) {
writer = new BufferedWriter(new FileWriter(slipFile));
String temp;
int count = 0;
while ((temp = reader.readLine()) != null) {
writer.append(temp).append(WRAP);
if (++count == MAX_ROW) {
count = 0;
writer.close();
slipFile = getSlipFile(slipDir, ++fileCount);
writer = new BufferedWriter(new FileWriter(slipFile));
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
writer.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* description: 将文件加载到内存排序
* version: 1.0
* date: 2021/3/17 11:49
* author: 余游洋
*
* @param file
* @return void
*/
public void sortFile(File file) {
final ArrayList<String> strings = new ArrayList<>();
try (final BufferedReader reader = new BufferedReader(new FileReader(file))) {
String temp;
while ((temp = reader.readLine()) != null) {
strings.add(temp);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
Collections.sort(strings);
try (final BufferedWriter writer = new BufferedWriter(new FileWriter(file))) {
strings.forEach(e -> {
try {
writer.append(e).append(WRAP);
} catch (IOException ioException) {
ioException.printStackTrace();
}
});
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* description: 利用多路归并,合并小文件
* version: 1.0
* date: 2021/3/17 12:40
* author: 余游洋
*
* @param fromDir
* @param target
* @return void
*/
public void meargeSortFile(File fromDir, File target) {
final TreeSet<FileAndReader> readerTreeSet = new TreeSet<>(Comparator.comparing(FileAndReader::getCurrentRow));
for (File file : fromDir.listFiles()) {
FileAndReader fileAndReader = new FileAndReader(file);
if (fileAndReader.getCurrentRow() != null) {
readerTreeSet.add(fileAndReader);
}
}
try (final BufferedWriter writer = new BufferedWriter(new FileWriter(target))) {
while (!readerTreeSet.isEmpty()) {
final FileAndReader first = readerTreeSet.pollFirst();
writer.append(first.getCurrentRow()).append(WRAP);
final String nextLine = first.readNextLine();
if (null != nextLine) {
readerTreeSet.add(first);
}
}
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* description: 创建拆分的小文件
* version: 1.0
* date: 2021/3/17 12:42
* author: 余游洋
*
* @param slipDir
* @param fileCount
* @return java.io.File
*/
public File getSlipFile(String slipDir, int fileCount) {
File slipFile = new File(slipDir + "/slip" + (++fileCount) + ".txt");
try {
slipFile.createNewFile();
} catch (IOException e) {
e.printStackTrace();
}
return slipFile;
}
}