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

newkid

你太抬举我了，就是个熟练工人而已，你要是连续写个十几年想不熟练都不行。

〇〇

数组版本运算时间差不多，写结果时间延长了很多
125  /
level 1:1332
level 1:2613
level 3:290
output:4200

PL/SQL 过程已成功完成。

已用时间:  00: 01: 28.53

非数组版
level 1:1134
level 2:2087
level 3:273
output:658

PL/SQL 过程已成功完成。

已用时间:  00: 00: 42.07

[ 本帖最后由 〇〇 于 2010-3-17 09:45 编辑 ]

〇〇

按照http://www.itpub.net/thread-1276989-2-2.html
的思路改写了ｇｉｄ＝１的查找

1. 　
   
2. #define a2dsmkey(j) if(key==(*lastiter).first){cnt++;f[j]++;int recn=(*lastiter).second-c_2;k2[recn]=key;int i=(*iter2).second;C2[recn]+=C[i];v3[recn]+=v2[i];}\
   
3. else{if((iter=key_recn2[j].find(key))== key_recn2[j].end())\
   
4. {f[j]++;int recn=c-c_2;key_recn2[j][key]=c++;k2[recn]=key;int i=(*iter2).second;C2[recn]+=C[i];v3[recn]+=v2[i];}\
   
5. else{lastiter=iter;f[j]++;int recn=/*key_recn2[j][key]-c_2*/(*iter).second-c_2;k2[recn]=key;int i=(*iter2).second;C2[recn]+=C[i];v3[recn]+=v2[i];}}
   

复制代码

找到的次数还是很可观，可惜时间没省
D:\app\instantclient10_1>..\mapc4b LT/LT@10.6.132.43/orcl query="select c1,c2,c3,c4,v from t" file=NUL
0,1     1,1     2,1     3,1     4,4
       0 rows exported at 2010-03-17 16:44:37
recn=0
  500000 rows exported at 2010-03-17 16:44:37
recn=500000
1000000 rows exported at 2010-03-17 16:44:38
         output file  closed at 1000000 rows.

sum=1
sum(c1+c2+c3+v)=500111497488
sum(c4)=51690810
从数据库把表读入内存1856ms
4,5,67,114,152760
申请map内存0ms
申请一层内存31ms
新建一层节点453ms,recn=1000000,每毫秒读2207行,每毫秒写2207节点
申请后面内存15ms,1000000
found 792226 time
新建后面节点1233ms,recn=2299600,每毫秒读811行key,每毫秒写1054节点
0,first=5040302,renc=0
1,first=1000007F,renc=1000003
2,first=20007F00,renc=1002132
3,first=30007F7F,renc=2260123
4,first=407F0000,renc=1049901
5,first=507F007F,renc=2260125
6,first=607F7F00,renc=2284775
7,first=707F7F7F,renc=2284669
8,first=8F000001,renc=1147278
9,first=9F00007F,renc=2260124
10,first=AF007F00,renc=2273610
11,first=BF007F7F,renc=2284668
12,first=CF7F0000,renc=2284776
13,first=DF7F007F,renc=2299367
14,first=EF7F7F00,renc=2299486
15,first=FF7F7F7F,renc=2284670
释放所有动态内存0ms,2299600
释放所有map内存187ms,2299600
总时间1950ms,2299600
3步（读入+运算+写出）总时间3806ms

Exiting with SUCCESS status 0

〇〇

不用这个算法
新建后面节点1295ms,

〇〇

如果记录数增加到2百万，分组的构成不变
把楼上算法用到从原始表读数算gid 0也许会有帮助(视原表记录顺序)
但对于gid 2 4 8基本上没有帮助
对其他gid因记录太少也没意义

〇〇

原帖由 〇〇 于 2010-3-17 18:28 发表
如果记录数增加到2百万，分组的构成不变
把楼上算法用到从原始表读数算gid 0也许会有帮助(视原表记录顺序)
但对于gid 2 4 8基本上没有帮助
对其他gid因记录太少也没意义

如果200w每行重复1行，节约50ms
如果200w每行重复3行，节约20ms
基本没有意义，要大量重复才行

〇〇

原帖由 〇〇 于 2010-3-16 16:32 发表
看到plsql的nest table用hash表很快，也想在c++里用，结果很糟糕（需要vc2003编译）

D:\app>mapc6h
9,97,119,114,11843118
申请map内存46ms
申请一层内存32ms
新建一层节点624ms,recn=1000000,每毫秒读1602行,每毫秒写1602节点
新建一层hashmap节点1529ms,recn=1000000,每毫秒读654行,每毫秒写654节点
申请后面内存31ms,1000000
新建后面节点1576ms,recn=2299600,每毫秒读634行key,每毫秒写824节点
0,first=6D6F435C,renc=0
1,first=1000007F,renc=1000003
2,first=20007F00,renc=1002132
3,first=30007F7F,renc=2260123
4,first=407F0000,renc=1049901
5,first=507F007F,renc=2260125
6,first=607F7F00,renc=2284775
7,first=707F7F7F,renc=2284669
8,first=8F000001,renc=1147278
9,first=9F00007F,renc=2260124
10,first=AF007F00,renc=2273610
11,first=BF007F7F,renc=2284668
12,first=CF7F0000,renc=2284776
13,first=DF7F007F,renc=2299367
14,first=EF7F7F00,renc=2299486
15,first=FF7F7F7F,renc=2284670
释放所有动态内存15ms,2299600
释放所有map内存7488ms,2299600
总时间11372ms,2299600
3步（读入+运算+写出）总时间25849ms

相同的hash函数和比较函数，sgi stl的快很多

4个重复的50万行
D:\app>mapc6i4
9,97,119,114,11843118
申请map内存31ms
申请一层内存47ms
gid=0 found 0 time
新建一层节点312ms,recn=500001,每毫秒读3205行,每毫秒写1602节点
新建一层hashmap节点125ms,recn=500001,每毫秒读8000行,每毫秒写4000节点
申请后面内存15ms,500001
gid=1 found 292227 time
新建后面节点687ms,recn=1338064,每毫秒读727行key,每毫秒写1219节点
释放所有动态内存0ms,1338064
释放所有map内存93ms,1338064
总时间1341ms,1338064
3步（读入+运算+写出）总时间1372ms

没有重复的200万行
D:\app>cl /O2 mapc6i4.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86
Copyright (C) Microsoft Corp 1984-1998. All rights reserved.

mapc6i4.cpp
Microsoft (R) Incremental Linker Version 6.00.8168
Copyright (C) Microsoft Corp 1992-1998. All rights reserved.

/out:mapc6i4.exe
mapc6i4.obj

D:\app>mapc6i4
9,97,119,114,11843118
申请map内存78ms
申请一层内存46ms
gid=0 found 0 time
新建一层节点983ms,recn=1950041,每毫秒读1017行,每毫秒写1983节点
新建一层hashmap节点765ms,recn=1950041,每毫秒读1307行,每毫秒写2549节点
申请后面内存46ms,1950041
gid=1 found 1742267 time
新建后面节点2044ms,recn=3584098,每毫秒读954行key,每毫秒写799节点
释放所有动态内存0ms,3584098
释放所有map内存328ms,3584098
总时间4290ms,3584098
3步（读入+运算+写出）总时间4446ms

D:\app>

〇〇

如果还用100万比较，vc6的速度怎么比2003快这么多？

9,97,119,114,11843118
申请map内存31ms
申请一层内存31ms
新建一层节点437ms,recn=1000000,每毫秒读2288行,每毫秒写2288节点
新建一层hashmap节点312ms,recn=1000000,每毫秒读3205行,每毫秒写3205节点
申请后面内存16ms,1000000
新建后面节点1279ms,recn=2299600,每毫秒读781行key,每毫秒写1016节点
0,first=696C6374,renc=0
1,first=1000007F,renc=1000003
2,first=20007F00,renc=1002132
3,first=30007F7F,renc=2260123
4,first=407F0000,renc=1049901
5,first=507F007F,renc=2260125
6,first=607F7F00,renc=2284775
7,first=707F7F7F,renc=2284669
8,first=8F000001,renc=1147278
9,first=9F00007F,renc=2260124
10,first=AF007F00,renc=2273610
11,first=BF007F7F,renc=2284668
12,first=CF7F0000,renc=2284776
13,first=DF7F007F,renc=2299367
14,first=EF7F7F00,renc=2299486
15,first=FF7F7F7F,renc=2284670
释放所有动态内存16ms,2299600
释放所有map内存171ms,2299600
总时间2308ms,2299600
3步（读入+运算+写出）总时间2418ms

〇〇

将所有map换成hash map ,节省400毫秒
总在

1. 
   
2. if(i==6)
   
3. for(iterh=key_recn2h[i].begin();iterh != key_recn2h[i].end(); iterh++)
   
4. {
   
5.         int key=(((*iterh).first)&0xFF)+((0xE0+15)<<24)+(127<<16)+(127<<8);//set c1,c2,c3 null,gid=14
   
6.         addsmkeyh(14);
   
7. }

复制代码

出错，少114行的时间。

D:\app\instantclient10_1>..\mapc4bh LT/LT@10.6.132.43/orcl query="select c1,c2,c3,c4,v from t" file=NUL
0,1     1,1     2,1     3,1     4,4
       0 rows exported at 2010-03-18 13:00:42
recn=0
  500000 rows exported at 2010-03-18 13:00:43
recn=500000
1000000 rows exported at 2010-03-18 13:00:44
         output file  closed at 1000000 rows.

sum=1
sum(c1+c2+c3+v)=500111497488
sum(c4)=51690810
从数据库把表读入内存1918ms
4,5,67,114,152760
申请map内存0ms
申请一层内存32ms
新建一层hashmap节点327ms,recn=1000000,每毫秒读3058行,每毫秒写3058节点
申请后面内存16ms,1000000
gid=1 found 0 time
新建后面节点951ms,recn=2299486,每毫秒读1051行key,每毫秒写1366节点
释放所有动态内存0ms,2299486
释放所有map内存0ms,2299486
总时间1342ms,2299486
3步（读入+运算+写出）总时间3447ms

Exiting with SUCCESS status 0
与map版的最快相比
D:\app\instantclient10_1>..\mapc4b LT/LT@10.6.132.43/orcl query="select c1,c2,c3,c4,v from t" file=NUL
0,1     1,1     2,1     3,1     4,4
       0 rows exported at 2010-03-17 16:44:37
recn=0
  500000 rows exported at 2010-03-17 16:44:37
recn=500000
1000000 rows exported at 2010-03-17 16:44:38
         output file  closed at 1000000 rows.

sum=1
sum(c1+c2+c3+v)=500111497488
sum(c4)=51690810
从数据库把表读入内存1856ms
4,5,67,114,152760
申请map内存0ms
申请一层内存31ms
新建一层节点453ms,recn=1000000,每毫秒读2207行,每毫秒写2207节点
申请后面内存15ms,1000000
found 792226 time
新建后面节点1233ms,recn=2299600,每毫秒读811行key,每毫秒写1054节点
释放所有动态内存0ms,2299600
释放所有map内存187ms,2299600
总时间1950ms,2299600
3步（读入+运算+写出）总时间3806ms

Exiting with SUCCESS status 0

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

〇〇

留个代码备查