准确的问题描述和适合问题数据的算法选择

对磁盘文件进行排序，文件包含最多一千万条记录，每条记录都是7位的整数，无其他相关数据，每个整数只出现一次，由于某种系统需要，只能提供1MB左右内存。由于是实时系统，最多运行几分钟就能给出回应，十秒钟是比较理想的运行时间。

准确的问题描述：

输入：一个包含n个正整数的文件，每个数都小于n，其中n=10 000 000。如果在输入文件中出现两个相同的整数就是致命错误。没有其他数据与该整数相关。

输出：按照升序输出的文件

约束：大约有1MB的内存空间可用，有充足的的磁盘空间，运行时间达到十秒以内不需要优化。

可以利用bit向量来表示整数集合，例如8bit长的维向量{0,0,1,1,0,1,0,1}，可以表示1-8的整数集合{3,4,6,8}

因此

1、初始化bit向量为全0　　2、读取磁盘数据i，并赋值bit[i] = 1　　3、扫描bit向量，if ( bit[i] == 1) print i

可行性：1MB = 1024 x 1024 x 8bit = 8388608bit，在大概1.25MB的条件下，就能够将所有数据采用bit向量完成表示

 1 #include <stdio.h>
 2 #define arrSpace 262144
 3 int arr[arrSpace];
 4 char fileName[20];
 5 
 6 void init(){
 7     int i;
 8     for(i=0; i < arrSpace; i++){
 9         arr[i] = 0;
10     }
11 }
12 
13 int main(void){
14     int n;
15     int i,j;
16     
17     scanf("%s",fileName);
18     FILE *in = fopen(fileName,"r");
19     FILE *out = fopen("outSort.txt","w");
20     
21     while(fscanf(in, "%d", &n) != EOF){
22         arr[n/32] = arr[n/32] | (1<<(n%32));
23     }
24 
25     for(i=0; i<arrSpace; i++){
26         for(j=0; j<32; j++){
27             if((arr[i] & (1<<j)) != 0){
28                 fprintf(out,"%d\n",i * 32 + j);       
29             }
30         }
31     }
32    
33    fclose(in);
34    fclose(out);
35 }

c语言中int类型占据32bit，因此262144长度的int数组为1MB

通过对读取的数据i对32求商和求余的运算，例如60/32=1，60%32=28，则应该把数组arr[1]的第28个bit置位1（一个int为0-31bit）

因此将整数1(int型)左移28位并与arr[1]进行逻辑或运算，可以将对应的bit置1

在最后输出的时候将1左移0-31位，并与arr做逻辑与运算如果结果为1，则说明数据中存在这个整数，将数据按照遍历顺序输出到文件就完成任务。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有