2PMMS(2-phase multiway merge sort)\uff0c\u987e\u540d\u601d\u4e49\uff0c\u75312\u4e2a\u9636\u6bb5\u7ec4\u6210\u3002\u7b2c\u4e00\u4e2a\u9636\u6bb5\u5c06\u6e90\u6587\u4ef6\u5206\u6279\u6b21\u8bfb\u5230\u5185\u5b58\u4e2d\uff0c\u91c7\u7528\u67d0\u79cd\u5185\u90e8\u6392\u5e8f\u7b97\u6cd5\u8fdb\u884c\u6392\u5e8f\uff0c\u7136\u540e\u5c06\u6bcf\u6b21\u6392\u5e8f\u540e\u7684\u7ed3\u679c\u5199\u5230\u786c\u76d8\u4e0a\uff0c1\u4e2a\u6279\u6b21\u5bf9\u5e941\u4e2a\u6587\u4ef6\uff1b\u7b2c\u4e8c\u4e2a\u9636\u6bb5\u5c06n\u4e2a\u6587\u4ef6\u6279\u91cf\u8bfb\u5230\u7f13\u5b58\u91cc\uff0c\u4eceN\u4e2a\u7f13\u5b58\u5e8f\u5217\u91cc\u627e\u5230\u6700\u5c0f\u6570\uff0c\u653e\u5230\u8f93\u51fa\u7f13\u5b58\u91cc\u3002\u6bcf\u6b21\u653e\u5b8c\u540e\uff0c\u8981\u68c0\u67e5\u6bcf\u4e2a\u8f93\u5165\u7f13\u5b58\u662f\u5426\u8bfb\u5b8c\uff0c\u5982\u679c\u8bfb\u5b8c\u5219\u4ece\u5bf9\u5e94\u7684\u6587\u4ef6\u91cc\u7ee7\u7eed\u8bfb\u6570\u636e\u5230\u7f13\u5b58\uff0c\u76f4\u5230\u6587\u4ef6\u5168\u90e8\u8bfb\u5b8c\u4e3a\u6b62\uff1b\u5e76\u68c0\u67e5\u8f93\u51fa\u7f13\u5b58\u662f\u5426\u5df2\u6ee1\uff0c\u5982\u6ee1\u5219\u8f93\u51fa\u5230\u6587\u4ef6\u5e76\u6e05\u7a7a\u8f93\u51fa\u7f13\u5b58\u3002<\/p>\n
4\u4e2a\u7c7b\uff1a<\/p>\n
(1)
\n[code lang=”java”]
\npublic class Main {<\/p>\n
\/*
\n* 2 arguments
\n* first argument: inputfile ex: d:\\\\data\\\\input.dat
\n* second argument: output folder ex: d:\\\\data
\n*\/
\npublic static void main(String[] args) throws Exception {
\n if(args.length!=2){
\n System.out.println("arguments are not valid");
\n return;
\n }
\n long startTime = System.currentTimeMillis();
\n \/\/read data, sort, output sorted data to files
\n PhaseOne phaseOne = new PhaseOne();
\n List<String> fileNameList = phaseOne.generateSortedFile(args[0], args[1]);
\n \/\/merge
\n PhaseTwo phaseTwo = new PhaseTwo();
\n phaseTwo.merge(fileNameList, args[1]);
\n \/\/delete temp files
\n for(String fileName: fileNameList){
\n new File(fileName).delete();
\n }
\n long finishTime = System.currentTimeMillis();
\n double totalTime = (double)(finishTime – startTime) \/ 1000;
\n System.out.println("total time: " + totalTime + " seconds");
\n}<\/p>\n
}
\n[\/code]
\n(2)
\n[code lang=”java”]
\nimport java.io.BufferedReader;
\nimport java.io.BufferedWriter;
\nimport java.io.FileReader;
\nimport java.io.FileWriter;
\nimport java.io.IOException;
\nimport java.util.ArrayList;
\nimport java.util.List;<\/p>\n
public class PhaseOne {<\/p>\n
private final int amountOnce = 550000;<\/p>\n
public List<String> generateSortedFile(String inputFile, String outputFolder) {
\n List<String> fileNameList = new ArrayList<String>();
\n BufferedReader reader = null;
\n try {
\n reader = new BufferedReader(new FileReader(inputFile));
\n String tempString = null;
\n int line = 0;
\n int[] array = new int[amountOnce];
\n while ((tempString = reader.readLine()) != null) {
\n \/\/System.out.println("line " + line + ": " + tempString);
\n array[line % amountOnce] = Integer.parseInt(tempString);
\n if(line % amountOnce == amountOnce -1){
\n String fileNO = (line\/amountOnce)<10 ? "0"+ line\/amountOnce : String.valueOf(line\/amountOnce);
\n String fileName = outputFolder+ "\/tmp"+ fileNO+".dat";
\n writeData(array, line%amountOnce+1, fileName,fileNameList);
\n }
\n line++;
\n }
\n String fileNO = (line\/amountOnce)<10 ? "0"+ line\/amountOnce : String.valueOf(line\/amountOnce);
\n String fileName = outputFolder+ "\/tmp"+ fileNO+".dat";
\n writeData(array, line%amountOnce, fileName, fileNameList);
\n reader.close();
\n} catch (IOException e) {
\n e.printStackTrace();
\n} finally {
\n if (reader != null) {
\n try {
\n reader.close();
\n }
\n catch (IOException e1) {
\n }
\n}
\nreturn fileNameList;
\n}
\n}<\/p>\n
private void writeData(int[] array, int length, String fileName, List<String> fileNames) throws IOException{
\n Quicksort.quickSort(array, length);
\n BufferedWriter output = new BufferedWriter(new FileWriter(fileName));
\n for(int i=0;i<length;i++){
\n output.write(String.valueOf(array[i]));
\n output.write("\\r\\n");
\n }
\n output.close();
\n fileNames.add(fileName);
\n array = new int[amountOnce];
\n}
\n}
\n[\/code]
\n(3)
\n[code lang=”java”]
\nimport java.io.BufferedReader;
\nimport java.io.BufferedWriter;
\nimport java.io.FileOutputStream;
\nimport java.io.FileReader;
\nimport java.io.IOException;
\nimport java.io.OutputStreamWriter;
\nimport java.util.ArrayList;
\nimport java.util.List;<\/p>\n
public class PhaseTwo {<\/p>\n
public static int inputBufferSize = 30000;<\/p>\n
public static int outputBufferSize = 100000;<\/p>\n
public static boolean finishFlag = false;<\/p>\n
public void merge(List<String> fileNameList, String outputFolder) {
\n int[] outputBuffer = new int[outputBufferSize];
\n int[][] inputBuffers = new int[fileNameList.size()][inputBufferSize];
\n List<BufferedReader> readers = new ArrayList<BufferedReader>();
\n try {
\n for(int i=0;i<fileNameList.size();i++){
\n BufferedReader reader = new BufferedReader(new FileReader(fileNameList.get(i)));
\n readers.add(reader);
\n String tempString = null;
\n int line = 0;
\n while ((tempString = readers.get(i).readLine()) != null) {
\n inputBuffers[i][line] = Integer.parseInt(tempString);
\n line++;
\n if(line >= inputBufferSize){
\n break;
\n }
\n }
\n }<\/p>\n
int[] pointers = new int[fileNameList.size()];<\/p>\n
int outputBufferIndex = 0;
\n while(true){
\n int min = findMin(inputBuffers,pointers, readers);
\n outputBuffer[outputBufferIndex % outputBufferSize] = min;
\n if(outputBufferIndex % outputBufferSize == outputBufferSize-1){
\n outputData(outputBuffer, outputBufferSize, outputFolder+"\/result.dat");
\n }
\n outputBufferIndex++;
\n if(finishFlag){
\n break;
\n }
\n }
\n outputData(outputBuffer, outputBufferIndex%outputBufferSize, outputFolder+"\/result.dat");<\/p>\n
for(int i=0;i<fileNameList.size();i++){
\n readers.get(i).close();
\n }
\n System.out.println("——————");<\/p>\n
} catch (IOException e) {
\n e.printStackTrace();
\n} finally {
\n for(int i=0;i<fileNameList.size();i++){
\n if (readers.get(i) != null) {
\n try {
\n readers.get(i).close();
\n }
\n catch (IOException e1) {
\n }
\n}
\n}
\n}
\n}<\/p>\n
private int findMin(int[][] arrays, int[] pointers, List<BufferedReader> readers) throws IOException{
\n int min = 0;
\n int index = 0;
\n for(int i=0;i<arrays.length;i++){
\n if(arrays[i][pointers[i]]>0){
\n min = arrays[i][pointers[i]];
\n index = i;
\n break;
\n }
\n }<\/p>\n
for(int i=index+1;i<arrays.length;i++){
\n if(arrays[i][pointers[i]]<=0){
\n continue;
\n }
\n if(arrays[i][pointers[i]] < min){
\n min = arrays[i][pointers[i]];
\n index = i;
\n }
\n }
\n pointers[index] = pointers[index]+1;<\/p>\n
for(int i=0;i<pointers.length;i++){
\n if(pointers[i]>=inputBufferSize){
\n arrays[i] = new int[inputBufferSize];
\n String tempString = null;
\n int line = 0;
\n while ((tempString = readers.get(i).readLine()) != null) {
\n arrays[i][line] = Integer.parseInt(tempString);
\n line++;
\n if(line >= inputBufferSize){
\n break;
\n }
\n }
\n pointers[i]= 0;
\n }
\n } <\/p>\n
\/\/update finishFlag
\n if(!finishFlag){
\n boolean flag = true;
\n for(int i=0;i<arrays.length;i++){
\n if(arrays[i][pointers[i]]>0){
\n flag = false;
\n break;
\n }
\n }
\n finishFlag = flag;
\n}
\nreturn min;
\n}<\/p>\n
private void outputData(int[] outputBuffer, int length, String outputFile) throws IOException{
\nBufferedWriter output = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(outputFile, true)));
\nfor(int i=0;i<length;i++){
\n StringBuffer sb = new StringBuffer();
\n sb.append(outputBuffer[i]);
\n sb.append("\\r\\n");
\n output.write(sb.toString());
\n}
\noutput.close();
\noutputBuffer = new int[outputBufferSize];
\n}<\/p>\n
}
\n[\/code]
\n(4)
\n[code lang=”java”]
\npublic class Quicksort {
\n public static void quickSort(int[] data, int length) {
\n recQuickSort(data, 0, length-1);
\n }<\/p>\n
private static void recQuickSort(int[] data,int left, int right) {
\n if(right-left <= 0){
\n return;
\n}
\nelse {
\n long pivot = data[right];
\n int partition = partitionIt(data, left, right, pivot);
\n recQuickSort(data, left, partition-1);
\n recQuickSort(data, partition+1, right);
\n}
\n}<\/p>\n
private static int partitionIt(int[] data, int left, int right, long pivot) {
\n int leftPtr = left-1;
\n int rightPtr = right;
\n while(true) {
\n while(data[++leftPtr] < pivot )
\n ;
\n while(rightPtr > 0 && data[–rightPtr] > pivot)
\n ;
\n if(leftPtr >= rightPtr){
\n break;
\n }
\n else{
\n swap(data, leftPtr, rightPtr);
\n }
\n}
\nswap(data, leftPtr, right);
\n return leftPtr;
\n}<\/p>\n
private static void swap(int[] data, int dex1, int dex2) {
\n int temp = data[dex1];
\n data[dex1] = data[dex2];
\n data[dex2] = temp;
\n}
\n}
\n[\/code]<\/p>\n","protected":false},"excerpt":{"rendered":"
2PMMS(2-phase multiway merge sort)\uff0c\u987e\u540d\u601d\u4e49\uff0c\u75312\u4e2a\u9636\u6bb5\u7ec4\u6210\u3002\u7b2c\u4e00\u4e2a\u9636\u6bb5\u5c06\u6e90 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[7,42],"class_list":["post-42","post","type-post","status-publish","format-standard","hentry","category-8","tag-2pmms","tag-java"],"_links":{"self":[{"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=\/wp\/v2\/posts\/42","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=42"}],"version-history":[{"count":7,"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=\/wp\/v2\/posts\/42\/revisions"}],"predecessor-version":[{"id":129,"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=\/wp\/v2\/posts\/42\/revisions\/129"}],"wp:attachment":[{"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=42"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=42"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lixiaodong.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=42"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}