用过程语言实现group by cube的代码挑战赛

〇〇

如果每个属性都没有函数依赖（例子中用互质数序列），那么
第一层的行数=min(pi count(unique c(i)),count(*))
后边层的行数=？
如果知道这些，那么可以预先估计分配内存，在创建节点的同时插入汇总数据（达到newkid的代码效果）
再评估后边层是从第1层直接产生，还是多次rollup,应该能达到一个满意值

猜测 插入/读取map都是O(log(2,N))

〇〇

FILE *fp=fopen("out.txt","wb");
fprintf(fp,"gid,c1,c2,c3,c4,count,sum\n");
for (int i=0;i<c_2;i++)
{
        y=i;
        fprintf(fp,"%d,%d,%d,%d,%d,%d,%I64d\n",
0,(k[y]>>24),((k[y]>>16)&255),((k[y]>>8)&255),(k[y]&255),C[y],v2[y]);

}
for (int i=0;i<c-c_2;i++)
{
        y=i;
        fprintf(fp,"%d,%d,%d,%d,%d,%d,%I64d\n",
(16+((k2[y]>>24)>>4))&15,(k2[y]>>24)&15,((k2[y]>>16)&255),((k2[y]>>8)&255),(k2[y]&255),C2[y],v3[y]);

}
fclose(fp);
printf("保存到文件%dms,recn=%d,每毫秒写%d行\n",clock()-t,c,c/(clock()-t));

~~~~~~~~~~~
4,5,67,114,152760
申请源表内存0ms
填充源表数据78ms,recn=0,每毫秒12820行
新建一层节点203ms,recn=152760,每毫秒读4926行,每毫秒写752节点
申请一层内存0ms
写入一层数据156ms,recn=152760,每毫秒读6410行，每毫秒写979行
新建后面节点250ms,recn=234600,每毫秒读611行key,每毫秒写327节点
申请后面内存0ms
汇总后面节点266ms,recn=234600,每毫秒读574行，每毫秒写307行
保存到文件203ms,recn=234600,每毫秒写1155行
释放所有动态内存0ms
9,19,109,114,2124846
申请源表内存0ms
填充源表数据16ms,recn=0,每毫秒62500行
新建一层节点500ms,recn=941716,每毫秒读2000行,每毫秒写1883节点
申请一层内存15ms
写入一层数据266ms,recn=941716,每毫秒读3759行，每毫秒写3540行
新建后面节点2047ms,recn=1346870,每毫秒读460行key,每毫秒写197节点
申请后面内存0ms
汇总后面节点2328ms,recn=1346870,每毫秒读404行，每毫秒写174行
保存到文件1672ms,recn=1346870,每毫秒写805行
释放所有动态内存0ms
9,97,119,114,11843118
申请源表内存0ms
填充源表数据15ms,recn=0,每毫秒66666行
新建一层节点438ms,recn=1000000,每毫秒读2283行,每毫秒写2283节点
申请一层内存0ms
写入一层数据219ms,recn=1000000,每毫秒读4566行，每毫秒写4566行
新建后面节点3062ms,recn=2299600,每毫秒读326行key,每毫秒写424节点
申请后面内存0ms
汇总后面节点3406ms,recn=2299600,每毫秒读293行，每毫秒写381行
保存到文件2813ms,recn=2299600,每毫秒写817行
释放所有动态内存15ms

〇〇

………………………………………………………………………………
用读入csv文件模拟读表
FILE *fp=fopen("in.txt","rb");
for (int i=0;i<1E6L;i++)
{
     /*   int j=i+1;
        c1[i]=j%s[r][0];
        c2[i]=j%s[r][1];
        c3[i]=j%s[r][2];
        c4[i]=(j%13?j%113:127);
        v1[i]=j;*/
        fscanf(fp,"%d,%d,%d,%d,%d\n",&c1[i],&c2[i],&c3[i],&c4[i],&v1[i]);
        //fprintf(fp,"%d,%d,%d,%d,%d\n",c1[i],c2[i],c3[i],c4[i],v1[i]);       

}
fclose(fp);

D:\lt\dl>map5
9,97,119,114,11843118
申请源表内存0ms
填充源表数据531ms,recn=0,每毫秒1883行
新建一层节点406ms,recn=1000000,每毫秒读2463行,每毫秒写2463节点
申请一层内存16ms
写入一层数据203ms,recn=1000000,每毫秒读4926行，每毫秒写4926行
新建后面节点2953ms,recn=2299600,每毫秒读338行key,每毫秒写440节点
申请后面内存0ms
汇总后面节点3375ms,recn=2299600,每毫秒读296行，每毫秒写385行
保存到文件2250ms,recn=2299600,每毫秒写1022行
释放所有动态内存0ms

D:\lt\dl>dir in.txt out.txt


2010-02-27  20:16        17,962,833 in.txt

2010-02-27  20:20        52,396,878 out.txt

nyfor

研究的神了！

〇〇

cube太通用，所以牺牲了效率，如果专用于特定需求，自己做可能会更好

〇〇

用newkid多次rollup的办法，又减少了1.5秒

1. 
   
2. /* compiled by cl of vc2003*/
   
3. #include <time.h>
   
4. #include <stdio.h>
   
5. #include <stdlib.h>
   
6. #include <map>
   
7. #include <iostream>
   
8. #define add_key {if((key_recn.find(key))== key_recn.end())key_recn[key]=c++;}
   
9. #define addkey {if((key_recn2.find(key))== key_recn2.end())key_recn2[key]=c++;}
   
10. #define adkey(i) {if((key_recn2[i].find(key))== key_recn2[i].end())key_recn2[i][key]=c++;}
    
11. 
    
12. #define __int64 long long
    
13. using namespace std;
    
14. struct ltstr
    
15. {
    
16.   bool operator()(const char* s1, const char* s2) const
    
17.   {
    
18.     return strcmp(s1, s2) < 0;
    
19.   }
    
20. };
    
21. struct ltint
    
22. {
    
23.   bool operator()(const int s1, const int s2) const
    
24.   {
    
25.     return (s1<s2) ;
    
26.   }
    
27. };
    
28. int main()
    
29. {
    
30. int s[3][3]={ {4,5,67},{9,19,109},{9,97,119}};
    
31. //printf("%d,%d",t[0][1],t[1][2]);
    
32. //return 0;
    
33. for(int r=2;r<3;r++)
    
34. {       
    
35. long t=clock();
    
36. printf("%d,%d,%d,114,%d\n",s[r][0],s[r][1],s[r][2],s[r][0]*s[r][1]*s[r][2]*114);
    
37. char* c1=(char*)malloc(1E6L);
    
38. char* c2=(char*)malloc(1E6L);
    
39. char* c3=(char*)malloc(1E6L);
    
40. char* c4=(char*)malloc(1E6L);
    
41. int*  v1=(int* )malloc(4E6L);
    
42. 
    
43. printf("申请源表内存%dms\n",clock()-t);
    
44. t=clock();
    
45. 
    
46. __int64* v2;//store sum(v1);
    
47. //FILE *fp=fopen("in.txt","wb");
    
48. //FILE *fp=fopen("in.txt","rb");
    
49. for (int i=0;i<1E6L;i++)
    
50. {
    
51.         int j=i+1;
    
52.         c1[i]=j%s[r][0];
    
53.         c2[i]=j%s[r][1];
    
54.         c3[i]=j%s[r][2];
    
55.         c4[i]=(j%13?j%113:127);
    
56.         v1[i]=j;
    
57.         //fscanf(fp,"%d,%d,%d,%d,%d\n",&c1[i],&c2[i],&c3[i],&c4[i],&v1[i]);
    
58.         //fprintf(fp,"%d,%d,%d,%d,%d\n",c1[i],c2[i],c3[i],c4[i],v1[i]);       
    
59. 
    
60. }
    
61. //fclose(fp);
    
62. //return 1;
    
63. map<const int, int, ltint> key_recn;
    
64. map<const int, int, ltint> key_recn2[16];
    
65. int c=0;
    
66. printf("填充源表数据%dms,recn=%d,每毫秒%d行\n",clock()-t,c,(long)1E6/(clock()-t));
    
67. t=clock();
    
68. 
    
69. for (int i=0;i<1E6L;i++)
    
70. {
    
71.         int key=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
72.         //printf("key=%d\n",key);
    
73.         add_key;
    
74. 
    
75. }
    
76. 
    
77. printf("新建一层节点%dms,recn=%d,每毫秒读%d行,每毫秒写%d节点\n",clock()-t,c,(long)1E6/(clock()-t),c/(clock()-t));
    
78. t=clock();
    
79. int *C=(int*)malloc(c*4);//store count(c1)
    
80. int *k=(int*)malloc(c*4);//store key
    
81. 
    
82. v2=(__int64*)malloc(c*8);
    
83. 
    
84. memset(C,0,c*4); //need?
    
85. memset(v2,0,c*8);
    
86. printf("申请一层内存%dms\n",clock()-t);
    
87. t=clock();
    
88. 
    
89. 
    
90. for (int i=0;i<1E6L;i++)
    
91. {
    
92. int recn=key_recn[(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i]];
    
93. k[recn]=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
94. C[recn]++;
    
95. v2[recn]=v2[recn]+v1[i];
    
96. 
    
97. }
    
98. printf("写入一层数据%dms,recn=%d,每毫秒读%d行，每毫秒写%d行\n",clock()-t,c,(long)1E6/(clock()-t),c/(clock()-t));
    
99. t=clock();
    
100. int c_2=c;
     
101. for (int i=0;i<c_2;i++)
     
102. {
     
103.         int key=(k[i]&0xFFFFFF)+((0x80+15)<<24);//set c1 null ,gid=8
     
104.         adkey(8);
     
105. 
     
106.         key=(k[i]&0xFF00FFFF)+((0x40)<<24)+(127<<16);//set c2 null,gid=4
     
107.         adkey(4);
     
108. 
     
109.         key=(k[i]&0xFFFF00FF)+((0x20)<<24)+(127<<8);//set c3 null,gid=2
     
110.         adkey(2);
     
111. 
     
112.         key=(k[i]&0xFFFFFF00)+((0x10)<<24)+(127);//set c4 null,gid=1
     
113.         adkey(1);
     
114. 
     
115. /*
     
116.         key=(k[i]&0xFFFF00)+((0x90+15)<<24)+(127);//set c1,c4 null ,gid=9
     
117.         adkey(9);
     
118. 
     
119.         key=(k[i]&0xFF00FF00)+((0x50)<<24)+(127<<16)+(127);//set c2,c4 null,gid=5
     
120.         adkey(5);
     
121. 
     
122.         key=(k[i]&0xFFFF0000)+((0x30)<<24)+(127<<8)+(127);//set c3,c4 null,gid=3
     
123.         adkey(3);
     
124. 
     
125.         key=(k[i]&0xFF0000FF)+((0x60)<<24)+(127<<16)+(127<<8);//set c2,c3 null,gid=6
     
126.         adkey(6);
     
127. 
     
128.         key=(k[i]&0x00FF00FF)+((0xA0+15)<<24)+(127<<8);//set c1,c3 null,gid=10
     
129.         adkey(10);
     
130. 
     
131.         key=(k[i]&0xFFFF)+((0xC0+15)<<24)+(127<<16);//set c1,c2 null,gid=12
     
132.         adkey(12);
     
133. 
     
134.         key=(k[i]&0xFF00)+((0xD0+15)<<24)+(127<<16)+(127);//set c1,c2,c4 null,gid=13
     
135.         adkey(13);
     
136. 
     
137.         key=(k[i]&0xFF)+((0xE0+15)<<24)+(127<<16)+(127<<8);//set c1,c2,c3 null,gid=14
     
138.         adkey(14);
     
139. 
     
140.         key=(k[i]&0xFF0000)+((0xB0+15)<<24)+(127<<8)+(127);//set c1,c3,c4 null,gid=11
     
141.         adkey(11);
     
142. 
     
143.         key=(k[i]&0xFF000000)+((0x70)<<24)+(127<<16)+(127<<8)+(127);//set c2,c3,c4 null,gid=7
     
144.         adkey(7);
     
145. 
     
146.         key=((0xF0+15)<<24)+(127<<16)+(127<<8)+(127);//set c1,c2,c3,c4 null,gid=15
     
147.         adkey(15);
     
148. */        
     
149. }
     
150. map<const int, int,ltint>::iterator iter;
     
151. for(int i=1;i<7;i++)
     
152. {
     
153. if (i==1)       
     
154. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
155. {
     
156.         int key=((iter->first)&0x0FFF0000)+((0x30)<<24)+(127<<8)+(127);//set c3,c4 null,gid=3
     
157.         adkey(3);
     
158. 
     
159.         key=((iter->first)&0xFFFF00)+((0x90+15)<<24)+(127);//set c1,c4 null ,gid=9
     
160.         adkey(9);
     
161. 
     
162.         key=((iter->first)&0x0F00FF00)+((0x50)<<24)+(127<<16)+(127);//set c2,c4 null,gid=5
     
163.         adkey(5);
     
164. 
     
165. }
     
166. if(i==2)
     
167. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
168. {
     
169.         int key=((iter->first)&0x00FF00FF)+((0xA0+15)<<24)+(127<<8);//set c1,c3 null,gid=10
     
170.         adkey(10);
     
171. }
     
172. if(i==4)
     
173. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
174. {
     
175.         int key=((iter->first)&0x0F0000FF)+((0x60)<<24)+(127<<16)+(127<<8);//set c2,c3 null,gid=6
     
176.         adkey(6);
     
177. 
     
178. 
     
179.         key=((iter->first)&0xFFFF)+((0xC0+15)<<24)+(127<<16);//set c1,c2 null,gid=12
     
180.         adkey(12);
     
181. }
     
182. if(i==3)
     
183. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
184. {
     
185.         int key=((iter->first)&0xFF0000)+((0xB0+15)<<24)+(127<<8)+(127);//set c1,c3,c4 null,gid=11
     
186.         adkey(11);
     
187. 
     
188.         key=((iter->first)&0x0F000000)+((0x70)<<24)+(127<<16)+(127<<8)+(127);//set c2,c3,c4 null,gid=7
     
189.         adkey(7);
     
190. }
     
191. if(i==5)
     
192. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
193. {
     
194.         int key=((iter->first)&0xFF00)+((0xD0+15)<<24)+(127<<16)+(127);//set c1,c2,c4 null,gid=13
     
195.         adkey(13);
     
196. }
     
197. if(i==6)
     
198. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
199. {
     
200.         int key=((iter->first)&0xFF)+((0xE0+15)<<24)+(127<<16)+(127<<8);//set c1,c2,c3 null,gid=14
     
201.         adkey(14);
     
202. }
     
203. }
     
204.         int key=((0xF0+15)<<24)+(127<<16)+(127<<8)+(127);//set c1,c2,c3,c4 null,gid=15
     
205.         adkey(15);
     
206. 
     
207. printf("新建后面节点%dms,recn=%d,每毫秒读%d行key,每毫秒写%d节点\n",clock()-t,c,c_2/(clock()-t),(c-c_2)/(clock()-t));
     
208. for(int i=0;i<16;i++)
     
209. {
     
210.         printf("%d,first=%0X,renc=%d\n",i,key_recn2[i].begin()->first,key_recn2[i][key_recn2[i].begin()->first]);
     
211.         }
     
212. t=clock();
     
213. int o[15]={8,4,2,1,9,5,3,6,10,12,13,14,11,7,15};
     
214. int mask[15]={
     
215. 0x00FFFFFF,
     
216. 0xFF00FFFF,
     
217. 0xFFFF00FF,
     
218. 0xFFFFFF00,
     
219. 0x00FFFF00,
     
220. 0xFF00FF00,
     
221. 0xFFFF0000,
     
222. 0xFF0000FF,
     
223. 0x00FF00FF,
     
224. 0x0000FFFF,
     
225. 0x0000FF00,
     
226. 0x000000FF,
     
227. 0x00FF0000,
     
228. 0xFF000000,
     
229. 0x00000000};
     
230. 
     
231. int null[15]={
     
232. ((0x80+15)<<24),
     
233. ((0x40)<<24)+(127<<16),
     
234. ((0x20)<<24)+(127<<8),
     
235. ((0x10)<<24)+(127),
     
236. ((0x90+15)<<24)+(127),
     
237. ((0x50)<<24)+(127<<16)+(127),
     
238. ((0x30)<<24)+(127<<8)+(127),
     
239. ((0x60)<<24)+(127<<16)+(127<<8),
     
240. ((0xA0+15)<<24)+(127<<8),
     
241. ((0xC0+15)<<24)+(127<<16),
     
242. ((0xD0+15)<<24)+(127<<16)+(127),
     
243. ((0xE0+15)<<24)+(127<<16)+(127<<8),
     
244. ((0xB0+15)<<24)+(127<<8)+(127),
     
245. ((0x70)<<24)+(127<<16)+(127<<8)+(127),
     
246. ((0xF0+15)<<24)+(127<<16)+(127<<8)+(127)
     
247. };
     
248. 
     
249. 
     
250. int *C2=(int*)malloc((c-c_2)*4);//store count(c1)
     
251. int *k2=(int*)malloc((c-c_2)*4);//store key
     
252. __int64* v3=(__int64*)malloc((c-c_2)*8);
     
253. 
     
254. memset(C2,0,(c-c_2)*4); //need?
     
255. memset(v3,0,(c-c_2)*8);
     
256. printf("申请后面内存%dms,%d\n",clock()-t,c);
     
257. t=clock();
     
258. //goto f;
     
259. int y=0;
     
260. int f[15];
     
261. memset(f,0,15*4);
     
262. 
     
263. for (int i=0;i<c_2;i++)
     
264. {
     
265. for(int j=0;j<15;j++)
     
266. {
     
267.         //int key=(k[i]&mask[j])+null[j];
     
268.         //if(key_recn2[o[j]].find(key)!= key_recn2[o[j]].end())
     
269.         {f[j]++;
     
270. int recn=key_recn2[o[j]][(k[i]&mask[j])+null[j]]-c_2;
     
271. k2[recn]=(k[i]&mask[j])+null[j];
     
272. C2[recn]+=C[i];
     
273. v3[recn]=v3[recn]+v2[i];
     
274. 
     
275. y=recn;
     
276. }
     
277. }
     
278. }
     
279. printf("汇总后面节点%dms,recn=%d,每毫秒读%d行，每毫秒写%d行\n",clock()-t,c,c_2/(clock()-t),(c-c_2)/(clock()-t));
     
280. t=clock();
     
281. /*
     
282. printf("%fms,recn=%d,c1=%d,c2=%d,c3=%d,c4=%d,count=%d,sum=%I64d\n",(float)(clock()-t)/CLOCKS_PER_SEC ,c,
     
283. (k2[y]>>24),((k2[y]>>16)&255),((k2[y]>>8)&255),(k2[y]&255),C2[y],v3[y]);
     
284. */
     
285. 
     
286. FILE *fp=fopen("out.txt","wb");
     
287. 
     
288. //fp=fopen("out.txt","wb");
     
289. fprintf(fp,"gid,c1,c2,c3,c4,count,sum\n");
     
290. for (int i=0;i<c_2;i++)
     
291. {
     
292.         y=i;
     
293.         fprintf(fp,"%d,%d,%d,%d,%d,%d,%I64d\n",
     
294. 0,(k[y]>>24),((k[y]>>16)&255),((k[y]>>8)&255),(k[y]&255),C[y],v2[y]);
     
295. 
     
296. }
     
297. 
     
298. for (int i=0;i<c-c_2;i++)
     
299. {
     
300.         y=i;
     
301.         fprintf(fp,"%d,%d,%d,%d,%d,%d,%I64d\n",
     
302. (16+((k2[y]>>24)>>4))&15,(k2[y]>>24)&15,((k2[y]>>16)&255),((k2[y]>>8)&255),(k2[y]&255),C2[y],v3[y]);
     
303. 
     
304. }
     
305. fclose(fp);
     
306. printf("保存到文件%dms,recn=%d,每毫秒写%d行\n",clock()-t,c,c/(clock()-t));
     
307. t=clock();
     
308. 
     
309. f:
     
310. free(c1);
     
311. free(c2);
     
312. free(c3);
     
313. free(c4);
     
314. free(v1);
     
315. free(v2);
     
316. free(C);
     
317. free(k);
     
318. free(C2);
     
319. free(k2);
     
320. free(v3);
     
321. printf("释放所有动态内存%dms,%d\n",clock()-t,c);
     
322. for(int i=0;i<15;i++)
     
323. printf("%d,%d\n",i,f[i]);
     
324. 
     
325. 
     
326. 
     
327. }
     
328. return 0;
     
329. }
     

复制代码

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
D:\lt\dl>map6
9,97,119,114,11843118
申请源表内存0ms
填充源表数据62ms,recn=0,每毫秒16129行
新建一层节点453ms,recn=1000000,每毫秒读2207行,每毫秒写2207节点
申请一层内存0ms
写入一层数据219ms,recn=1000000,每毫秒读4566行，每毫秒写4566行
新建后面节点1547ms,recn=2299600,每毫秒读646行key,每毫秒写840节点
0,first=3D454D41,renc=0
1,first=1000007F,renc=1397076
2,first=20007F00,renc=1381362
3,first=30007F7F,renc=2260123
4,first=407F0000,renc=1431349
5,first=507F007F,renc=2260125
6,first=607F7F00,renc=2284774
7,first=707F7F7F,renc=2284669
8,first=8F000001,renc=1549286
9,first=9F00007F,renc=2260124
10,first=AF007F00,renc=2273610
11,first=BF007F7F,renc=2284668
12,first=CF7F0000,renc=2284775
13,first=DF7F007F,renc=2299366
14,first=EF7F7F00,renc=2299485
15,first=FF7F7F7F,renc=2299599
申请后面内存16ms,2299600
汇总后面节点3172ms,recn=2299600,每毫秒读315行，每毫秒写409行
保存到文件2656ms,recn=2299600,每毫秒写865行
释放所有动态内存16ms,2299600
0,1000000
1,1000000
2,1000000
3,1000000
4,1000000
5,1000000
6,1000000
7,1000000
8,1000000
9,1000000
10,1000000
11,1000000
12,1000000
13,1000000
14,1000000

D:\lt\dl>dir out.txt

2010-02-28  12:36        52,396,878 out.txt

〇〇

用newkid多次rollup的办法从中间结果汇总，又减少了1.5秒

1. 
   
2. /* compiled by cl of vc2003*/
   
3. #include <time.h>
   
4. #include <stdio.h>
   
5. #include <stdlib.h>
   
6. #include <map>
   
7. #include <iostream>
   
8. #define add_key {if((key_recn.find(key))== key_recn.end())key_recn[key]=c++;}
   
9. #define addkey {if((key_recn2.find(key))== key_recn2.end())key_recn2[key]=c++;}
   
10. #define adkey(i) {if((key_recn2[i].find(key))== key_recn2[i].end())key_recn2[i][key]=c++;}
    
11. #define sumkey(i) {f[i]++;int recn=key_recn2[i][key]-c_2;k2[recn]=key;C2[recn]+=C2[(iter->second)-c_2];v3[recn]+=v3[(iter->second)-c_2];}
    
12. #define __int64 long long
    
13. using namespace std;
    
14. struct ltstr
    
15. {
    
16.   bool operator()(const char* s1, const char* s2) const
    
17.   {
    
18.     return strcmp(s1, s2) < 0;
    
19.   }
    
20. };
    
21. struct ltint
    
22. {
    
23.   bool operator()(const int s1, const int s2) const
    
24.   {
    
25.     return (s1<s2) ;
    
26.   }
    
27. };
    
28. int main()
    
29. {
    
30. int s[3][3]={ {4,5,67},{9,19,109},{9,97,119}};
    
31. //printf("%d,%d",t[0][1],t[1][2]);
    
32. //return 0;
    
33. for(int r=2;r<3;r++)
    
34. {       
    
35. long t=clock();
    
36. printf("%d,%d,%d,114,%d\n",s[r][0],s[r][1],s[r][2],s[r][0]*s[r][1]*s[r][2]*114);
    
37. char* c1=(char*)malloc(1E6L);
    
38. char* c2=(char*)malloc(1E6L);
    
39. char* c3=(char*)malloc(1E6L);
    
40. char* c4=(char*)malloc(1E6L);
    
41. int*  v1=(int* )malloc(4E6L);
    
42. 
    
43. printf("申请源表内存%dms\n",clock()-t);
    
44. t=clock();
    
45. 
    
46. __int64* v2;//store sum(v1);
    
47. //FILE *fp=fopen("in.txt","wb");
    
48. //FILE *fp=fopen("in.txt","rb");
    
49. for (int i=0;i<1E6L;i++)
    
50. {
    
51.         int j=i+1;
    
52.         c1[i]=j%s[r][0];
    
53.         c2[i]=j%s[r][1];
    
54.         c3[i]=j%s[r][2];
    
55.         c4[i]=(j%13?j%113:127);
    
56.         v1[i]=j;
    
57.         //fscanf(fp,"%d,%d,%d,%d,%d\n",&c1[i],&c2[i],&c3[i],&c4[i],&v1[i]);
    
58.         //fprintf(fp,"%d,%d,%d,%d,%d\n",c1[i],c2[i],c3[i],c4[i],v1[i]);       
    
59. 
    
60. }
    
61. //fclose(fp);
    
62. //return 1;
    
63. map<const int, int, ltint> key_recn;
    
64. map<const int, int, ltint> key_recn2[16];
    
65. int c=0;
    
66. printf("填充源表数据%dms,recn=%d,每毫秒%d行\n",clock()-t,c,(long)1E6/(clock()-t));
    
67. t=clock();
    
68. 
    
69. for (int i=0;i<1E6L;i++)
    
70. {
    
71.         int key=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
72.         //printf("key=%d\n",key);
    
73.         add_key;
    
74. 
    
75. }
    
76. 
    
77. printf("新建一层节点%dms,recn=%d,每毫秒读%d行,每毫秒写%d节点\n",clock()-t,c,(long)1E6/(clock()-t),c/(clock()-t));
    
78. t=clock();
    
79. int *C=(int*)malloc(c*4);//store count(c1)
    
80. int *k=(int*)malloc(c*4);//store key
    
81. 
    
82. v2=(__int64*)malloc(c*8);
    
83. 
    
84. memset(C,0,c*4); //need?
    
85. memset(v2,0,c*8);
    
86. printf("申请一层内存%dms\n",clock()-t);
    
87. t=clock();
    
88. 
    
89. 
    
90. for (int i=0;i<1E6L;i++)
    
91. {
    
92. int recn=key_recn[(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i]];
    
93. k[recn]=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
94. C[recn]++;
    
95. v2[recn]=v2[recn]+v1[i];
    
96. 
    
97. }
    
98. printf("写入一层数据%dms,recn=%d,每毫秒读%d行，每毫秒写%d行\n",clock()-t,c,(long)1E6/(clock()-t),c/(clock()-t));
    
99. t=clock();
    
100. int c_2=c;
     
101. for (int i=0;i<c_2;i++)
     
102. {
     
103.         int key=(k[i]&0xFFFFFF)+((0x80+15)<<24);//set c1 null ,gid=8
     
104.         adkey(8);
     
105. 
     
106.         key=(k[i]&0xFF00FFFF)+((0x40)<<24)+(127<<16);//set c2 null,gid=4
     
107.         adkey(4);
     
108. 
     
109.         key=(k[i]&0xFFFF00FF)+((0x20)<<24)+(127<<8);//set c3 null,gid=2
     
110.         adkey(2);
     
111. 
     
112.         key=(k[i]&0xFFFFFF00)+((0x10)<<24)+(127);//set c4 null,gid=1
     
113.         adkey(1);
     
114. 
     
115. /*
     
116.         key=(k[i]&0xFFFF00)+((0x90+15)<<24)+(127);//set c1,c4 null ,gid=9
     
117.         adkey(9);
     
118. 
     
119.         key=(k[i]&0xFF00FF00)+((0x50)<<24)+(127<<16)+(127);//set c2,c4 null,gid=5
     
120.         adkey(5);
     
121. 
     
122.         key=(k[i]&0xFFFF0000)+((0x30)<<24)+(127<<8)+(127);//set c3,c4 null,gid=3
     
123.         adkey(3);
     
124. 
     
125.         key=(k[i]&0xFF0000FF)+((0x60)<<24)+(127<<16)+(127<<8);//set c2,c3 null,gid=6
     
126.         adkey(6);
     
127. 
     
128.         key=(k[i]&0x00FF00FF)+((0xA0+15)<<24)+(127<<8);//set c1,c3 null,gid=10
     
129.         adkey(10);
     
130. 
     
131.         key=(k[i]&0xFFFF)+((0xC0+15)<<24)+(127<<16);//set c1,c2 null,gid=12
     
132.         adkey(12);
     
133. 
     
134.         key=(k[i]&0xFF00)+((0xD0+15)<<24)+(127<<16)+(127);//set c1,c2,c4 null,gid=13
     
135.         adkey(13);
     
136. 
     
137.         key=(k[i]&0xFF)+((0xE0+15)<<24)+(127<<16)+(127<<8);//set c1,c2,c3 null,gid=14
     
138.         adkey(14);
     
139. 
     
140.         key=(k[i]&0xFF0000)+((0xB0+15)<<24)+(127<<8)+(127);//set c1,c3,c4 null,gid=11
     
141.         adkey(11);
     
142. 
     
143.         key=(k[i]&0xFF000000)+((0x70)<<24)+(127<<16)+(127<<8)+(127);//set c2,c3,c4 null,gid=7
     
144.         adkey(7);
     
145. 
     
146.         key=((0xF0+15)<<24)+(127<<16)+(127<<8)+(127);//set c1,c2,c3,c4 null,gid=15
     
147.         adkey(15);
     
148. */        
     
149. }
     
150. map<const int, int,ltint>::iterator iter;
     
151. for(int i=1;i<7;i++)
     
152. {
     
153. if (i==1)       
     
154. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
155. {
     
156.         int key=((iter->first)&0x0FFF0000)+((0x30)<<24)+(127<<8)+(127);//set c3,c4 null,gid=3
     
157.         adkey(3);
     
158. 
     
159.         key=((iter->first)&0xFFFF00)+((0x90+15)<<24)+(127);//set c1,c4 null ,gid=9
     
160.         adkey(9);
     
161. 
     
162.         key=((iter->first)&0x0F00FF00)+((0x50)<<24)+(127<<16)+(127);//set c2,c4 null,gid=5
     
163.         adkey(5);
     
164. 
     
165. }
     
166. if(i==2)
     
167. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
168. {
     
169.         int key=((iter->first)&0x00FF00FF)+((0xA0+15)<<24)+(127<<8);//set c1,c3 null,gid=10
     
170.         adkey(10);
     
171. }
     
172. if(i==4)
     
173. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
174. {
     
175.         int key=((iter->first)&0x0F0000FF)+((0x60)<<24)+(127<<16)+(127<<8);//set c2,c3 null,gid=6
     
176.         adkey(6);
     
177. 
     
178. 
     
179.         key=((iter->first)&0xFFFF)+((0xC0+15)<<24)+(127<<16);//set c1,c2 null,gid=12
     
180.         adkey(12);
     
181. }
     
182. if(i==3)
     
183. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
184. {
     
185.         int key=((iter->first)&0xFF0000)+((0xB0+15)<<24)+(127<<8)+(127);//set c1,c3,c4 null,gid=11
     
186.         adkey(11);
     
187. 
     
188.         key=((iter->first)&0x0F000000)+((0x70)<<24)+(127<<16)+(127<<8)+(127);//set c2,c3,c4 null,gid=7
     
189.         adkey(7);
     
190. }
     
191. if(i==5)
     
192. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
193. {
     
194.         int key=((iter->first)&0xFF00)+((0xD0+15)<<24)+(127<<16)+(127);//set c1,c2,c4 null,gid=13
     
195.         adkey(13);
     
196. }
     
197. if(i==6)
     
198. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
199. {
     
200.         int key=((iter->first)&0xFF)+((0xE0+15)<<24)+(127<<16)+(127<<8);//set c1,c2,c3 null,gid=14
     
201.         adkey(14);
     
202. }
     
203. }
     
204.         int key=((0xF0+15)<<24)+(127<<16)+(127<<8)+(127);//set c1,c2,c3,c4 null,gid=15
     
205.         adkey(15);
     
206. 
     
207. printf("新建后面节点%dms,recn=%d,每毫秒读%d行key,每毫秒写%d节点\n",clock()-t,c,c_2/(clock()-t),(c-c_2)/(clock()-t));
     
208. for(int i=0;i<16;i++)
     
209. {
     
210.         printf("%d,first=%0X,renc=%d\n",i,key_recn2[i].begin()->first,key_recn2[i][key_recn2[i].begin()->first]);
     
211.         }
     
212. t=clock();
     
213. int o[15]={8,4,2,1,9,5,3,6,10,12,13,14,11,7,15};
     
214. int mask[15]={
     
215. 0x00FFFFFF,
     
216. 0xFF00FFFF,
     
217. 0xFFFF00FF,
     
218. 0xFFFFFF00,
     
219. 0x00FFFF00,
     
220. 0xFF00FF00,
     
221. 0xFFFF0000,
     
222. 0xFF0000FF,
     
223. 0x00FF00FF,
     
224. 0x0000FFFF,
     
225. 0x0000FF00,
     
226. 0x000000FF,
     
227. 0x00FF0000,
     
228. 0xFF000000,
     
229. 0x00000000};
     
230. 
     
231. int null[15]={
     
232. ((0x80+15)<<24),
     
233. ((0x40)<<24)+(127<<16),
     
234. ((0x20)<<24)+(127<<8),
     
235. ((0x10)<<24)+(127),
     
236. ((0x90+15)<<24)+(127),
     
237. ((0x50)<<24)+(127<<16)+(127),
     
238. ((0x30)<<24)+(127<<8)+(127),
     
239. ((0x60)<<24)+(127<<16)+(127<<8),
     
240. ((0xA0+15)<<24)+(127<<8),
     
241. ((0xC0+15)<<24)+(127<<16),
     
242. ((0xD0+15)<<24)+(127<<16)+(127),
     
243. ((0xE0+15)<<24)+(127<<16)+(127<<8),
     
244. ((0xB0+15)<<24)+(127<<8)+(127),
     
245. ((0x70)<<24)+(127<<16)+(127<<8)+(127),
     
246. ((0xF0+15)<<24)+(127<<16)+(127<<8)+(127)
     
247. };
     
248. 
     
249. 
     
250. int *C2=(int*)malloc((c-c_2)*4);//store count(c1)
     
251. int *k2=(int*)malloc((c-c_2)*4);//store key
     
252. __int64* v3=(__int64*)malloc((c-c_2)*8);
     
253. 
     
254. memset(C2,0,(c-c_2)*4); //need?
     
255. memset(v3,0,(c-c_2)*8);
     
256. printf("申请后面内存%dms,%d\n",clock()-t,c);
     
257. t=clock();
     
258. //goto f;
     
259. int y=0;
     
260. int f[16];
     
261. memset(f,0,15*4);
     
262. 
     
263. for (int i=0;i<c_2;i++)
     
264. {
     
265. for(int j=0;j<4;j++)
     
266. {
     
267.         //int key=(k[i]&mask[j])+null[j];
     
268.         //if(key_recn2[o[j]].find(key)!= key_recn2[o[j]].end())
     
269.         {f[o[j]]++;
     
270. int recn=key_recn2[o[j]][(k[i]&mask[j])+null[j]]-c_2;
     
271. k2[recn]=(k[i]&mask[j])+null[j];
     
272. C2[recn]+=C[i];
     
273. v3[recn]+=v2[i];
     
274. 
     
275. y=recn;
     
276. }
     
277. }
     
278. }
     
279. 
     
280. for(int i=1;i<7;i++)
     
281. {
     
282. if (i==1)       
     
283. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
284. {
     
285.         int key=((iter->first)&0x0FFF0000)+((0x30)<<24)+(127<<8)+(127);//set c3,c4 null,gid=3
     
286. /*        {f[3]++;
     
287. int recn=key_recn2[3][key]-c_2;
     
288. k2[recn]=key;
     
289. C2[recn]+=C2[(iter->second)-c_2];
     
290. v3[recn]+=v3[(iter->second)-c_2];
     
291. }*/
     
292.         sumkey(3);
     
293. 
     
294.         key=((iter->first)&0xFFFF00)+((0x90+15)<<24)+(127);//set c1,c4 null ,gid=9
     
295.         sumkey(9);
     
296. 
     
297.         key=((iter->first)&0x0F00FF00)+((0x50)<<24)+(127<<16)+(127);//set c2,c4 null,gid=5
     
298.         sumkey(5);
     
299. 
     
300. }
     
301. if(i==2)
     
302. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
303. {
     
304.         int key=((iter->first)&0x00FF00FF)+((0xA0+15)<<24)+(127<<8);//set c1,c3 null,gid=10
     
305.         sumkey(10);
     
306. }
     
307. 
     
308. if(i==4)
     
309. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
310. {
     
311.         int key=((iter->first)&0x0F0000FF)+((0x60)<<24)+(127<<16)+(127<<8);//set c2,c3 null,gid=6
     
312.         sumkey(6);
     
313. 
     
314. 
     
315.         key=((iter->first)&0xFFFF)+((0xC0+15)<<24)+(127<<16);//set c1,c2 null,gid=12
     
316.         sumkey(12);
     
317. }
     
318. if(i==3)
     
319. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
320. {
     
321.         int key=((iter->first)&0xFF0000)+((0xB0+15)<<24)+(127<<8)+(127);//set c1,c3,c4 null,gid=11
     
322.         sumkey(11);
     
323. 
     
324.         key=((iter->first)&0x0F000000)+((0x70)<<24)+(127<<16)+(127<<8)+(127);//set c2,c3,c4 null,gid=7
     
325.         sumkey(7);
     
326. 
     
327.         key=((0xF0+15)<<24)+(127<<16)+(127<<8)+(127);//set c1,c2,c3,c4 null,gid=15
     
328.         sumkey(15);
     
329. }
     
330. if(i==5)
     
331. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
332. {
     
333.         int key=((iter->first)&0xFF00)+((0xD0+15)<<24)+(127<<16)+(127);//set c1,c2,c4 null,gid=13
     
334.         sumkey(13);
     
335. }
     
336. if(i==6)
     
337. for(iter=key_recn2[i].begin();iter != key_recn2[i].end(); iter++)
     
338. {
     
339.         int key=((iter->first)&0xFF)+((0xE0+15)<<24)+(127<<16)+(127<<8);//set c1,c2,c3 null,gid=14
     
340.         sumkey(14);
     
341. }
     
342. }
     
343. 
     
344. printf("汇总后面节点%dms,recn=%d,每毫秒读%d行，每毫秒写%d行\n",clock()-t,c,c_2/(clock()-t),(c-c_2)/(clock()-t));
     
345. t=clock();
     
346. /*
     
347. printf("%fms,recn=%d,c1=%d,c2=%d,c3=%d,c4=%d,count=%d,sum=%I64d\n",(float)(clock()-t)/CLOCKS_PER_SEC ,c,
     
348. (k2[y]>>24),((k2[y]>>16)&255),((k2[y]>>8)&255),(k2[y]&255),C2[y],v3[y]);
     
349. 
     
350. */
     
351. FILE *fp=fopen("out.txt","wb");
     
352. 
     
353. //fp=fopen("out.txt","wb");
     
354. fprintf(fp,"gid,c1,c2,c3,c4,count,sum\n");
     
355. for (int i=0;i<c_2;i++)
     
356. {
     
357.         y=i;
     
358.         fprintf(fp,"%d,%d,%d,%d,%d,%d,%I64d\n",
     
359. 0,(k[y]>>24),((k[y]>>16)&255),((k[y]>>8)&255),(k[y]&255),C[y],v2[y]);
     
360. 
     
361. }
     
362. 
     
363. for (int i=0;i<c-c_2;i++)
     
364. {
     
365.         y=i;
     
366.         fprintf(fp,"%d,%d,%d,%d,%d,%d,%I64d\n",
     
367. (16+((k2[y]>>24)>>4))&15,(k2[y]>>24)&15,((k2[y]>>16)&255),((k2[y]>>8)&255),(k2[y]&255),C2[y],v3[y]);
     
368. 
     
369. }
     
370. fclose(fp);
     
371. printf("保存到文件%dms,recn=%d,每毫秒写%d行\n",clock()-t,c,c/(clock()-t));
     
372. t=clock();
     
373. 
     
374. f:
     
375. free(c1);
     
376. free(c2);
     
377. free(c3);
     
378. free(c4);
     
379. free(v1);
     
380. free(v2);
     
381. free(C);
     
382. free(k);
     
383. free(C2);
     
384. free(k2);
     
385. free(v3);
     
386. printf("释放所有动态内存%dms,%d\n",clock()-t,c);
     
387. for(int i=0;i<16;i++)
     
388. printf("%d,%d\n",i,f[i]);
     
389. 
     
390. 
     
391. 
     
392. }
     
393. return 0;
     
394. }
     

复制代码

D:\lt\dl>map7
9,97,119,114,11843118
申请源表内存0ms
填充源表数据62ms,recn=0,每毫秒16129行
新建一层节点453ms,recn=1000000,每毫秒读2207行,每毫秒写2207节点
申请一层内存0ms
写入一层数据219ms,recn=1000000,每毫秒读4566行，每毫秒写4566行
新建后面节点1531ms,recn=2299600,每毫秒读653行key,每毫秒写848节点
0,first=3D454D41,renc=0
1,first=1000007F,renc=1397076
2,first=20007F00,renc=1381362
3,first=30007F7F,renc=2260123
4,first=407F0000,renc=1431349
5,first=507F007F,renc=2260125
6,first=607F7F00,renc=2284774
7,first=707F7F7F,renc=2284669
8,first=8F000001,renc=1549286
9,first=9F00007F,renc=2260124
10,first=AF007F00,renc=2273610
11,first=BF007F7F,renc=2284668
12,first=CF7F0000,renc=2284775
13,first=DF7F007F,renc=2299366
14,first=EF7F7F00,renc=2299485
15,first=FF7F7F7F,renc=2299599
申请后面内存15ms,2299600
汇总后面节点1563ms,recn=2299600,每毫秒读639行，每毫秒写831行
保存到文件2422ms,recn=2299600,每毫秒写949行
释放所有动态内存0ms,2299600
0,0
1,1000000
2,1000000
3,103887
4,1000000
5,103887
6,122094
7,873
8,1000000
9,103887
10,99522
11,873
12,122094
13,1071
14,1026
15,873

D:\lt\dl>dir out.txt


2010-02-28  13:59        52,396,878 out.txt

---------------
很奇怪,服务器又比笔记本慢
D:\app>map7
9,97,119,114,11843118
申请源表内存0ms
填充源表数据46ms,recn=0,每毫秒21739行
新建一层节点656ms,recn=1000000,每毫秒读1524行,每毫秒写1524节点
申请一层内存31ms
写入一层数据312ms,recn=1000000,每毫秒读3205行，每毫秒写3205行
新建后面节点2636ms,recn=2299600,每毫秒读379行key,每毫秒写493节点
0,first=6C694620,renc=0
1,first=1000007F,renc=1397076
2,first=20007F00,renc=1381362
3,first=30007F7F,renc=2260123
4,first=407F0000,renc=1431349
5,first=507F007F,renc=2260125
6,first=607F7F00,renc=2284774
7,first=707F7F7F,renc=2284669
8,first=8F000001,renc=1549286
9,first=9F00007F,renc=2260124
10,first=AF007F00,renc=2273610
11,first=BF007F7F,renc=2284668
12,first=CF7F0000,renc=2284775
13,first=DF7F007F,renc=2299366
14,first=EF7F7F00,renc=2299485
15,first=FF7F7F7F,renc=2299599
申请后面内存47ms,2299600
汇总后面节点2683ms,recn=2299600,每毫秒读372行，每毫秒写484行
保存到文件2387ms,recn=2299600,每毫秒写963行
释放所有动态内存0ms,2299600
0,0
1,1000000
2,1000000
3,103887
4,1000000
5,103887
6,122094
7,873
8,1000000
9,103887
10,99522
11,873
12,122094
13,1071
14,1026
15,1000
^C
D:\app>

[ 本帖最后由 〇〇 于 2010-3-1 13:14 编辑 ]

newkid

你说的“分2步申请内存”是哪几行代码？
多线程我没有做过。PLSQL是不行的，除非提交一个JOB，但是内存又不能共享。
我还试图做过一个改进，但没有效果，因为最耗时的在第一级。这个思路就是把不同GID的汇总数据分开（二维数组），新的GID可以选择条数最少的前级来汇总。
比如GID=5，可以从GID=4或GID=1来汇总；而GID=7就更丰富了，有3,5,6可选。
这都是玩玩而已，我不觉得有实用意义，哪怕你比CUBE提高了一分钟又怎么样呢？程序的代价要考虑进去。况且这只是简单的COUNT,SUM, 人家CUBE可是支持所有聚合函数的，包括DISTINCT关键字。

〇〇

分2步申请内存:
1.add_key 包含了c++
int *C=(int*)malloc(c*4);//store count(c1)
int *k=(int*)malloc(c*4);//store key

v2=(__int64*)malloc(c*8);
2.adkey(i) 包含了c++
int *C2=(int*)malloc((c-c_2)*4);//store count(c1)
int *k2=(int*)malloc((c-c_2)*4);//store key
__int64* v3=(__int64*)malloc((c-c_2)*8);

程序的代价:
要是代码能够动态生成和编译，象上回你帮我拼的union all动态sql一样


比CUBE提高了一分钟：这是不可能的，因为4个分组cube只要几秒
但是如果100万行能提高3秒
10亿就能提高3000秒

〇〇

服务器：xeon e5420 2.5G *2 内存8G
笔记本：core2 duo t9300 2.5G 内存2G