PLSQL计算质数

前两天给开发人员进行了PL/SQL的培训，为了帮助他们熟悉PL/SQL的语法，最后留了一个小的练习题，列出100以内的质数。

其实算法很简单，两个循环就搞定了。但是发现使用不同的算法，执行效率差别之大相当惊人，特别是数据量级很大的时候。

A(|{C*gHp%^#}0

下面就是最常见的一种写法：（也是最差的一种）

SQL> SET SERVEROUT ON
y0{3_,|3}0SQL> DECLARE
"EY1w#hm:He3`4G-j S02 V_FLAG BOOLEAN;ITPUB个人空间cu0HZ
` OIf\
3 BEGINITPUB个人空间&H \7rm*i.U3PB
4 FOR I IN 2 .. 100 LOOP
3\7]w)gzT7N+z05 V_FLAG := TRUE;
,S^J-MGl
z;|06 FOR J IN 2 .. I - 1 LOOP
eU"n2q \9h07 IF MOD(I,J) = 0 THENITPUB个人空间9N`7zSK@'^
8 V_FLAG := FALSE;ITPUB个人空间7O!U0n%Z#G
9 END IF;ITPUB个人空间$u+Q.scGg0\k
10 END LOOP;
#lM8{`{?T011 ITPUB个人空间X n)xZ6y?*B
12 IF V_FLAG = TRUE THEN
E x8`UBxwA013 DBMS_OUTPUT.PUT_LINE(I);
yc-DP T014 END IF;ITPUB个人空间,e*\_Fi2M$E@3yz
15 END LOOP;ITPUB个人空间%IRS:C Y4^w9l
16 END;
.M+mG zI9We _~017 /
9O`#p5ZJ5_ _02ITPUB个人空间.W3{r {n$X'}-~ B
3ITPUB个人空间,h&N"~D[@
5ITPUB个人空间Mt.y~-Y#Es
7
mY&n#t&te%Pa011
1Sg
i
SL|l*s
V013
[V0k_:v4m's-l iH017
b.u3e_!U?y019ITPUB个人空间
d\(vg
hH
23
v oY0V"V9z6j029ITPUB个人空间4maOslQ
^2e
31
#GS.tK Q;h&U!Q037ITPUB个人空间:lC`S?Qy
41
q6G5})bX043ITPUB个人空间NvF6PF
47ITPUB个人空间#my%V&d8aE/t
53ITPUB个人空间E"J.m9sq]
59
l1S)t?"I
@'cx061ITPUB个人空间 WD,F^,Aq1M
67ITPUB个人空间PZph!T(C$VE3M:w!v"l
71ITPUB个人空间 W9`6KZ3d5i
73
dt^+NB}lN079
'TcY}:Vs083
mV&fL;if%g(H$HV3`_089ITPUB个人空间0K!xj4pK&}
97

PL/SQL 过程已成功完成。

已用时间: 00: 00: 00.09

由于屏幕输出操作比较慢，为了避免影响，将屏幕输出关闭。并将数据量增大到100000，以下所有的测试都在这个相同条件下进行。

SQL> DECLARE
0m"[3Gr ?/E#f02 V_FLAG BOOLEAN;ITPUB个人空间0]"d~
{-k!L FS4No6w
3 BEGINITPUB个人空间^P8pb@ a:QK9ug
4 FOR I IN 2 .. 100000 LOOPITPUB个人空间H\3Z9tR/j&E
5 V_FLAG := TRUE;ITPUB个人空间Wcp3^4J,V;|4G
6 FOR J IN 2 .. I - 1 LOOP
^:U1Y
}tV+sr07 IF MOD(I,J) = 0 THENITPUB个人空间f0x,sj?9x$L!V(b
8 V_FLAG := FALSE;ITPUB个人空间(^p6z H
z;N
9 END IF;
9} v1LEQ6M3S@010 END LOOP;ITPUB个人空间
Ll9oU)M BN u$U^
11
l E{|'E*M012 IF V_FLAG = TRUE THENITPUB个人空间FY#nk8tDY
XX
13 --DBMS_OUTPUT.PUT_LINE(I);ITPUB个人空间_/D SV:\
14 NULL;
u!W9x7~,KWi015 END IF;
1}4jK5f)US)];L~)}:E016 END LOOP;
fA.w9h$R
Z`P017 END;ITPUB个人空间_9k LX7b G(Ow%]
18 /

PL/SQL 过程已成功完成。

已用时间: 02: 02: 58.73

这种方法在100000数据量的用时居然达到了2个小时。

如果稍微仔细考虑一下，就会发现，系统做了很多没有必要的工作，首先判断是否能整除的时候不需要循环到I – 1，只要执行到I的平方根就可以了，而且，如果I可以被整除就不需要继续循环，可以马上跳出内层循环了。经过简单优化后：

SQL> DECLAREITPUB个人空间"Az)N:Zqb
2 V_FLAG BOOLEAN;ITPUB个人空间\f[%\"jqq/}x9GC c
3 BEGINITPUB个人空间WAGx ?(V
4 FOR I IN 2 .. 100000 LOOP
(X~"Y5Hn{mm05 V_FLAG := TRUE;ITPUB个人空间A e+MA
f9n0Bmd:b/k
6 FOR J IN 2 .. TRUNC(POWER(I, 0.5)) LOOPITPUB个人空间E!FCU+? W2@E
7 IF MOD(I,J) = 0 THEN
u8l4M5d(O6g5g.y08 V_FLAG := FALSE;ITPUB个人空间Xw7U!t6c%d5f6G
9 EXIT;ITPUB个人空间-a2w dnR-h.M@c
10 END IF;ITPUB个人空间/h2rSv Z
11 END LOOP;ITPUB个人空间:J ~3| `1Rw&a
12
.oz"Q;X^-BRKDf013 IF V_FLAG = TRUE THENITPUB个人空间V,[0Sb+a6gQS
14 --DBMS_OUTPUT.PUT_LINE(I);ITPUB个人空间C:{$V"u$y
15 NULL;
F8\&wPe/XI(E`W016 END IF;
]4N|6W!@*q Kj%{{e017 END LOOP;ITPUB个人空间 bxmV*]?
18 END;ITPUB个人空间0y"aEp:PF!Tp(c
19 /

PL/SQL 过程已成功完成。

已用时间: 00: 00: 16.21

效果十分的明显，从2个多小时，缩减到了16秒。

算法还可以进一步优化，考虑到质数中只有2是偶数，其他都是奇数，可以将2单独处理，然后将循环的步长设置为2，这样外层循环次数就减少了一半。

SQL> DECLAREITPUB个人空间WL gp2{4E[o.JW
2 I NUMBER DEFAULT 3;ITPUB个人空间)C:T#d[;l&]B*j
3 V_FLAG BOOLEAN;
Yq4]X)](mQ$Y04 BEGINITPUB个人空间3DP:h4XCQL
5 --DBMS_OUTPUT.PUT_LINE(2);
;`m1Ds?`06 WHILE I < 100000 LOOPITPUB个人空间:f!j s6[%y
7 V_FLAG := TRUE;ITPUB个人空间E6f+rWgS G
8 FOR J IN 2 .. TRUNC(POWER(I, 0.5)) LOOPITPUB个人空间+jP#[{oE:Y0T
9 IF MOD(I,J) = 0 THEN
j _+Q&aF GA010 V_FLAG := FALSE;ITPUB个人空间W&Tx"Y&@%g|*ghP
11 EXIT;ITPUB个人空间O-hY ?s c1{Q
12 END IF;
-iAX(O/__013 END LOOP;ITPUB个人空间"wm&g;b
wm;l]$}
14
:ij~d0Ur015 IF V_FLAG = TRUE THENITPUB个人空间6ziTmtt/Q"L
16 --DBMS_OUTPUT.PUT_LINE(I);ITPUB个人空间^B9b(G9U\
17 NULL;ITPUB个人空间8]g!A.{2O9FY+wQ-i
18 END IF;
m y&@ u|MY]#~%E019 I := I + 2;ITPUB个人空间V.AZO
d4I bwM
20 END LOOP;ITPUB个人空间%Bl.Yc4e:F
21 END;
9H9N1Ix,e KQP022 /

PL/SQL 过程已成功完成。

已用时间: 00: 00: 09.37

仔细考虑一下，其实用来被整除的数是质数就足够了，不需要对所有奇数进行判断。在下面的过程中，使用索引表来保存计算得到的所有的质数：

SQL> DECLARE
:G0m:|Z I02 TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
bA H X]'kx03 V_RESULT T_RECORD;ITPUB个人空间4v:gJ%A+y"o
4 V_FLAG BOOLEAN;
$}
v'LC:wV \h05 V_CNT NUMBER;
3y0C7\:z}!`7HXH06 I NUMBER DEFAULT 3;
:|F W8btv4eR k07 BEGINITPUB个人空间6P Gc6k0s;B#t{C J
8 V_RESULT(1) := 2;
q?.Vup d09 --DBMS_OUTPUT.PUT_LINE(V_RESULT(1));
|iGqX_&s010 WHILE(I < 100000) LOOP
E!s#uI)c{/J011 V_FLAG := TRUE;ITPUB个人空间av}d-rk/@P6uWI
12 V_CNT := V_RESULT.COUNT;
dW5h^l013 FOR J IN 1..V_CNT LOOP
E ybt.Hr4i014 IF V_RESULT(J) > POWER(I, 0.5) THEN
i(cUWkOq015 EXIT;
5M#b4BxoF%jn\v[016 END IF;
:^B&Q([k"L:Z\g017 IF MOD(I,V_RESULT(J)) = 0 THEN
b
i|9LQ&C1q018 V_FLAG := FALSE;
)m T XeD4_ Q019 EXIT;
$]o'LF)]nY020 END IF;
Zu5d4i(Tj;UG*}021 END LOOP;ITPUB个人空间:n9Vuk|xTP
22 IF V_FLAG THEN
_:[nW6GN023 -- DBMS_OUTPUT.PUT_LINE(I);ITPUB个人空间)QBUd4s5a
24 V_RESULT(V_CNT+1) := I;ITPUB个人空间Fa?5M2_
25 END IF;
,P Z8o:s5s1A.C026 I := I + 2;
R1y0S#e*PWHy027 END LOOP;
Z
SF2j,eRD ?Ol028 END;ITPUB个人空间^pS-jC{#K
29 /

PL/SQL 过程已成功完成。

已用时间: 00: 00: 06.68

已经将速度提高到了6秒左右，还能不能更快呢？注意到在最内层循环中调用了一个函数POWER(I, 0.5)，下面将这个表达式转换一下，避免使用这个函数：

SQL> DECLARE
M yCI(cR{7}02 TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;ITPUB个人空间4J[T\ EV7v-dy
3 V_RESULT T_RECORD;
,D0zu1l}P L;?04 V_FLAG BOOLEAN;ITPUB个人空间(P.d+s#k*I(b)AH
5 I NUMBER DEFAULT 3;
"E y/JLZr&I06 BEGINITPUB个人空间shy}~(`_6V o
7 --DBMS_OUTPUT.PUT_LINE(2);
F2j&B.hhAV08 V_RESULT(1) := 2;ITPUB个人空间}6EobEa
9 WHILE(I < 100000) LOOPITPUB个人空间b`;v`T'Kz?B
EB8S
10 V_FLAG := TRUE;ITPUB个人空间:w-E&\w3Rb5Q,m
11 FOR J IN 1..V_RESULT.COUNT LOOP
z(Z&faEt~012 IF V_RESULT(J) * V_RESULT(J) > I THENITPUB个人空间D fQ#`;n}uyl
13 EXIT;
UW#~$] |_u/q014 END IF;
zF9Jpt+mN$W4e015 IF MOD(I,V_RESULT(J)) = 0 THEN
,G;e}.\5Raq}016 V_FLAG := FALSE;ITPUB个人空间FYz:J*^d!jT[
17 EXIT;ITPUB个人空间 g5Pd$r)Ipj&U
18 END IF;ITPUB个人空间-n$An|/_n
19 END LOOP;
?`P.g7q;I(c020 IF V_FLAG THEN
-no[)n,m:z1Y021 -- DBMS_OUTPUT.PUT_LINE(I);
O%wE#z`7F$F8H022 V_RESULT(V_RESULT.COUNT + 1) := I;
A`7zG4UY'D023 END IF;ITPUB个人空间 _2m:@+D0G
24 I := I + 2;
F[R9c:Kg:H025 END LOOP;
@\hhmoM026 END;ITPUB个人空间V }"bPN$R
27 /

PL/SQL 过程已成功完成。

已用时间: 00: 00: 01.03

难以置信吧，一个执行两个小时的PL/SQL，通过算法的调整可以优化到了1秒。

其实能优化的地方还有很多，不过这些优化能带来的性能提升已经很小了。比如：

SQL> DECLARE
g(BRC|,[ @02 TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;ITPUB个人空间Ep,s \ \x tl
3 V_RESULT T_RECORD;ITPUB个人空间 a$oFz;Q uiJ iqL7z r.x
4 V_FLAG BOOLEAN;
3^eP8@ R5wwx05 I NUMBER DEFAULT 3;
FBra6C#B06 BEGINITPUB个人空间B Wl:v{9`f
7 --DBMS_OUTPUT.PUT_LINE(2);ITPUB个人空间X1?|8n[O!VkW
8 V_RESULT(0) := 2;
$u;x[~:J Gh/W09 WHILE(I < 100000) LOOPITPUB个人空间 D\Wj
ck
10 V_FLAG := TRUE;ITPUB个人空间&n*T&mWm-j
11 FOR J IN 1..V_RESULT.COUNT - 1 LOOPITPUB个人空间Fk;yd [j
12 IF V_RESULT(J) * V_RESULT(J) > I THENITPUB个人空间C$M,P:Dih@:l
13 EXIT;
C!C[+wv"ZxKG9]014 END IF;ITPUB个人空间2I&c$_1W0Nz}Tj
15 IF MOD(I,V_RESULT(J)) = 0 THENITPUB个人空间|Rm`!{tT
16 V_FLAG := FALSE;ITPUB个人空间G[;t ^RYU
17 EXIT;ITPUB个人空间8bcHX&u|g%Q
18 END IF;
OB9mt&C$w@019 END LOOP;ITPUB个人空间)`fH-l B"\'A
20 IF V_FLAG THEN
*gO'z.U&d/wl021 -- DBMS_OUTPUT.PUT_LINE(I);
4oz;ZB9J&~g(sA S022 V_RESULT(V_RESULT.COUNT) := I;ITPUB个人空间_o)B \}6C_)FV
23 END IF;
g;j[*{"hiS7L024 I := I + 2;ITPUB个人空间~-s#V8tx
25 END LOOP;ITPUB个人空间$m ~6cw:Ep1Am
26 END;ITPUB个人空间E8S(q"j_`,`
27 /

PL/SQL 过程已成功完成。

已用时间: 00: 00: 00.96

由于从3开始步长为2，因此判断随后的质数的时候，没有必要用2去整除，而直接可以从3开始。

过程仍然可以进一步优化，可以省略掉不必要的赋值和判断语句：

SQL> DECLAREITPUB个人空间HU7A uhO
2 TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
5I~0H,JL4O gN2x03 V_RESULT T_RECORD;ITPUB个人空间
m8Ygi8C`c
4 I NUMBER DEFAULT 3;
nd,A&F$S)| Fh;s7B7R05 BEGINITPUB个人空间0iCC%K0{-r)]w G
6 --DBMS_OUTPUT.PUT_LINE(2);ITPUB个人空间#PTU8wg7O:d}+q_-oQ
7 V_RESULT(1) := 3;
ti0D%ej+lb#p5?rp08 WHILE(I < 100000) LOOP
Pbx|
F'bF {*k09 FOR J IN 1..V_RESULT.COUNT LOOP
7A,yYz6CQ,aS&h010 IF MOD(I,V_RESULT(J)) = 0 THENITPUB个人空间6of(b1s4npg
11 EXIT;ITPUB个人空间Ur_!BQ6n(FaA)~-c
12 END IF;
(cA.Rq@|,n013 IF V_RESULT(J) * V_RESULT(J) > I THEN
7N mR3yS4ns^r*o014 -- DBMS_OUTPUT.PUT_LINE(I);
:|&?+VKv I~
Ig015 V_RESULT(V_RESULT.COUNT + 1) := I;
J2\b T4r)km016 EXIT;ITPUB个人空间'g.m^(aW"egq
17 END IF;
5nf)GlwHl018 END LOOP;
}1H_,U9bR~"`019 I := I + 2;ITPUB个人空间+} oiBFwgJ\&{O}
20 END LOOP;ITPUB个人空间$G Vf1fw_e[
21 V_RESULT(0) := 2;
)z4P S1xlLNb)j'G022 END;
l_JG4@7`023 /

PL/SQL 过程已成功完成。

已用时间: 00: 00: 00.96

但是在100000这个数量级已经看不出性能的差别了。正如Tom所说的，系统总是可以提高1%的性能，不过付出的代价会越来越大。

刚才测试发现，将MOD函数转换一下，性能还会有一个相对明显的提升

SQL> DECLARE
| S@\&Il)|I[E02 TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;ITPUB个人空间4U6IY2G}gdb(i~
3 V_RESULT T_RECORD;ITPUB个人空间)w KM#eGm4V~
4 I NUMBER DEFAULT 3;
7YqM)Xt
Z Z?(e#A4k05 BEGIN
K"V%aV+C06 --DBMS_OUTPUT.PUT_LINE(2);
'c KgjSO07 V_RESULT(1) := 3;ITPUB个人空间0P!mJ6F.Om
8 WHILE(I < 100000) LOOPITPUB个人空间W.qYK8YJ&o)yw2jDv
9 FOR J IN 1..V_RESULT.COUNT LOOPITPUB个人空间$Mh&Zg/c*jofoU3mq
10 IF V_RESULT(J) * V_RESULT(J) > I THEN
"b\.Nxa4F)yW011 --DBMS_OUTPUT.PUT_LINE(I);
%D#QJk4s/@/z;@o012 V_RESULT(V_RESULT.COUNT + 1) := I;
e.q(s1N`_4R*O013 EXIT;ITPUB个人空间7Z%ZqAxh-K
14 END IF;
8L9[4sI)Lv015 IF TRUNC(I/V_RESULT(J)) = I/V_RESULT(J) THENITPUB个人空间}_(eMIT!Q\%k)s
16 EXIT;ITPUB个人空间&R&z
Z(C)Ay
17 END IF;ITPUB个人空间2ULQ7`U.}0QWC
18 END LOOP;
v)D5Ljz019 I := I + 2;
/yh(\~R%m020 END LOOP;ITPUB个人空间a`6aZinR
D5t
21 V_RESULT(0) := 2;
{8Wb'V+q XIyX&^ruK022 END;
{KkMkgR023 /

PL/SQL 过程已成功完成。

已用时间: 00: 00: 00.87

再来一次尝试：

SQL> DECLARE
)D*^ PJ/p5R+d C0 2 TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;ITPUB个人空间 OYpI._0XS
3 V_RESULT T_RECORD;ITPUB个人空间#r3W4g/}!k{|LT
4 I NUMBER DEFAULT 3;ITPUB个人空间.z H*m/j1],b~f
5 N NUMBER DEFAULT 0;
'J+Y/FZ~0 6 BEGINITPUB个人空间HLGHkS
7 --DBMS_OUTPUT.PUT_LINE(2);ITPUB个人空间}uE!{]
8 V_RESULT(1) := 3;
QRX$^]0 9 WHILE(I < 100000) LOOPITPUB个人空间Fu2i d9?$G ^I
10 FOR J IN 1..V_RESULT.COUNT LOOPITPUB个人空间V*yDm Y;S+H
11 IF V_RESULT(J) * V_RESULT(J) > I THENITPUB个人空间cn]-M G8z
12 --DBMS_OUTPUT.PUT_LINE(I);
qwqN@%y'sJ%q0 13 V_RESULT(V_RESULT.COUNT + 1) := I;
-V?%|T)f5qq0 14 EXIT;ITPUB个人空间"rq4|-{:ih`8?
15 END IF;
~8ezkdVjAD0 16 IF TRUNC(I/V_RESULT(J)) = I/V_RESULT(J) THENITPUB个人空间(Ci-V5S)}.r'as)z
17 EXIT;
|}F4lp+|T8y,k0 18 END IF;ITPUB个人空间m:e
Orp+bK
19 END LOOP;
f,@
ALh$mOK0 20 IF N = 2 THEN
yo+\{2Y!WRz:Y0 21 I := I + 4;ITPUB个人空间M0r;t x*k'p"]+{CMu
22 N := 1;
BIA8o.E9C&Py5^0 23 ELSE
4F$G
t)~/w:mkFH0 24 I := I + 2;ITPUB个人空间:C&w%nwJ~ S1i
25 N := N + 1;
,iOU.d$g5{&e%_?0 26 END IF;ITPUB个人空间 |&ku:C{'u$A
27 END LOOP;ITPUB个人空间i#MA~O@!A_
28 V_RESULT(0) := 2;ITPUB个人空间}|s(y'R0^+l k
29 END;
7EZpo*QC(VK(T]%O0 30 /

PL/SQL 过程已成功完成。

已用时间: 00: 00: 00.84

看来Tom说的确实没有错，优化的方法总是存在的。