本文最后更新于 891 天前，其中的信息可能已经有所发展或是发生改变。

思路

刚开始我以为这题的考点是如何快速读取文件（因为这是公司多线程学习分享后布置的作业），我就用多线程来解题。后来出题人跟我说：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;
    }
}

Post Views: 796

思路

题目

查找第K小/大数据

代码

发送评论 编辑评论

推荐文章

发送评论编辑评论