DGIM算法

  1 /*****************************************************
  2 copyright (C), 2014-2015, Lighting Studio. Co.,     Ltd. 
  3 File name：
  4 Author：Jerey_Jobs    Version:0.1    Date: 
  5 Description：
  6 Funcion List: 
  7 *****************************************************/
  8 
  9 #include <stdio.h>
 10 #include <stdlib.h>
 11 
 12 
 13 typedef struct
 14 {
 15     unsigned int count;
 16     unsigned int time_stamp;
 17 }BARR;//桶的属性
 18 /*函数声明*/
 19 int accurate(int *wins);
 20 void merge(BARR*, int);
 21 int estimate(BARR*);
 22 void judge_file_pointer_null(FILE *fp);
 23 
 24 int window;//窗口大小
 25 int size = 0;//桶的个数
 26 
 27 int main()
 28 {
 29     //BARR barrel[276];
 30     BARR *barrel = (BARR *)malloc(150000 * sizeof(BARR));
 31     int i = 0;
 32     int data;//接收0 1
 33     int *wins;//分配窗口大小的数组
 34 
 35     printf("please input window size:
");
 36     scanf("%d", &window);
 37     wins = (int *)malloc(window * sizeof(int));
 38     
 39     //FILE *fp = fopen("./01stream.txt", "r");//打开文件
 40     FILE *fp = fopen("./01stream_sample.txt", "r");//打开文件
 41 
 42     judge_file_pointer_null(fp);//文件打开是否失败
 43 
 44     int win_count = 0;//窗口计数
 45 
 46     while (!feof(fp))//扫描流中的数据
 47     {
 48         fscanf(fp, "%d", &data);
 49         win_count++;
 50 
 51         if (win_count < window)
 52         {
 53             wins[win_count] = data;
 54         }
 55         else//大于窗口时
 56         {
 57             wins[win_count % window] = data;//数组下标求模
 58         }
 59 #if 1
 60         if (data == 1)//放入桶中
 61         {
 62             barrel[size].time_stamp = win_count;
 63             barrel[size].count = 1;
 64             size++;
 65             merge(barrel, size);
 66         }
 67 #endif
 68     }
 69     printf("1 estimate count :%d
", estimate(barrel));
 70     printf("1 accurate count :%d
", accurate(wins));
 71 
 72     fclose(fp);
 73     free(wins);
 74     free(barrel);
 75     system("pause");
 76     return 0;
 77 }
 78 
 79 /*合并桶*/
 80 void merge(BARR barrel[], int length)
 81 {
 82     int i, j;
 83     int count = 0;//记录最多可以存在几个相同
 84     int tmp;
 85 #if 1
 86     //判断有没有桶过期
 87     if ((barrel[length - 1].time_stamp > window))
 88     {
 89         for (i = 0; i < length - 1; i++)
 90         {
 91             if (barrel[i].time_stamp < (barrel[length - 1].time_stamp - window))//
 92             {
 93                 barrel[i].count = 0;
 94             }
 95         }
 96     }
 97 #endif
 98 
 99     //合并
100     for (i = 0; i < length ; i++)
101     {    
102         count = 0;//记录窗口中的相同大小的桶的个数
103         for (j = i + 1; j < length ; j++)
104         {
105             if (barrel[i].count == barrel[j].count && (barrel[i].count != 0))
106             {
107                 count++;
108                 if (count == 1)
109                 {
110                     tmp = j;//保存时间较久的桶的下标
111                 }
112             }
113         }//end of inner for
114         if (count == 2)//如果窗口中有三个相同大小的桶则合并时间最久的两个桶
115         {
116                 barrel[i].count = 0;//时间戳小的舍弃，置零
117                 barrel[tmp].count *= 2;
118         }
119     }//end of external for
120 }
121 
122 /*DGIM估计窗口中1的数目*/
123 int estimate(BARR *barrel)
124 {
125     int i;
126     int estimate_count = 0;
127 
128     //打印窗口中的桶
129     for (i = 0; i < size; i++)
130     {
131         if (barrel[i].count != 0)
132         {
133             printf("%d, %d
",barrel[i].time_stamp, barrel[i].count);
134         }
135     }
136 
137     int count = 0;//计数第一个窗口内的值
138     for (i = 0; i < size; i++)
139     {
140         if (barrel[i].time_stamp >= 1000 - window && barrel[i].count != 0)
141         {
142             count++;
143             if (count == 1)
144             {
145                 estimate_count += 0.5 * barrel[i].count;//最小时间戳的桶值*0.5
146             }
147             else
148             {
149                 estimate_count +=  barrel[i].count;
150             }
151         }
152     }
153 
154     return estimate_count;
155 }
156 
157 /*精确计数窗口中1的数目*/
158 int accurate(int *wins)
159 {
160     int accurate_count = 0;
161     for (int i = 0; i < window; i++)
162     {
163         if (*(wins + i) == 1)
164         {
165             accurate_count++;
166         }
167     }
168     return accurate_count;
169 }
170 
171 /*判断文件指针是否为空*/
172 void judge_file_pointer_null(FILE *fp)
173 {
174     if (fp == NULL)
175     {
176         printf("file open failed!
");
177         exit(0);
178     }
179 }