ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 利用HASH CLUSTER判断质数

利用HASH CLUSTER判断质数

原创 Linux操作系统 作者:yangtingkun 时间:2009-06-24 23:36:18 0 删除 编辑

以前写过几篇文章,描述在Oracle如何通过SQLPL/SQL判断一个数是否是质数,没想到这个功能在Oracle中已经内置了。

 

 

首要要说的是,Oracle并没有给出一个接口来实现这个功能,但是Oracle在建立HASH CLUSTER的时候要求HASHKEYS必须是质数,因此上Oracle实际已经内置了这个功能。

这篇文章只是描述这个现象,并不是说这个方法是判断一个数是否为质数的好办法,实际上这个方法是相对糟糕的办法,不但需要执行DDL,而且CLUSTER真正的创建了,还会实际的分配空间,如果输入的数值比较大,所在表空间很可能会报空间不足的错误。

SQL> CREATE CLUSTER C_TEST (ID NUMBER) HASHKEYS 13;

簇已创建。

SQL> SELECT HASHKEYS FROM USER_CLUSTERS WHERE CLUSTER_NAME = 'C_TEST';

  HASHKEYS
----------
        13

SQL> DROP CLUSTER C_TEST;

簇已删除。

SQL> CREATE CLUSTER C_TEST (ID NUMBER) HASHKEYS 25;

簇已创建。

SQL> SELECT HASHKEYS FROM USER_CLUSTERS WHERE CLUSTER_NAME = 'C_TEST';

  HASHKEYS
----------
        29

SQL> DROP CLUSTER C_TEST;

簇已删除。

如果输入的HASHKEYS是质数,则Oracle会使用输入的值作为HASH CLUSTERHASHKEYS,如果不是,Oracle会寻找大于输入值的最接近的质数。

如果愿意,可以将上面的三个步骤封装为一个过程,不过这种方法实在是缺点很多,因此就没有什么必要了。

SQL> SET TIMING ON
SQL> CREATE CLUSTER C_TEST (ID NUMBER) HASHKEYS 10001;

簇已创建。

已用时间:  00: 16: 00.63
SQL> SELECT HASHKEYS FROM USER_CLUSTERS WHERE CLUSTER_NAME = 'C_TEST';

  HASHKEYS
----------
     10007

已用时间:  00: 00: 00.00

可以看到,指定HASHKEYS10001,居然运行了16分钟,虽然这台服务器的处理能力确实很低,但是这个速度也太慢了一点。

SQL> SELECT BYTES/1024/1024 FROM USER_SEGMENTS WHERE SEGMENT_NAME = 'C_TEST';

BYTES/1024/1024
---------------
            320

已用时间:  00: 00: 00.44

可以看到,Oracle实际上已经为C_TEST分配了320M的空间。

当然这时使用了默认的SIZE参数所造成的后果,其实可以优化这个创建操作,使得Oracle预分配的空间最小。

首先检查Oracle每个块所允许的最大HASHKEY数量:

SQL> CREATE CLUSTER C_TEST (ID NUMBER) HASHKEYS 10001 SIZE 1;
CREATE CLUSTER C_TEST (ID NUMBER) HASHKEYS 10001 SIZE 1
*
1 行出现错误:
ORA-02454:
每块的散列关键字数 (32658) 超出最大数 256


已用时间:  00: 00: 00.02
SQL> SELECT 32658/256 FROM DUAL;

 32658/256
----------
127.570313

已用时间:  00: 00: 00.02
SQL> CREATE CLUSTER C_TEST (ID NUMBER) HASHKEYS 10001 SIZE 128;

簇已创建。

已用时间:  00: 00: 02.30
SQL> SELECT HASHKEYS FROM USER_CLUSTERS WHERE CLUSTER_NAME = 'C_TEST';

  HASHKEYS
----------
     10007

已用时间:  00: 00: 00.01
SQL> SELECT BYTES/1024/1024 FROM USER_SEGMENTS WHERE SEGMENT_NAME = 'C_TEST';

BYTES/1024/1024
---------------
              2

已用时间:  00: 00: 00.04

根据上面得到的256这个最大值,设置HASH CLUSTERSIZE128,这时创建时间只用了2.3秒就完成了。

当然虽然经过了优化,这个速度要比一个很普通的计算质数的算法仍然要慢得多:

SQL> set serverout on
SQL> DECLARE
  2     I NUMBER DEFAULT 10001;
  3     V_FLAG VARCHAR2(5) := 'TRUE';
  4  BEGIN
  5     FOR J IN 2 .. TRUNC(POWER(I, 0.5)) LOOP
  6             IF MOD(I,J) = 0 THEN
  7                     V_FLAG := 'FALSE';
  8                     EXIT;
  9             END IF;
 10     END LOOP;
 11     DBMS_OUTPUT.PUT_LINE(V_FLAG);
 12  END;
 13  /
FALSE

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.05
SQL> DECLARE
  2     I NUMBER DEFAULT 10007;
  3     V_FLAG VARCHAR2(5) := 'TRUE';
  4  BEGIN
  5     FOR J IN 2 .. TRUNC(POWER(I, 0.5)) LOOP
  6             IF MOD(I,J) = 0 THEN
  7                     V_FLAG := 'FALSE';
  8                     EXIT;
  9             END IF;
 10     END LOOP;
 11     DBMS_OUTPUT.PUT_LINE(V_FLAG);
 12  END;
 13  /
TRUE

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.02

一个很普通的PL/SQL算法,就可以在0.05秒内完成计算。

不过利用HASH CLUSTER的方法来判断质数,倒是与用SQL方式实现的效率相差不多:

SQL> UNDEF NUM
SQL> WITH
  2     T AS (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL <= &&NUM/2)
  3  SELECT &NUM
  4     || DECODE
  5     (
  6             (
  7                     SELECT &NUM FROM DUAL
  8                     MINUS
  9                     SELECT A.RN * B.RN FROM T A, T B
 10                     WHERE A.RN <= ROUND(POWER(&NUM, 0.5))
 11                     AND B.RN >= ROUND(POWER(&NUM, 0.5))
 12             ),
 13             NULL,
 14             '
'
 15     )
 16     || '
是质数'
 17  FROM DUAL;
输入 num 的值:  10001
原值    2:      T AS (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL <= &&NUM/2)
新值    2:      T AS (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL <= 10001/2)
原值    3: SELECT &NUM
新值    3: SELECT 10001
原值    7:                      SELECT &NUM FROM DUAL
新值    7:                      SELECT 10001 FROM DUAL
原值   10:                      WHERE A.RN <= ROUND(POWER(&NUM, 0.5))
新值   10:                      WHERE A.RN <= ROUND(POWER(10001, 0.5))
原值   11:                      AND B.RN >= ROUND(POWER(&NUM, 0.5))
新值   11:                      AND B.RN >= ROUND(POWER(10001, 0.5))

10001||DECODE((SELECT10001
--------------------------
10001
不是质数

已用时间:  00: 00: 01.93
SQL> UNDEF NUM
SQL> WITH
  2     T AS (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL <= &&NUM/2)
  3  SELECT &NUM
  4     || DECODE
  5     (
  6             (
  7                     SELECT &NUM FROM DUAL
  8                     MINUS
  9                     SELECT A.RN * B.RN FROM T A, T B
 10                     WHERE A.RN <= ROUND(POWER(&NUM, 0.5))
 11                     AND B.RN >= ROUND(POWER(&NUM, 0.5))
 12             ),
 13             NULL,
 14             '
'
 15     )
 16     || '
是质数'
 17  FROM DUAL;
输入 num 的值:  10007
原值    2:      T AS (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL <= &&NUM/2)
新值    2:      T AS (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL <= 10007/2)
原值    3: SELECT &NUM
新值    3: SELECT 10007
原值    7:                      SELECT &NUM FROM DUAL
新值    7:                      SELECT 10007 FROM DUAL
原值   10:                      WHERE A.RN <= ROUND(POWER(&NUM, 0.5))
新值   10:                      WHERE A.RN <= ROUND(POWER(10007, 0.5))
原值   11:                      AND B.RN >= ROUND(POWER(&NUM, 0.5))
新值   11:                      AND B.RN >= ROUND(POWER(10007, 0.5))

10007||DECODE((SELECT10007
--------------------------
10007
是质数

已用时间:  00: 00: 01.92

绝大多数情况下,使用Oracle内置的功能都能得到更好的效果,当然也有反例。比如利用空间数据库求两点间距离,再比如这个例子。

有时候并不是Oracle内置的算法不优秀,而是使用这个方法不合适。

当前这个例子就不用说了,Oracle本来没有打算提供这个功能,这只是Oracle实现HASH CLUSTER的一个隐含功能而已,如果直接拿来使用,势必有很多问题。

利用空间数据库求两点距离也是类似的道理,Oracle提供的空间数据库功能很强大,能实现很多的空间计算功能,如果只是用来求两点间距离,实在是小题大做。正因为它的功能强大,使得Oracle将结构定义的十分复杂,因此在计算也会十分复杂,而直接通过SQLPL/SQL实现代码简单得多,自然效率也高得多。

用合适的工具做适合的事情,效率才会提高。

 

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

请登录后发表评论 登录
全部评论
暂无介绍

注册时间:2007-12-29

  • 博文量
    1955
  • 访问量
    10426047