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

newkid

这题目出得不行啊，没什么人感兴趣，两天过去了还是哥几个在闹腾。

〇〇

可能是哥你抛的砖太玉了，别人一时拿不出更好的了

〇〇

也可能是奖太没有吸引力,参见
http://www.itpub.net/viewthread. ... extra=&page=283

〇〇

编译器连接 http://www.itpub.net/thread-1227973-1-1.html
感觉从第2层开始可以用并行的方法,c有并行库，pl/sql不知是否支持

nyfor

原帖由 newkid 于 2010-2-24 22:42 发表
这题目出得不行啊，没什么人感兴趣，两天过去了还是哥几个在闹腾。

呵呵, 說實話, 我是不太感興趣, 這僅僅涉及到算法而已,而且還有點費時,  基本不涉及到 Oracle 知識.
而且這個算法的實現, 估計不會有太精彩的亮點.

〇〇

对这个具体的数据没有意义,对未知的大表可能还是有意思的
比如根据原始表列的取值范围和行数,分组的要求判断较优的算法(时间和空间)

yulihua49

原帖由 〇〇 于 2010-2-25 09:58 发表
对这个具体的数据没有意义,对未知的大表可能还是有意思的
比如根据原始表列的取值范围和行数,分组的要求判断较优的算法(时间和空间)

还是CUBE最快，没必要自己整了。如果使用其他数据库不带CUBE的，可以玩玩看。

我那个表，ora连来带回才16ms，单单用树归并就35ms，不玩了。

[ 本帖最后由 yulihua49 于 2010-2-25 10:51 编辑 ]

〇〇

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 addkey {if((key_recn.find(key))== key_recn.end())key_recn[key]=c++;}
   
9. using namespace std;
   
10. struct ltstr
    
11. {
    
12.   bool operator()(const char* s1, const char* s2) const
    
13.   {
    
14.     return strcmp(s1, s2) < 0;
    
15.   }
    
16. };
    
17. struct ltint
    
18. {
    
19.   bool operator()(const int s1, const int s2) const
    
20.   {
    
21.     return (s1<s2) ;
    
22.   }
    
23. };
    
24. int main()
    
25. {
    
26. char* c1=(char*)malloc(1E6L);
    
27. char* c2=(char*)malloc(1E6L);
    
28. char* c3=(char*)malloc(1E6L);
    
29. char* c4=(char*)malloc(1E6L);
    
30. int*  v1=(int* )malloc(4E6L);
    
31. __int64* v2;//store sum(v1);
    
32. long t=clock();
    
33. for (int i=0;i<1E6L;i++)
    
34. {
    
35.         int j=i+1;
    
36.         c1[i]=j%4;
    
37.         c2[i]=j%5;
    
38.         c3[i]=j%67;
    
39.         c4[i]=(j%13?j%113:127);
    
40.         v1[i]=j;
    
41. }
    
42. 
    
43. 
    
44. map<const int, int, ltint> key_recn;
    
45. int c=0;
    
46. for (int i=0;i<1E6L;i++)
    
47. {
    
48.         int key=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
49.         //printf("key=%d\n",key);
    
50.         addkey;
    
51. 
    
52. }
    
53. 
    
54. 
    
55. int *C=(int*)malloc(c*4);//store count(c1)
    
56. int *k=(int*)malloc(c*4);//store key
    
57. 
    
58. v2=(__int64*)malloc(c*8);
    
59. /*
    
60. memset(C,0,c*4); //need?
    
61. memset(v2,0,c*8);
    
62. */
    
63. 
    
64. for (int i=0;i<1E6L;i++)
    
65. {
    
66. int recn=key_recn[(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i]];
    
67. k[recn]=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
68. C[recn]++;
    
69. v2[recn]=v2[recn]+v1[i];
    
70. 
    
71. }
    
72. 
    
73. int c_2=c;
    
74. for (int i=0;i<c_2;i++)
    
75. {
    
76.         int key=(k[i]&0xFFFFFF)+((0x80+15)<<24);//set c1 null ,gid=8
    
77.         addkey;
    
78.                
    
79.         key=(k[i]&0xFF00FFFF)+((0x40)<<24)+(127<<16);//set c2 null,gid=4
    
80.         addkey;
    
81. 
    
82.         key=(k[i]&0xFFFF00FF)+((0x20)<<24)+(127<<8);//set c3 null,gid=2
    
83.         addkey;
    
84. 
    
85.         key=(k[i]&0xFFFFFF00)+((0x10)<<24)+(127);//set c4 null,gid=1
    
86.         addkey;
    
87. 
    
88.         key=(k[i]&0xFFFF00)+((0x90+15)<<24)+(127);//set c1,c4 null ,gid=9
    
89.         addkey;
    
90.                
    
91.         key=(k[i]&0xFF00FF00)+((0x50)<<24)+(127<<16)+(127);//set c2,c4 null,gid=5
    
92.         addkey;
    
93. 
    
94.         key=(k[i]&0xFFFF0000)+((0x30)<<24)+(127<<8)+(127);//set c3,c4 null,gid=3
    
95.         addkey;
    
96. 
    
97.         key=(k[i]&0xFF0000FF)+((0x60)<<24)+(127<<16)+(127<<8);//set c2,c3 null,gid=6
    
98.         addkey;
    
99.        
    
100.         key=(k[i]&0x00FF00FF)+((0xA0+15)<<24)+(127<<8);//set c1,c3 null,gid=10
     
101.         addkey;
     
102.                
     
103.         key=(k[i]&0xFFFF)+((0xC0+15)<<24)+(127<<16);//set c1,c2 null,gid=12
     
104.         addkey;
     
105.                
     
106.         key=(k[i]&0xFF00)+((0xD0+15)<<24)+(127<<16)+(127);//set c1,c2,c4 null,gid=13
     
107.         addkey;
     
108. 
     
109.         key=(k[i]&0xFF)+((0xE0+15)<<24)+(127<<16)+(127<<8);//set c1,c2,c3 null,gid=14
     
110.         addkey;
     
111. 
     
112.         key=(k[i]&0xFF0000)+((0xB0+15)<<24)+(127<<8)+(127);//set c1,c3,c4 null,gid=11
     
113.         addkey;
     
114.                
     
115.         key=(k[i]&0xFF000000)+((0x70)<<24)+(127<<16)+(127<<8)+(127);//set c2,c3,c4 null,gid=7
     
116.         addkey;
     
117. 
     
118.         key=((0xF0+15)<<24)+(127<<16)+(127<<8)+(127);//set c1,c2,c3,c4 null,gid=15
     
119.         addkey;
     
120. }
     
121. printf("%dms,recn=%d",clock()-t,c);
     
122. /*int d=
     
123. printf("%dms,recn=%d,c1=%d,c2=%d,c3=%d,c4=%d,count=%d,sum=%ld",clock()-t,c,
     
124. (k[c-1]>>24),((k[c-1]>>16)&255),((k[c-1]>>8)&255),(k[c-1]&255),C[c-1],v2[c-1]);
     
125. */
     
126. free(c1);
     
127. free(c2);
     
128. free(c3);
     
129. free(c4);
     
130. free(v1);
     
131. free(v2);
     
132. free(C);
     
133. free(k);
     
134. return 0;
     
135. 
     
136. }
     

复制代码

D:\app>map2
811ms,recn=234600

〇〇

c纯内存操作1秒完成，不知道读入和写出数据到表的时间

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. using namespace std;
    
11. struct ltstr
    
12. {
    
13.   bool operator()(const char* s1, const char* s2) const
    
14.   {
    
15.     return strcmp(s1, s2) < 0;
    
16.   }
    
17. };
    
18. struct ltint
    
19. {
    
20.   bool operator()(const int s1, const int s2) const
    
21.   {
    
22.     return (s1<s2) ;
    
23.   }
    
24. };
    
25. int main()
    
26. {
    
27. char* c1=(char*)malloc(1E6L);
    
28. char* c2=(char*)malloc(1E6L);
    
29. char* c3=(char*)malloc(1E6L);
    
30. char* c4=(char*)malloc(1E6L);
    
31. int*  v1=(int* )malloc(4E6L);
    
32. __int64* v2;//store sum(v1);
    
33. long t=clock();
    
34. for (int i=0;i<1E6L;i++)
    
35. {
    
36.         int j=i+1;
    
37.         c1[i]=j%4;
    
38.         c2[i]=j%5;
    
39.         c3[i]=j%67;
    
40.         c4[i]=(j%13?j%113:127);
    
41.         v1[i]=j;
    
42. }
    
43. 
    
44. 
    
45. map<const int, int, ltint> key_recn;
    
46. map<const int, int, ltint> key_recn2;
    
47. int c=0;
    
48. for (int i=0;i<1E6L;i++)
    
49. {
    
50.         int key=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
51.         //printf("key=%d\n",key);
    
52.         add_key;
    
53. 
    
54. }
    
55. 
    
56. 
    
57. int *C=(int*)malloc(c*4);//store count(c1)
    
58. int *k=(int*)malloc(c*4);//store key
    
59. 
    
60. v2=(__int64*)malloc(c*8);
    
61. 
    
62. memset(C,0,c*4); //need?
    
63. memset(v2,0,c*8);
    
64. 
    
65. 
    
66. for (int i=0;i<1E6L;i++)
    
67. {
    
68. int recn=key_recn[(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i]];
    
69. k[recn]=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
70. C[recn]++;
    
71. v2[recn]=v2[recn]+v1[i];
    
72. 
    
73. }
    
74. printf("%dms,recn=%d\n",clock()-t,c);
    
75. t=clock();
    
76. int c_2=c;
    
77. for (int i=0;i<c_2;i++)
    
78. {
    
79.         int key=(k[i]&0xFFFFFF)+((0x80+15)<<24);//set c1 null ,gid=8
    
80.         addkey;
    
81. 
    
82.         key=(k[i]&0xFF00FFFF)+((0x40)<<24)+(127<<16);//set c2 null,gid=4
    
83.         addkey;
    
84. 
    
85.         key=(k[i]&0xFFFF00FF)+((0x20)<<24)+(127<<8);//set c3 null,gid=2
    
86.         addkey;
    
87. 
    
88.         key=(k[i]&0xFFFFFF00)+((0x10)<<24)+(127);//set c4 null,gid=1
    
89.         addkey;
    
90. 
    
91.         key=(k[i]&0xFFFF00)+((0x90+15)<<24)+(127);//set c1,c4 null ,gid=9
    
92.         addkey;
    
93. 
    
94.         key=(k[i]&0xFF00FF00)+((0x50)<<24)+(127<<16)+(127);//set c2,c4 null,gid=5
    
95.         addkey;
    
96. 
    
97.         key=(k[i]&0xFFFF0000)+((0x30)<<24)+(127<<8)+(127);//set c3,c4 null,gid=3
    
98.         addkey;
    
99. 
    
100.         key=(k[i]&0xFF0000FF)+((0x60)<<24)+(127<<16)+(127<<8);//set c2,c3 null,gid=6
     
101.         addkey;
     
102. 
     
103.         key=(k[i]&0x00FF00FF)+((0xA0+15)<<24)+(127<<8);//set c1,c3 null,gid=10
     
104.         addkey;
     
105. 
     
106.         key=(k[i]&0xFFFF)+((0xC0+15)<<24)+(127<<16);//set c1,c2 null,gid=12
     
107.         addkey;
     
108. 
     
109.         key=(k[i]&0xFF00)+((0xD0+15)<<24)+(127<<16)+(127);//set c1,c2,c4 null,gid=13
     
110.         addkey;
     
111. 
     
112.         key=(k[i]&0xFF)+((0xE0+15)<<24)+(127<<16)+(127<<8);//set c1,c2,c3 null,gid=14
     
113.         addkey;
     
114. 
     
115.         key=(k[i]&0xFF0000)+((0xB0+15)<<24)+(127<<8)+(127);//set c1,c3,c4 null,gid=11
     
116.         addkey;
     
117. 
     
118.         key=(k[i]&0xFF000000)+((0x70)<<24)+(127<<16)+(127<<8)+(127);//set c2,c3,c4 null,gid=7
     
119.         addkey;
     
120. 
     
121.         key=((0xF0+15)<<24)+(127<<16)+(127<<8)+(127);//set c1,c2,c3,c4 null,gid=15
     
122.         addkey;
     
123. }
     
124. 
     
125. int mask[15]={
     
126. 0x00FFFFFF,
     
127. 0xFF00FFFF,
     
128. 0xFFFF00FF,
     
129. 0xFFFFFF00,
     
130. 0x00FFFF00,
     
131. 0xFF00FF00,
     
132. 0xFFFF0000,
     
133. 0xFF0000FF,
     
134. 0x00FF00FF,
     
135. 0x0000FFFF,
     
136. 0x0000FF00,
     
137. 0x000000FF,
     
138. 0x00FF0000,
     
139. 0xFF000000,
     
140. 0x00000000};
     
141. 
     
142. int null[15]={
     
143. ((0x80+15)<<24),
     
144. ((0x40)<<24)+(127<<16),
     
145. ((0x20)<<24)+(127<<8),
     
146. ((0x10)<<24)+(127),
     
147. ((0x90+15)<<24)+(127),
     
148. ((0x50)<<24)+(127<<16)+(127),
     
149. ((0x30)<<24)+(127<<8)+(127),
     
150. ((0x60)<<24)+(127<<16)+(127<<8),
     
151. ((0xA0+15)<<24)+(127<<8),
     
152. ((0xC0+15)<<24)+(127<<16),
     
153. ((0xD0+15)<<24)+(127<<16)+(127),
     
154. ((0xE0+15)<<24)+(127<<16)+(127<<8),
     
155. ((0xB0+15)<<24)+(127<<8)+(127),
     
156. ((0x70)<<24)+(127<<16)+(127<<8)+(127),
     
157. ((0xF0+15)<<24)+(127<<16)+(127<<8)+(127)
     
158. };
     
159. 
     
160. 
     
161. int *C2=(int*)malloc((c-c_2)*4);//store count(c1)
     
162. int *k2=(int*)malloc((c-c_2)*4);//store key
     
163. __int64* v3=(__int64*)malloc((c-c_2)*8);
     
164. 
     
165. memset(C2,0,(c-c_2)*4); //need?
     
166. memset(v3,0,(c-c_2)*8);
     
167. 
     
168. int y=0;
     
169. for (int i=0;i<c_2;i++)
     
170. {
     
171. for(int j=0;j<15;j++)
     
172. {
     
173. int recn=key_recn2[(k[i]&mask[j])+null[j]]-c_2;
     
174. k2[recn]=(k[i]&mask[j])+null[j];
     
175. C2[recn]+=C[i];
     
176. v3[recn]=v3[recn]+v2[i];
     
177. 
     
178. y=recn;
     
179. }
     
180. }
     
181. printf("%dms,recn=%d,c1=%d,c2=%d,c3=%d,c4=%d,count=%d,sum=%I64d",clock()-t,c,
     
182. (k2[y]>>24),((k2[y]>>16)&255),((k2[y]>>8)&255),(k2[y]&255),C2[y],v3[y]);
     
183. 
     
184. free(c1);
     
185. free(c2);
     
186. free(c3);
     
187. free(c4);
     
188. free(v1);
     
189. free(v2);
     
190. free(C);
     
191. free(k);
     
192. free(C2);
     
193. free(k2);
     
194. free(v3);
     
195. 
     
196. return 0;
     
197. 
     
198. }
     

复制代码

D:\>map2
483ms,recn=152760
577ms,recn=234600,c1=-1,c2=127,c3=127,c4=127,count=1000000,sum=500000500000

〇〇

用oci读写数据库，direct path、绑定变量真麻烦