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

2018-06-18 03:52:15来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

对磁盘文件进行排序,文件包含最多一千万条记录,每条记录都是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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C语言-struct&amp;typedef

下一篇:STM32高级定时器TIM1产生两路互补的PWM波(带死区)