排序(11) 外部排序

发表于 | 分类于 | 阅读次数:

前面讨论的排序算法，都假定要排序的所有数据在内存中都同时可用，如数组。要对存储在外部文件中的数据排序，首先要将数据送入内存，然后对它们进行内部排序。然而，如果文件太大，那么文件中的所有数据不能都同时送入内存。在大型外部文件中对数据排序，称为外部排序(external sort)。

创建大文件

创建一个200万int值存储在一个名为largedata.dat的二进制文件中。使用下面的程序创建：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.io.*;
public class CreateLargeFile {
    public static void main(String[] args) throws Exception {
        DataOutputStream output = new DataOutputStream(
            new BufferedOutputStream(new FileOutputStream("largedata.dat")));
        for (int i = 0; i < 800004; i++){
            output.writeInt((int)(Math.random() * 1000000));
        }
        output.close();

        DataInputStream input = new DataInputStream(
            new BufferedInputStream(new FileInputStream("largedata.dat")));
        for (int i = 0; i < 100; i++) {
            System.out.print(input.readInt() + " ");
        }
        input.close();
    }
}

归并排序实现

实现阶段1

重复将数据从文件读入数组，并使用内部排序算法堆数组排序，然后将数据从数组输出到一个临时文件中。
下面的代码给出了一个方法，它从文件中读取每个数据段，并对分段进行排序，然后将排好序的分段存在一个心文件中。该方法返回分段的个数。

创建初始的有序分段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private static int initializeSegments
    (int segmentSize, String originalFile, String f1) throws Exception {
        int[] list =  new int[segmentSize];
        DataInputStream input = new DataInputStream(
                new BufferedInputStream(new FileInputStream(originalFile)));
        DataOutputStream output = new DataOutputStream(
                new BufferedOutputStream(new FileOutputStream(f1)));
        
        int numberOfSegments = 0;
        while (input.available() > 0) {
            numberOfSegments++;
            // 读取一段数据到数组中
            int i = 0;
            for ( ; input.available() > 0 && i < segmentSize; i++) {
                list[i] = input.readInt();
            }
            // 对数组排序
            java.util.Arrays.sort(list, 0, i);
            // 将数组中的数据写入到临时文件中
            for (int j = 0; j < i; j++) {
                output.writeInt(list[j]);
            }
        }
        input.close();
        output.close();
        //返回分段个数，除了最后一个分段的元素数可能较少外，其他分段都有
        //MAX_ARRAY_SIZE个元素
        return numberOfSegments;
    }

MAX_ARRAY_SIZE，数组的最大尺寸依赖于操作系统分配给JVM的内存大小。
假定数组的最大尺寸为100 000个int值，那么在临时文件中就是对每100 000个int值进行的排序。将它们标记为S1，S2，…，Sk，最后一段包含的数值可能会少于100 000个。

实现阶段2

将每对有序分段（比如S1，S2，…，Sk）归并到一个大一些的有序分段中，并将新分段存储到新的临时文件中。继续同样的过程直到得到仅仅一个有序分段。
每步归并都将两个有序分段归并成一个新分段。新段的元素数目是原来的两倍，因此，每次归并后分段的个数减少一半。
如果一个分段太大，它将不能放到内存的数组中。为了实现归并步骤，要将文件f1.dat中的一半数目的分段复制到临时文件f2.dat中。然后，将f1.dat中剩下的收割分段与f2.dat中的首个分段归并到名为f3.dat的临时文件中。
复制前半部分的分段

复制前半部分的分段
1
2
3
4
5
6
private static void copyHalfToF2(int numberOfSegments, int segmentSize,
                DataInputStream f1, DataOutputStream f2) throws Exception {
        for (int i = 0; i < (numberOfSegments / 2) * segmentSize; i++) {
            f2.writeInt(f1.readInt());
        }
}

归并所有分段

归并所有分段
1
2
3
4
5
6
7
8
9
10
11
private static void mergeSegments(int numberOfSegments, 
            int segmentSize, DataInputStream f1, DataInputStream f2, DataOutputStream f3) 
            throws Exception {
        for (int i = 0; i < numberOfSegments; i++) {
            mergeTwoSegments(segmentSize, f1, f2, f3);
        }
        
        while (f1.available() > 0) {
            f3.writeInt(f1.readInt());
        }
    }

归并两个阶段

归并两个阶段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
private static void mergeTwoSegments(int segmentSize, DataInputStream f1, 
            DataInputStream f2, DataOutputStream f3) throws Exception {
        
        int intFromF1 = f1.readInt();
        int intFromF2 = f2.readInt();
        int f1Count = 1;
        int f2Count = 1;
        
        while (true) {
            if (intFromF1 < intFromF2) {
                f3.writeInt(intFromF1);
                if (f1.available() == 0 || f1Count++ >= segmentSize) {
                    f3.writeInt(intFromF2);
                    break;
                }
                else {
                    intFromF1 = f1.readInt();
                }
            }
            else {
                f3.writeInt(intFromF2);
                if (f2.available() == 0 || f2Count++ >= segmentSize) {
                    f3.writeInt(intFromF1);
                    break;
                }
                else {
                    intFromF2 = f2.readInt();
                }
            }
        }
        while (f1.available() > 0 && f1Count++ <segmentSize) {
            f3.writeInt(f1.readInt());
        }
        while (f2.available() > 0 && f2Count++ < segmentSize) {
            f3.writeInt(f2.readInt());
        }
    }

结合两个阶段

完整代码

外部排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
package sorting;

import java.io.*;

public class SortLargeFile {

    public static final int MAX_ARRAY_SIZE = 43;
    public static final int BUFFER_SIZE = 100000;

    public static void main(String[] args) throws Exception {
        sort("largedata.dat", "sortedfile.dat");
        
        displayFile("sortedfile.dat");
    }    
    
    public static void sort(String sourcefile, String targetfile) throws Exception {
        int numberOfSegments = initializeSegments(MAX_ARRAY_SIZE, sourcefile, "f1.dat");        
        merge(numberOfSegments, MAX_ARRAY_SIZE, 
                "f1.dat", "f2.dat", "f3.dat", targetfile);        
    }
    
    private static int initializeSegments
    (int segmentSize, String originalFile, String f1) throws Exception {
        int[] list =  new int[segmentSize];
        DataInputStream input = new DataInputStream(
                new BufferedInputStream(new FileInputStream(originalFile)));
        DataOutputStream output = new DataOutputStream(
                new BufferedOutputStream(new FileOutputStream(f1)));
        
        int numberOfSegments = 0;
        while (input.available() > 0) {
            numberOfSegments++;
            int i = 0;
            for ( ; input.available() > 0 && i < segmentSize; i++) {
                list[i] = input.readInt();
            }
            java.util.Arrays.sort(list, 0, i);
            
            for (int j = 0; j < i; j++) {
                output.writeInt(list[j]);
            }
        }
        input.close();
        output.close();
        return numberOfSegments;
    }
    
    private static void merge(int numberOfSegments, int segmentSize,
            String f1, String f2, String f3, String targetfile) throws Exception {
        if (numberOfSegments > 1) {
            mergeOneStep(numberOfSegments, segmentSize, f1, f2, f3);
            merge((numberOfSegments + 1) / 2, segmentSize * 2, f3, f1, f2, targetfile);
        }
        else {
            File sortedFile = new File(targetfile);
            if (sortedFile.exists()) sortedFile.delete();
            new File(f1).renameTo(sortedFile);
        }
    }
    
    private static void mergeOneStep(int numberOfSegments, int segmentSize, 
            String f1, String f2, String f3) throws Exception {
        DataInputStream f1Input = new DataInputStream(
                new BufferedInputStream(new FileInputStream(f1), BUFFER_SIZE));
        DataOutputStream f2Output = new DataOutputStream(
                new BufferedOutputStream(new FileOutputStream(f2), BUFFER_SIZE));
        
        copyHalfToF2(numberOfSegments, segmentSize, f1Input, f2Output);
        f2Output.close();
        
        DataInputStream f2Input = new DataInputStream(
                new BufferedInputStream(new FileInputStream(f2), BUFFER_SIZE));
        DataOutputStream f3Output = new DataOutputStream(
                new BufferedOutputStream(new FileOutputStream(f3), BUFFER_SIZE));
        
        mergeSegments(numberOfSegments / 2, segmentSize, f1Input, f2Input, f3Output);        
        f1Input.close();
        f2Input.close();
        f3Output.close();                
    }    
    
    private static void copyHalfToF2(int numberOfSegments, int segmentSize,
                DataInputStream f1, DataOutputStream f2) throws Exception {
        for (int i = 0; i < (numberOfSegments / 2) * segmentSize; i++) {
            f2.writeInt(f1.readInt());
        }
    }
    
    
    private static void mergeSegments(int numberOfSegments, 
            int segmentSize, DataInputStream f1, DataInputStream f2, DataOutputStream f3) 
            throws Exception {
        for (int i = 0; i < numberOfSegments; i++) {
            mergeTwoSegments(segmentSize, f1, f2, f3);
        }
        
        while (f1.available() > 0) {
            f3.writeInt(f1.readInt());
        }
    }
    
    private static void mergeTwoSegments(int segmentSize, DataInputStream f1, 
            DataInputStream f2, DataOutputStream f3) throws Exception {
        
        int intFromF1 = f1.readInt();
        int intFromF2 = f2.readInt();
        int f1Count = 1;
        int f2Count = 1;        
        while (true) {
            if (intFromF1 < intFromF2) {
                f3.writeInt(intFromF1);
                if (f1.available() == 0 || f1Count++ >= segmentSize) {
                    f3.writeInt(intFromF2);
                    break;
                }
                else {
                    intFromF1 = f1.readInt();
                }
            }
            else {
                f3.writeInt(intFromF2);
                if (f2.available() == 0 || f2Count++ >= segmentSize) {
                    f3.writeInt(intFromF1);
                    break;
                }
                else {
                    intFromF2 = f2.readInt();
                }
            }
        }
        while (f1.available() > 0 && f1Count++ <segmentSize) {
            f3.writeInt(f1.readInt());
        }
        while (f2.available() > 0 && f2Count++ < segmentSize) {
            f3.writeInt(f2.readInt());
        }
    }
    
    
    public static void displayFile(String filename) {
        try {
            DataInputStream input = 
                    new DataInputStream(new FileInputStream(filename));
            for (int i = 0; i < 100; i++) {
                System.out.print(input.readInt() + " ");
            }
            input.close();
        }
        catch (IOException ex) {
            ex.printStackTrace();
        }
    }
}

外部排序复杂度

在外部排序中，主要开销是在IO上。假设n是文件中要排序的元素个数。在阶段1，从原始文件读取元素个数n，然后将它输出给一个临时文件。因此，阶段1的IO复杂度为O(n)。

对于阶段2，在第一个合并步骤之前，排好序的分段的个数为 n/c，其中c是MAX_ARRAY_SIZE。每一个合并步骤都会使分段的个数减半。因此，在第一次合并步骤之后，分段个数为 n/2c。
在第二次合并步骤之后，分段个数为 n/4c。 在第三次合并步骤之后，分段个数为 n/8c。
在第log(n/c)次合并步骤之后，分段个数减到1。因此，合并步骤的总数为log(n/c)。

在每次合并步骤中，从文件f1读取一半数量的分段，然后将它们写入到一个临时文件f2。合并f1中剩余的分段和f2中的分段。每一个合并步骤中IO的次数为O(n)。因为合并步骤的总数是log(n/c)，IO的总数是 O(n) * log(n/c) = O(nlogn)。
因此外部排序的复杂度是O(nlogn)

0%