合併排序具有可變字數的多個文件

我將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多少個額外單詞）的事實，是否可以進行包含可變詞計數文件的合併排序？或者我應該按照其他方法來分割文件？

來源

2013-03-06 Prasanna

是否有可能做一個合併排序，涉及可變字數的文件？

當然。我假設這裏的目標是external sorting。只需打開所有輸入文件（除非有真的很多，在這種情況下，您可能需要執行多次運行），請從每個文件中讀取第一個單詞。然後識別最小單詞的輸入，將其輸入到輸出中，並從該輸入中讀取下一個單詞。關閉並移除任何變空的輸入，除非您沒有更多的輸入。

如果您有很多輸入，您可以使用heap來組織您的輸入，並將下一個單詞作爲關鍵字。您將刪除最小的對象，然後在進入下一個單詞之後重新插入它。

來源

2013-03-06 01:21:11 MvG

合併排序具有可變字數的多個文件

回答

相關問題