对磁盘文件进行排序，文件包含最多一千万条记录，每条记录都是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,"%dn",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，则说明数据中存在这个整数，将数据按照遍历顺序输出到文件就完成任务。
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
