首页 > 代码库 > 外部排序 实例

外部排序 实例

一 外部排序的基本思路

假设有一个72KB的文件,其中存储了18K个整数,磁盘中物理块的大小为4KB,将文件分成18组,每组刚好4KB。

首先通过18次内部排序,把18组数据排好序,得到初始的18个归并段R1~R18,每个归并段有1024个整数。

然后对这18个归并段使用4路平衡归并排序:

第1次归并:产生5个归并段

R11   R12    R13    R14    R15

其中

R11是由{R1,R2,R3,R4}中的数据合并而来

R12是由{R5,R6,R7,R8}中的数据合并而来

R13是由{R9,R10,R11,R12}中的数据合并而来

R14是由{R13,R14,R15,R16}中的数据合并而来

R15是由{R17,R18}中的数据合并而来

把这5个归并段的数据写入5个文件:

foo_1.dat    foo_2.dat    foo_3.dat     foo_4.dat     foo_5.dat

 

第2次归并:从第1次归并产生的5个文件中读取数据,合并,产生2个归并段

R21  R22

其中R21是由{R11,R12,R13,R14}中的数据合并而来

其中R22是由{R15}中的数据合并而来

把这2个归并段写入2个文件

bar_1.dat   bar_2.dat

 

第3次归并:从第2次归并产生的2个文件中读取数据,合并,产生1个归并段

R31

R31是由{R21,R22}中的数据合并而来

把这个文件写入1个文件

foo_1.dat

此即为最终排序好的文件。

 

二 使用败者树加快合并排序

外部排序最耗时间的操作时磁盘读写,对于有m个初始归并段,k路平衡的归并排序,磁盘读写次数为

|logkm|,可见增大k的值可以减少磁盘读写的次数,但增大k的值也会带来负面效应,即进行k路合并

的时候会增加算法复杂度,来看一个例子。

把n个整数分成k组,每组整数都已排序好,现在要把k组数据合并成1组排好序的整数,求算法复杂度

u1: xxxxxxxx

u2: xxxxxxxx

u3: xxxxxxxx

.......

uk: xxxxxxxx

算法的步骤是:每次从k个组中的首元素中选一个最小的数,加入到新组,这样每次都要比较k-1次,故

算法复杂度为O((n-1)*(k-1)),而如果使用败者树,可以在O(logk)的复杂度下得到最小的数,算法复杂

度将为O((n-1)*logk), 对于外部排序这种数据量超大的排序来说,这是一个不小的提高。

 

关于败者树的创建和调整,可以参考清华大学《数据结构-C语言版》

 

三 产生二进制测试数据

打开Linux终端,输入命令

dd if=/dev/urandom of=random.dat bs=1M count=512

 这样在当前目录下产生一个512M大的二进制文件,文件内的数据是随机的,读取文件,每4个字节

看成1个整数,相当于得到128M个随机整数。

 

四 程序实现

  1    2 #include <assert.h>    3 #include <fcntl.h>    4 #include <stdio.h>    5 #include <stdlib.h>    6 #include <string.h>    7 #include <unistd.h>    8     9 #include <sys/time.h>   10 #include <sys/types.h>   11 #include <sys/stat.h>   12    13 #define MAX_INT ~(1<<31)   14 #define MIN_INT 1<<31   15    16 //#define DEBUG   17    18 #ifdef DEBUG   19 #define debug(...) debug( __VA_ARGS__)    20 #else   21 #define debug(...)   22 #endif   23    24 #define MAX_WAYS 100   25    26 typedef struct run_t {   27     int *buf;       /* 输入缓冲区 */   28     int length;     /* 缓冲区当前有多少个数 */   29     int offset;     /* 缓冲区读到了文件的哪个位置 */   30     int idx;        /* 缓冲区的指针 */   31 } run_t;   32    33 static unsigned int K;              /* K路合并 */   34 static unsigned int BUF_PAGES;      /* 缓冲区有多少个page */   35 static unsigned int PAGE_SIZE;      /* page的大小 */   36 static unsigned int BUF_SIZE;       /* 缓冲区的大小, BUF_SIZE = BUF_PAGES*PAGE_SIZE */   37    38 static int *buffer;                 /* 输出缓冲区 */   39    40 static char input_prefix[] = "foo_";   41 static char output_prefix[] = "bar_";   42    43 static int ls[MAX_WAYS];            /* loser tree */   44    45 void swap(int *p, int *q);   46 int partition(int *a, int s, int t);   47 void quick_sort(int *a, int s, int t);   48 void adjust(run_t ** runs, int n, int s);   49 void create_loser_tree(run_t **runs, int n);   50 long get_time_usecs();   51 void k_merge(run_t** runs, char* input_prefix, int num_runs, int base, int n_merge);   52 void usage();   53    54    55 int main(int argc, char **argv)   56 {   57     char                filename[100];   58     unsigned int    data_size;   59     unsigned int    num_runs;               /* 这轮迭代时有多少个归并段 */   60     unsigned int    num_merges;             /* 这轮迭代后产生多少个归并段 num_merges = num_runs/K */   61     unsigned int    run_length;             /* 归并段的长度,指数级增长 */   62     unsigned int    num_runs_in_merge;      /* 一般每个merge由K个runs合并而来,但最后一个merge可能少于K个runs */   63     int                 fd, rv, i, j, bytes;   64     struct stat         sbuf;   65    66     if (argc != 3) {   67         usage();   68         return 0;   69     }   70     long start_usecs = get_time_usecs();   71    72     strcpy(filename, argv[1]);   73     fd = open(filename, O_RDONLY);   74     if (fd < 0) {   75         printf("can‘t open file %s\n", filename);   76         exit(0);   77     }   78     rv = fstat(fd, &sbuf);   79     data_size = sbuf.st_size;   80    81     K = atoi(argv[2]);   82     PAGE_SIZE = 4096;                           /* page = 4KB */   83     BUF_PAGES = 32;   84     BUF_SIZE = PAGE_SIZE*BUF_PAGES;   85     num_runs = data_size / PAGE_SIZE;           /* 初始时的归并段数量,每个归并段有4096 byte, 即1024个整数 */   86     buffer = (int *)malloc(BUF_SIZE);   87    88     run_length = 1;   89     run_t **runs = (run_t **)malloc(sizeof(run_t *)*(K+1));   90     for (i = 0; i < K; i++) {   91         runs[i] = (run_t *)malloc(sizeof(run_t));   92         runs[i]->buf = (int *)calloc(1, BUF_SIZE+4);   93     }   94     while (num_runs > 1) {   95         num_merges = num_runs / K;   96         int left_runs = num_runs % K;   97         if(left_runs > 0) num_merges++;   98         for (i = 0; i < num_merges; i++) {   99             num_runs_in_merge = K;  100             if ((i+1) == num_merges && left_runs > 0) {  101                 num_runs_in_merge = left_runs;  102             }  103             int base = 0;  104             printf("Merge %d of %d,%d ways\n", i, num_merges, num_runs_in_merge);  105             for (j = 0; j < num_runs_in_merge; j++) {  106                 if (run_length == 1) {  107                     base = 1;  108                     bytes = read(fd, runs[j]->buf, PAGE_SIZE);  109                     runs[j]->length = bytes/sizeof(int);  110                     quick_sort(runs[j]->buf, 0, runs[j]->length-1);  111                 } else {  112                     snprintf(filename, 20, "%s%d.dat", input_prefix, i*K+j);  113                     int infd = open(filename, O_RDONLY);  114                     bytes = read(infd, runs[j]->buf, BUF_SIZE);  115                     runs[j]->length = bytes/sizeof(int);  116                     close(infd);      117                 }  118                 runs[j]->idx = 0;  119                 runs[j]->offset = bytes;  120             }  121             k_merge(runs, input_prefix, num_runs_in_merge, base, i);  122         }  123   124         strcpy(filename, output_prefix);  125         strcpy(output_prefix, input_prefix);  126         strcpy(input_prefix, filename);  127   128         run_length *= K;  129         num_runs = num_merges;  130     }  131   132     for (i = 0; i < K; i++) {  133         free(runs[i]->buf);  134         free(runs[i]);  135     }  136     free(runs);  137     free(buffer);  138     close(fd);  139   140     long end_usecs = get_time_usecs();  141     double secs = (double)(end_usecs - start_usecs) / (double)1000000;  142     printf("Sorting took %.02f seconds.\n", secs);  143     printf("sorting result saved in %s%d.dat.\n", input_prefix, 0);  144   145     return 0;  146 }  147   148 void k_merge(run_t** runs, char* input_prefix, int num_runs, int base, int n_merge)  149 {  150     int bp, bytes, output_fd;  151     int live_runs = num_runs;  152     run_t *mr;  153     char filename[20];  154   155     bp = 0;  156     create_loser_tree(runs, num_runs);  157   158     snprintf(filename, 100, "%s%d.dat", output_prefix, n_merge);  159     output_fd = open(filename, O_CREAT|O_WRONLY|O_TRUNC,   160             S_IRWXU|S_IRWXG);  161     if (output_fd < 0) {  162         printf("create file %s fail\n", filename);  163         exit(0);  164     }  165   166     while (live_runs > 0) {  167         mr = runs[ls[0]];  168         buffer[bp++] = mr->buf[mr->idx++];  169         // 输出缓冲区已满  170         if (bp*4 == BUF_SIZE) {  171             bytes = write(output_fd, buffer, BUF_SIZE);  172             bp = 0;  173         }  174         // mr的输入缓冲区用完  175         if (mr->idx == mr->length) {  176             snprintf(filename, 20, "%s%d.dat", input_prefix, ls[0]+n_merge*K);  177             if (base) {  178                 mr->buf[mr->idx] = MAX_INT;  179                 live_runs--;  180             } else {  181                 int fd = open(filename, O_RDONLY);  182                 lseek(fd, mr->offset, SEEK_SET);  183                 bytes = read(fd, mr->buf, BUF_SIZE);  184                 close(fd);  185                 if (bytes == 0) {  186                     mr->buf[mr->idx] = MAX_INT;  187                     live_runs--;  188                 }  189                 else {  190                     mr->length = bytes/sizeof(int);  191                     mr->offset += bytes;  192                     mr->idx = 0;  193                 }  194             }  195         }  196         adjust(runs, num_runs, ls[0]);  197     }  198     bytes = write(output_fd, buffer, bp*4);  199     if (bytes != bp*4) {  200         printf("!!!!!! Write Error !!!!!!!!!\n");  201         exit(0);  202     }  203     close(output_fd);  204 }  205   206 long get_time_usecs()  207 {  208     struct timeval time;  209     struct timezone tz;  210     memset(&tz, \0, sizeof(struct timezone));  211     gettimeofday(&time, &tz);  212     long usecs = time.tv_sec*1000000 + time.tv_usec;  213   214     return usecs;  215 }  216   217 void swap(int *p, int *q)  218 {  219     int     tmp;  220   221     tmp = *p;  222     *p = *q;  223     *q = tmp;  224 }  225   226 int partition(int *a, int s, int t)  227 {  228     int     i, j;   /* i用来遍历a[s]...a[t-1], j指向大于x部分的第一个元素 */  229   230     for (i = j = s; i < t; i++) {  231         if (a[i] < a[t]) {  232             swap(a+i, a+j);  233             j++;  234         }  235     }  236     swap(a+j, a+t);  237   238     return j;  239 }  240   241 void quick_sort(int *a, int s, int t)  242 {  243     int     p;  244   245     if (s < t) {  246         p = partition(a, s, t);  247         quick_sort(a, s, p-1);  248         quick_sort(a, p+1, t);  249     }  250 }  251   252 void adjust(run_t ** runs, int n, int s)  253 {  254     int t, tmp;  255   256     t = (s+n)/2;  257     while (t > 0) {  258         if (s == -1) {  259             break;  260         }  261         if (ls[t] == -1 || runs[s]->buf[runs[s]->idx] > runs[ls[t]]->buf[runs[ls[t]]->idx]) {  262             tmp = s;  263             s = ls[t];  264             ls[t] = tmp;  265         }  266         t >>= 1;  267     }  268     ls[0] = s;  269 }  270   271 void create_loser_tree(run_t **runs, int n)  272 {  273     int     i;  274   275     for (i = 0; i < n; i++) {  276         ls[i] = -1;  277     }  278     for (i = n-1; i >= 0; i--) {  279         adjust(runs, n, i);  280     }  281 }  282   283 void usage()  284 {  285     printf("sort <filename> <K-ways>\n");  286     printf("\tfilename: filename of file to be sorted\n");  287     printf("\tK-ways: how many ways to merge\n");  288     exit(1);  289 }  

 

 

五 编译运行

gcc sort.c -o sort -g

./sort random.dat 64

以64路平衡归并对random.dat内的数据进行外部排序。在I5处理器,4G内存的硬件环境下,实验结果如下

文件大小    耗时

128M        14.72 秒

256M        30.89 秒

512M        71.65 秒

1G             169.18秒

 

六 读取二进制文件,查看排序结果   

 1 #include <assert.h>   2 #include <fcntl.h>   3 #include <stdio.h>   4 #include <stdlib.h>   5 #include <string.h>   6 #include <unistd.h>   7    8 #include <sys/time.h>   9 #include <sys/types.h>  10 #include <sys/stat.h>  11   12 int main(int argc, char **argv)  13 {  14     char *filename = argv[1];  15     int *buffer = (int *)malloc(1<<20);  16     struct stat     sbuf;  17     int rv, data_size, i, bytes, fd;  18   19     fd = open(filename, O_RDONLY);  20     if (fd < 0) {  21         printf("%s not found!\n", filename);  22         exit(0);  23     }  24     rv = fstat(fd, &sbuf);  25     data_size = sbuf.st_size;  26   27     bytes = read(fd, buffer, data_size);  28     for (i = 0; i < bytes/4; i++) {  29         printf("%d ", buffer[i]);  30         if ((i+1) % 10 == 0) {  31             printf("\n");  32         }  33     }  34     printf("\n");  35     close(fd);  36     free(buffer);  37     return 0;  38 }  

 

转自:http://blog.csdn.net/naturebe/article/details/8080083

 

外部排序 实例