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)<\/p>\n
\r\npublic class Main {\r\n\r\n\/*\r\n* 2 arguments\r\n* first argument: inputfile ex: d:\\\\data\\\\input.dat\r\n* second argument: output folder ex: d:\\\\data\r\n*\/\r\npublic static void main(String[] args) throws Exception {\r\n if(args.length!=2){\r\n System.out.println("arguments are not valid");\r\n return;\r\n }\r\n long startTime = System.currentTimeMillis();\r\n \/\/read data, sort, output sorted data to files\r\n PhaseOne phaseOne = new PhaseOne();\r\n List<String> fileNameList = phaseOne.generateSortedFile(args[0], args[1]);\r\n \/\/merge\r\n PhaseTwo phaseTwo = new PhaseTwo();\r\n phaseTwo.merge(fileNameList, args[1]);\r\n \/\/delete temp files\r\n for(String fileName: fileNameList){\r\n new File(fileName).delete();\r\n }\r\n long finishTime = System.currentTimeMillis();\r\n double totalTime = (double)(finishTime - startTime) \/ 1000;\r\n System.out.println("total time: " + totalTime + " seconds");\r\n}\r\n\r\n}\r\n<\/pre>\n(2)<\/p>\n
\r\nimport java.io.BufferedReader;\r\nimport java.io.BufferedWriter;\r\nimport java.io.FileReader;\r\nimport java.io.FileWriter;\r\nimport java.io.IOException;\r\nimport java.util.ArrayList;\r\nimport java.util.List;\r\n\r\npublic class PhaseOne {\r\n\r\nprivate final int amountOnce = 550000;\r\n\r\npublic List<String> generateSortedFile(String inputFile, String outputFolder) {\r\n List<String> fileNameList = new ArrayList<String>();\r\n BufferedReader reader = null;\r\n try {\r\n reader = new BufferedReader(new FileReader(inputFile));\r\n String tempString = null;\r\n int line = 0;\r\n int[] array = new int[amountOnce];\r\n while ((tempString = reader.readLine()) != null) {\r\n \/\/System.out.println("line " + line + ": " + tempString);\r\n array[line % amountOnce] = Integer.parseInt(tempString);\r\n if(line % amountOnce == amountOnce -1){\r\n String fileNO = (line\/amountOnce)<10 ? "0"+ line\/amountOnce : String.valueOf(line\/amountOnce);\r\n String fileName = outputFolder+ "\/tmp"+ fileNO+".dat";\r\n writeData(array, line%amountOnce+1, fileName,fileNameList);\r\n }\r\n line++;\r\n }\r\n String fileNO = (line\/amountOnce)<10 ? "0"+ line\/amountOnce : String.valueOf(line\/amountOnce);\r\n String fileName = outputFolder+ "\/tmp"+ fileNO+".dat";\r\n writeData(array, line%amountOnce, fileName, fileNameList);\r\n reader.close();\r\n} catch (IOException e) {\r\n e.printStackTrace();\r\n} finally {\r\n if (reader != null) {\r\n try {\r\n reader.close();\r\n }\r\n catch (IOException e1) {\r\n }\r\n}\r\nreturn fileNameList;\r\n}\r\n}\r\n\r\nprivate void writeData(int[] array, int length, String fileName, List<String> fileNames) throws IOException{\r\n Quicksort.quickSort(array, length);\r\n BufferedWriter output = new BufferedWriter(new FileWriter(fileName));\r\n for(int i=0;i<length;i++){\r\n output.write(String.valueOf(array[i]));\r\n output.write("\\r\\n");\r\n }\r\n output.close();\r\n fileNames.add(fileName);\r\n array = new int[amountOnce];\r\n}\r\n}\r\n<\/pre>\n(3)<\/p>\n
\r\nimport java.io.BufferedReader;\r\nimport java.io.BufferedWriter;\r\nimport java.io.FileOutputStream;\r\nimport java.io.FileReader;\r\nimport java.io.IOException;\r\nimport java.io.OutputStreamWriter;\r\nimport java.util.ArrayList;\r\nimport java.util.List;\r\n\r\npublic class PhaseTwo {\r\n\r\npublic static int inputBufferSize = 30000;\r\n\r\npublic static int outputBufferSize = 100000;\r\n\r\npublic static boolean finishFlag = false;\r\n\r\npublic void merge(List<String> fileNameList, String outputFolder) {\r\n int[] outputBuffer = new int[outputBufferSize];\r\n int[][] inputBuffers = new int[fileNameList.size()][inputBufferSize];\r\n List<BufferedReader> readers = new ArrayList<BufferedReader>();\r\n try {\r\n for(int i=0;i<fileNameList.size();i++){\r\n BufferedReader reader = new BufferedReader(new FileReader(fileNameList.get(i)));\r\n readers.add(reader);\r\n String tempString = null;\r\n int line = 0;\r\n while ((tempString = readers.get(i).readLine()) != null) {\r\n inputBuffers[i][line] = Integer.parseInt(tempString);\r\n line++;\r\n if(line >= inputBufferSize){\r\n break;\r\n }\r\n }\r\n }\r\n\r\n\r\n int[] pointers = new int[fileNameList.size()];\r\n\r\n int outputBufferIndex = 0;\r\n while(true){\r\n int min = findMin(inputBuffers,pointers, readers);\r\n outputBuffer[outputBufferIndex % outputBufferSize] = min;\r\n if(outputBufferIndex % outputBufferSize == outputBufferSize-1){\r\n outputData(outputBuffer, outputBufferSize, outputFolder+"\/result.dat");\r\n }\r\n outputBufferIndex++;\r\n if(finishFlag){\r\n break;\r\n }\r\n }\r\n outputData(outputBuffer, outputBufferIndex%outputBufferSize, outputFolder+"\/result.dat");\r\n\r\n for(int i=0;i<fileNameList.size();i++){\r\n readers.get(i).close();\r\n }\r\n System.out.println("------------------");\r\n\r\n} catch (IOException e) {\r\n e.printStackTrace();\r\n} finally {\r\n for(int i=0;i<fileNameList.size();i++){\r\n if (readers.get(i) != null) {\r\n try {\r\n readers.get(i).close();\r\n }\r\n catch (IOException e1) {\r\n }\r\n}\r\n}\r\n}\r\n}\r\n\r\nprivate int findMin(int[][] arrays, int[] pointers, List<BufferedReader> readers) throws IOException{\r\n int min = 0;\r\n int index = 0;\r\n for(int i=0;i<arrays.length;i++){\r\n if(arrays[i][pointers[i]]>0){\r\n min = arrays[i][pointers[i]];\r\n index = i;\r\n break;\r\n }\r\n }\r\n\r\n for(int i=index+1;i<arrays.length;i++){\r\n if(arrays[i][pointers[i]]<=0){\r\n continue;\r\n }\r\n if(arrays[i][pointers[i]] < min){\r\n min = arrays[i][pointers[i]];\r\n index = i;\r\n }\r\n }\r\n pointers[index] = pointers[index]+1;\r\n\r\n for(int i=0;i<pointers.length;i++){\r\n if(pointers[i]>=inputBufferSize){\r\n arrays[i] = new int[inputBufferSize];\r\n String tempString = null;\r\n int line = 0;\r\n while ((tempString = readers.get(i).readLine()) != null) {\r\n arrays[i][line] = Integer.parseInt(tempString);\r\n line++;\r\n if(line >= inputBufferSize){\r\n break;\r\n }\r\n }\r\n pointers[i]= 0;\r\n }\r\n } \r\n\r\n \/\/update finishFlag\r\n if(!finishFlag){\r\n boolean flag = true;\r\n for(int i=0;i<arrays.length;i++){\r\n if(arrays[i][pointers[i]]>0){\r\n flag = false;\r\n break;\r\n }\r\n }\r\n finishFlag = flag;\r\n}\r\nreturn min;\r\n}\r\n\r\nprivate void outputData(int[] outputBuffer, int length, String outputFile) throws IOException{\r\nBufferedWriter output = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(outputFile, true)));\r\nfor(int i=0;i<length;i++){\r\n StringBuffer sb = new StringBuffer();\r\n sb.append(outputBuffer[i]);\r\n sb.append("\\r\\n");\r\n output.write(sb.toString());\r\n}\r\noutput.close();\r\noutputBuffer = new int[outputBufferSize];\r\n}\r\n\r\n}\r\n<\/pre>\n(4)<\/p>\n
\r\npublic class Quicksort {\r\n public static void quickSort(int[] data, int length) {\r\n recQuickSort(data, 0, length-1);\r\n }\r\n\r\nprivate static void recQuickSort(int[] data,int left, int right) {\r\n if(right-left <= 0){\r\n return;\r\n}\r\nelse {\r\n long pivot = data[right];\r\n int partition = partitionIt(data, left, right, pivot);\r\n recQuickSort(data, left, partition-1);\r\n recQuickSort(data, partition+1, right);\r\n}\r\n}\r\n\r\nprivate static int partitionIt(int[] data, int left, int right, long pivot) {\r\n int leftPtr = left-1;\r\n int rightPtr = right;\r\n while(true) {\r\n while(data[++leftPtr] < pivot )\r\n ;\r\n while(rightPtr > 0 && data[--rightPtr] > pivot)\r\n ;\r\n if(leftPtr >= rightPtr){\r\n break;\r\n }\r\n else{\r\n swap(data, leftPtr, rightPtr);\r\n }\r\n}\r\nswap(data, leftPtr, right);\r\n return leftPtr;\r\n}\r\n\r\nprivate static void swap(int[] data, int dex1, int dex2) {\r\n int temp = data[dex1];\r\n data[dex1] = data[dex2];\r\n data[dex2] = temp;\r\n}\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"2PMMS(2-phase multiway merge sort)\uff0c\u987e\u540d\u601d\u4e49\uff0c … \u7ee7\u7eed\u9605\u8bfb