Go语言视频零基础入门到精通

黑乌乌

对远远大于内存的数据进行外排序，在多路比较的时候用败者树效率会更高。

2. package my.sort;
3. import java.io.BufferedInputStream;
4. import java.io.BufferedOutputStream;
5. import java.io.BufferedWriter;
6. import java.io.DataInputStream;
7. import java.io.DataOutputStream;
8. import java.io.File;
9. import java.io.FileInputStream;
10. import java.io.FileNotFoundException;
11. import java.io.FileOutputStream;
12. import java.io.FileWriter;
13. import java.io.IOException;
14. import java.util.ArrayList;
15. import java.util.Arrays;
16. import java.util.Iterator;
17. import java.util.Random;
18. /**
19. * 基于大数据量的外排序算法，分为二路贵宾和多路归并
20. * @author java2king
21. * @link http://blog.csdn.net/Java2King
22. *
23. */
24. public class ExternalSort {
25.     public static int ITEM_COUNT = 10000000; //总数
26.     public static int BUFFER_SIZE = 1024*4*1000;// 一次缓冲读取
27.    
28.     public static int FILE_COUNT = 1024*1000*1*4;// 每个文件的记录数1
29.    
30.     public static File MAIN_FILE = new File("mainset");//要排序的文件
31.     /**
32.      * 二路归并
33.      * @param file
34.      * @return
35.      * @throws IOException
36.      */
37.     public File sort(File file) throws IOException {
38.         ArrayList<File> files = split(file);
39.         return process(files);
40.     }
41.     /**
42.      * 多路归并
43.      * @param file
44.      * @throws IOException
45.      */
46.     public void mSort(File file) throws IOException{
47.         ArrayList<File> files = split(file);
48.         multipleMerge(files);
49.         
50.     }
51.     // recursive method to merge the lists until we are left with a
52.     // single merged list
53.     private File process(ArrayList<File> list) throws IOException {
54.         if (list.size() == 1) {
55.             return list.get(0);
56.         }
57.         ArrayList<File> inter = new ArrayList<File>();
58.         for (Iterator<File> itr = list.iterator(); itr.hasNext();) {
59.             File one = itr.next();
60.             if (itr.hasNext()) {
61.                 File two = itr.next();
62.                 inter.add(merge(one, two));
63.             } else {
64.               //  return one;
65.                 inter.add(one);
66.             }
67.         }
68.         return process(inter);
69.     }
70.     /**
71.      * Splits the original file into a number of sub files.
72.      */
73.     private ArrayList<File> split(File file) throws IOException {
74.         ArrayList<File> files = new ArrayList<File>();
75.         int[] buffer = new int[FILE_COUNT];
76.         FileInputStream fr = new FileInputStream(file);
77.         BufferedInputStream bin = new BufferedInputStream(fr,BUFFER_SIZE);
78.         DataInputStream din=new DataInputStream(bin);  
79.         boolean fileComplete = false;
80.         
81.         while (!fileComplete) {
82.             int index = buffer.length;
83.             for (int i = 0; i < buffer.length && !fileComplete; i++) {
84.                 try {
85.                      buffer[i] = din.readInt();
86.                 } catch (Exception e) {
87.                     fileComplete = true;
88.                     index = i;
89.                 }
90.             }
91.             if (index != 0 && buffer[0] > -1) {
92.                 Arrays.sort(buffer, 0, index);
93.                 File f = new File("set" + new Random().nextInt());
94.          //       File temp = File.createTempFile("josp", ".tmp", f);   
95.                 FileOutputStream writer = new FileOutputStream(f);
96.                 BufferedOutputStream bOutputStream = new BufferedOutputStream(writer);
97.             
98.                 DataOutputStream dout=new DataOutputStream(bOutputStream);
99.                 for (int j = 0; j < index; j++) {
100.                     dout.writeInt(buffer[j]);
101.                 }
102.                 dout.close();
103.                 bOutputStream.close();
104.                 writer.close();
105.                 files.add(f);
106.                
107.             }
108.         }
109.         din.close();
110.         bin.close();
111.         fr.close();
112.         return files;
113.     }
114.     /**
115.      * 多路归并
116.      * @param list
117.      * @throws IOException
118.      */
119.     private void multipleMerge(ArrayList<File> list) throws IOException {
120.         
121.         int fileSize = list.size();
122.         
123.         if(fileSize == 1){
124.             return;
125.         }
126.         
127.         ArrayList<DataInputStream> dinlist = new ArrayList<DataInputStream>();
128.         
129.         int[] ext = new int[fileSize];//比较数组
130.     //    File output = new File("multipleMerged");
131.         FileOutputStream os = new FileOutputStream(MAIN_FILE);
132.         BufferedOutputStream bout = new BufferedOutputStream(os);
133.         DataOutputStream dout = new DataOutputStream(bout);
134.         for (int i = 0; i < fileSize; i++) {
135.         try {
136.         dinlist.add(i, new DataInputStream(new BufferedInputStream(
137.          new FileInputStream(list.get(i)), BUFFER_SIZE)));
138.         } catch (Exception e) {
139.                 e.printStackTrace();
140.             }
141.         }
142.         int index = 0;
143.         for (int i = 0; i < fileSize; i++) {
144.             try {
145.                 ext[i] = dinlist.get(i).readInt();
146.             } catch (Exception e) {
147.                 System.err.println("file_" + i + "为空");
148.                 ext[i] = -1;
149.             }
150.         }
151.         int count = fileSize;
152.         int[] sum = new int[fileSize];
153.         
154.         while (count > 1) {
155.             index = getMinIndex(ext);
156.             dout.writeInt(ext[index]);
157.             sum[index]++;
158.             try {
159.                 ext[index] = dinlist.get(index).readInt();
160.             } catch (Exception e) {
161.                 ext[index] = -1;
162.                 count--;
163.                 dinlist.get(index).close();
164.         //        System.err.println(index + "空,写进:" +sum[index]);
165.                
166.             }
167.         }
168.         int sIndex = getSIndex(ext);
169.         dout.writeInt(ext[sIndex]);
170.         while (true) {
171.             try {
172.                 dout.writeInt(dinlist.get(sIndex).readInt());
173.             } catch (Exception e) {
174.                 dinlist.get(sIndex).close();
175.                 break;
176.             }
177.         }
178.         dout.close();
179.     }
180.     //找到剩下的最后一个文件输入流
181.     public int getSIndex(int[] ext){
182.         int result = 0;
183.         for (int i = 0; i < ext.length; i++) {
184.             if(ext[i]!= -1){
185.                 result = i;
186.                 break;
187.             }
188.         }
189.         return result;
190.     }
191.     //找到数据中最小的一个
192.     public int getMinIndex(int[] ext){
193.         int min = 2147483647;
194.         int index = -1;
195.         for (int i = 0; i < ext.length; i++) {
196.             if(ext[i] != -1 && ext[i] < min){
197.                 min = ext[i];
198.                 index = i;
199.             }
200.         }
201.         return index;
202.     }
203.     /**
204.      * 二路归并
205.      *
206.      * @param one
207.      * @param two
208.      * @return
209.      * @throws IOException
210.      */
211.     private File merge(File one, File two) throws IOException {
212.         FileInputStream fis1 = new FileInputStream(one);
213.         FileInputStream fis2 = new FileInputStream(two);
214.         BufferedInputStream bin1 = new BufferedInputStream(fis1,BUFFER_SIZE);
215.         BufferedInputStream bin2 = new BufferedInputStream(fis2,BUFFER_SIZE);
216.         
217.         DataInputStream din1=new DataInputStream(bin1);  
218.         DataInputStream din2=new DataInputStream(bin2);  
219.         
220.         File output = new File("merged" + new Random().nextInt());
221.         FileOutputStream os = new FileOutputStream(output);
222.         BufferedOutputStream bout = new BufferedOutputStream(os);
223.         DataOutputStream dout=new DataOutputStream(bout);
224.    
225.         int a = -1;//= din1.readInt();
226.         int b = -1;//= din2.readInt();
227.         
228.         boolean finished = false;
229.         boolean emptyA = false;//
230.         int flag = 0;
231.         while (!finished) {
232.             if (flag != 1) {
233.                 try {
234.                     a = din1.readInt();
235.                 } catch (Exception e) {
236.                     emptyA = true;
237.                     break;
238.                 }
239.             }
240.             if (flag != 2) {
241.                 try {
242.                     b = din2.readInt();
243.                 } catch (Exception e) {
244.                     emptyA = false;
245.                     break;
246.                 }
247.             }
248.             if(a > b){
249.                 dout.writeInt(b);
250.                 flag = 1;
251.             }else if( a < b){
252.                 dout.writeInt(a);
253.                 flag = 2;
254.             }else if(a == b){
255.                 dout.write(a);
256.                 dout.write(b);
257.                 flag = 0;
258.             }
259.         }
260.         finished = false;
261.         if(emptyA){
262.             dout.writeInt(b);
263.             while(!finished){
264.                 try {
265.                     b = din2.readInt();
266.                 } catch (Exception e) {
267.                     break;
268.                 }
269.                 dout.writeInt(b);
270.             }
271.         }else{
272.             dout.writeInt(a);
273.             while(!finished){
274.                 try {
275.                     a = din1.readInt();
276.                 } catch (Exception e) {
277.                     break;
278.                 }
279.                 dout.writeInt(a);
280.             }
281.         }
282.         dout.close();
283.         os.close();
284.         bin1.close();
285.         bin2.close();
286.         bout.close();
287.         return output;
288.     }
290.   
291.     /**
292.      * @param args
293.      * @throws IOException
294.      */
295.     public static void main(String[] args) throws IOException {
296.               
297.         Random random = new Random(System.currentTimeMillis());
298.         FileOutputStream fw = new FileOutputStream(MAIN_FILE);
299.         BufferedOutputStream bout = new BufferedOutputStream(fw);
300.         DataOutputStream dout=new DataOutputStream(bout);  
301.         
302.         for (int i = 0; i < ITEM_COUNT; i++) {
303.             int ger = random.nextInt();
304.             ger = ger < 0 ? -ger : ger;
305.             dout.writeInt(ger);
306.         }
307.         dout.close();
308.         bout.close();
309.         fw.close();
310.         ExternalSort sort = new ExternalSort();
311.         System.out.println("Original:");
312.         long start = System.currentTimeMillis();
313.         sort.mSort(MAIN_FILE);
314.       
315.         
316.         long end = System.currentTimeMillis();
317.         System.out.println((end - start)/1000 + "s");
318.         recordFile((end - start)/1000 ,true);
319.     }
320.     private static void recordFile(long time,boolean isBuffer)
321.             throws FileNotFoundException, IOException {
322.         BufferedWriter bw = new BufferedWriter(new FileWriter("log",true));
323.         bw.write("FILE_COUNT = "+FILE_COUNT+";对"+ ITEM_COUNT + "条数据 "+ ITEM_COUNT*4/(1024*1204) +"MB排序耗时:" + time + "s ");
324.         if(isBuffer){
325.             bw.write("  使用缓冲:"+BUFFER_SIZE*4/(1024*1204) +"MB");
326.         }
327.         bw.newLine();
328.         bw.close();
329.     }
330. }

复制代码

nweuuu

不错的啊。