java - 合并排序具有可变字数的多个文件

Question

我将一个 10 GB 文件分割成多个 100000 + 几百个单词的文件(因为当我遇到 100000 个单词时我会读到该行)。

private void splitInputFile(String path) {
    try{
        File file=new File(path);
        FileReader fr = new FileReader(file);
        BufferedReader br = new BufferedReader(fr);
        String temp;
        temp = br.readLine();
        String fileName="fileName";
        int fileCount = 1;
        while(temp!=null){
                //TODO Read 100000 words, sort and write to a file. Repeat for the entire file
            if(wordsToBeSorted.size()<=100000){
                startCounting(temp);
                temp=br.readLine();
            }//end of if ->  place 100000+ words inside the list
            else{
                Collections.sort(wordsToBeSorted);
                fileName = "fileName"+fileCount;
                fileCount++;
                File splitFile = new File(fileName);
                PrintWriter pr = new PrintWriter(splitFile);
                for(String word:wordsToBeSorted){   
                    pr.write(word);
                    pr.write("\n");//check if this works -> 1 word per line
                }//end of for
            }//end of else              
        }//end of while
        mergeSort(fileCount);
    }//end of try
    catch(Exception e){
        e.printStackTrace();
    }
}


private void startCounting(String sb) {
    StringTokenizer tokenizer = new StringTokenizer(sb);// Split by space
    while (tokenizer.hasMoreTokens()) {
        String text = tokenizer.nextToken();
        text = text.replaceAll("\\W", "");// Remove all symbols
        if("".equals(text.trim()))
            continue;
        wordsToBeSorted.add(text);
    }

}

现在我想知道如何对这些文件进行排序。我发现我应该进行合并排序。考虑到每个 splitFile 的单词数可变(100000 + 一些额外单词)，是否可以对可变单词数的文件进行合并排序？或者我应该采用其他方法来分割文件？

Answer 1

is it possible to do a merge sort involving files of variable word counts?

当然。我假设这里的目标是 external sorting 。只需打开所有输入文件(除非有 非常多，在这种情况下您可能需要执行多次运行)，读取每个文件中的第一个单词。然后识别具有最小单词的输入，将其放入输出中并从该输入读取下一个单词。关闭并删除所有变空的输入，除非您没有更多输入。

如果您有很多输入，您可以使用heap以下一个单词为关键来组织您的输入。您将删除最小对象，然后在继续处理下一个单词后重新插入它。