Decode360's Blog

业精于勤而荒于嬉 QQ:150355677 MSN:decode360@hotmail.com

  BlogJava :: 首页 :: 新随笔 :: 联系 ::  :: 管理 ::
  397 随笔 :: 33 文章 :: 29 评论 :: 0 Trackbacks
用SQL计算100以内的质数
 
    蛮有意思的一段SQL,拿来看一下。
 

===========================================================
作者: yangtingkun(
http://yangtingkun.itpub.net )
发表于: 2008.01.07 23:23
分类: ORACLE
出处:
http://yangtingkun.itpub.net/post/468/450278
-----------------------------------------------------------
 
    以前写过一篇文章,描述如何使用PL/SQL来计算100以内的质数,今天重翻那篇文章的时候,突然想到,能不能用SQL来实现同样的功能。
 
    PLSQL计算质数: http://yangtingkun.itpub.net/post/468/53770
 
 
 
 
    其实这个功能用PLSQL实现最简单,思路也很清晰,判断一个数是否是质数,只需要检查这个数能否被比它小的质数整除就可以了。但是这种操作通过SQL来实现就十分的困难,因此这里通过另外一种方式来实现这个功能——构造。
 
通过查询100以内的数,去掉所有的合数,剩下的就是质数了:
 
SQL> WITH T
  2 AS
  3 (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 100)
  4 SELECT RN FROM T
  5 WHERE RN > 1
  6 MINUS
  7 SELECT A.RN * B.RN FROM T A, T B
  8 WHERE A.RN <= B.RN
  9 AND A.RN > 1
 10 AND B.RN > 1;
 
        RN
----------
         2
         3
         5
         7
        11
        13
        17
        19
        23
        29
        31
        37
        41
        43
        47
        53
        59
        61
        67
        71
        73
        79
        83
        89
        97
 
25 rows selected.
 
 
 
但是这种方法的效率明显要比PL/SQL的效率要低,如果取10000以内的质数:
 
 
SQL> SET TIMING ON
SQL> SET AUTOT TRACE STAT
SQL> WITH T
  2 AS
  3 (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 10000)
  4 SELECT RN FROM T
  5 WHERE RN > 1
  6MINUS
  7 SELECT A.RN * B.RN FROM T A, T B
  8 WHERE A.RN <= B.RN
  9 AND A.RN > 1
 10AND B.RN > 1;
 
1229 rows selected.
 
Elapsed: 00:02:41.54
 
Statistics
----------------------------------------------------------
        511 recursive calls
         81 db block gets
     180002 consistent gets
      65131 physical reads
        648 redo size
      17139 bytes sent via SQL*Net to client
       1276 bytes received via SQL*Net from client
         83 SQL*Net roundtrips to/from client
          2 sorts (memory)
          1 sorts (disk)
       1229 rows processed
 
 
这个SQL执行了2分半种以上,当然这个SQL还可以进行一下优化,比如A的取值可以小于10000的开方,而B的取值可以小于10000除以最小的质数:
 
 
SQL> WITH T
  2 AS
  3 (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 10000)
  4 SELECT RN FROM T
  5 WHERE RN > 1
  6 MINUS
  7 SELECT A.RN * B.RN FROM T A, T B
  8 WHERE A.RN <= B.RN
  9AND A.RN > 1
 10 AND A.RN <= 100
 11 AND B.RN > 1
 12 AND B.RN <= 5000;
 
1229 rows selected.
 
Elapsed: 00:00:00.78
 
Statistics
----------------------------------------------------------
          2 recursive calls
         23 db block gets
       1820 consistent gets
         16 physical reads
        692 redo size
      17139 bytes sent via SQL*Net to client
       1276 bytes received via SQL*Net from client
         83 SQL*Net roundtrips to/from client
          3 sorts (memory)
          0 sorts (disk)
       1229 rows processed
 
 
优化后,SQL的执行效率提高了3个数量级,其实这个SQL仍然是可以优化的,考虑除了2以外,所有的质数均为奇数:
 
 
SQL> WITH T
  2 AS
  3 (SELECT ROWNUM * 2 + 1 RN FROM DUAL CONNECT BY LEVEL < 4999)
  4 SELECT 2 FROM DUAL
  5 UNION ALL
  6 (
  7 SELECT RN FROM T
  8 WHERE RN > 1
  9 MINUS
 10 SELECT A.RN * B.RN FROM T A, T B
 11 WHERE A.RN <= B.RN
 12 AND A.RN > 1
 13 AND A.RN <= 100
 14 AND B.RN > 1
 15 AND B.RN <= 5000
 16 )
 17 ;
 
1229 rows selected.
 
Elapsed: 00:00:00.25
 
Statistics
----------------------------------------------------------
          2 recursive calls
         15 db block gets
        512 consistent gets
          8 physical reads
        648 redo size
      17138 bytes sent via SQL*Net to client
       1276 bytes received via SQL*Net from client
         83 SQL*Net roundtrips to/from client
          3 sorts (memory)
          0 sorts (disk)
       1229 rows processed
 
虽然通过SQL优化已经将极大的提高了效率,但是和PLSQL比,效率仍然相去甚远:
 
 
 
SQL> DECLARE
  2 TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
  3 V_RESULT T_RECORD;
  4 I NUMBER DEFAULT 3;
  5 N NUMBER DEFAULT 0;
  6 BEGIN
  7 --DBMS_OUTPUT.PUT_LINE(2);
  8 V_RESULT(1) := 3;
  9 WHILE(I < 10000) LOOP
 10 FOR J IN 1..V_RESULT.COUNT LOOP
 11 IF V_RESULT(J) * V_RESULT(J) > I THEN
 12 --DBMS_OUTPUT.PUT_LINE(I);
 13 V_RESULT(V_RESULT.COUNT + 1) := I;
 14 EXIT;
 15 END IF;
 16 IF TRUNC(I/V_RESULT(J)) = I/V_RESULT(J) THEN
 17 EXIT;
 18END IF;
 19 END LOOP;
 20 IF N = 2 THEN
 21 I := I + 4;
 22 N := 1;
 23 ELSE
 24 I := I + 2;
 25 N := N + 1;
 26 END IF;
 27 END LOOP;
 28 V_RESULT(0) := 2;
 29 END;
 30 /
 
PL/SQL procedure successfully completed.
 
Elapsed: 00:00:00.04
 
这说明使用SQL并不一定就是最佳选择,有的时候使用PLSQL效率反而会更高。使用合适的方法做适合的事情,一味追求使用单条SQL实现很可能会损失性能。
 

 
posted on 2008-12-27 21:31 decode360 阅读(319) 评论(0)  编辑  收藏 所属分类: 05.SQL

只有注册用户登录后才能发表评论。


网站导航: