ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 用SQL计算100以内的质数

用SQL计算100以内的质数

原创 Linux操作系统 作者:yangtingkun 时间:2008-01-07 23:22:59 0 删除 编辑

以前写过一篇文章,描述如何使用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行。

但是这种方法的效率明显要比PL/SQL的效率要低,如果取10000以内的质数:

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
  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;

已选择1229行。

已用时间:  00: 02: 41.54

统计信息
----------------------------------------------------------
        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
  9  AND A.RN > 1
 10  AND A.RN <= 100
 11  AND B.RN > 1
 12  AND B.RN <= 5000;

已选择1229行。

已用时间:  00: 00: 00.78

统计信息
----------------------------------------------------------
          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行。

已用时间:  00: 00: 00.25

统计信息
----------------------------------------------------------
          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;
 18     END 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 过程已成功完成。

已用时间:  00: 00: 00.04
SQL>

这说明使用SQL并不一定就是最佳选择,有的时候使用PLSQL效率反而会更高。使用合适的方法做适合的事情,一味追求使用单条SQL实现很可能会损失性能。

 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/4227/viewspace-117509/,如需转载,请注明出处,否则将追究法律责任。

下一篇: ORA-21561错误
请登录后发表评论 登录
全部评论
暂无介绍

注册时间:2007-12-29

  • 博文量
    1955
  • 访问量
    10486275