趣味题

newkid · 发表于 2010-6-10 23:36

明明是自己有BUG还怀疑ORACLE有BUG, 惭愧惭愧!

WITH n AS (
SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9
)
,t (n1,n2,n3,n4,n5,n6,n7,n8,n9,lvl) AS (
SELECT n,0,0,0,0,0,0,0,0,1
   FROM n
WHERE n<=4
UNION ALL
SELECT t.n1
      ,DECODE(t.lvl,1,n.n,t.n2)
      ,DECODE(t.lvl,2,n.n,t.n3)
      ,DECODE(t.lvl,3,n.n,t.n4)
      ,DECODE(t.lvl,4,n.n,t.n5)
      ,DECODE(t.lvl,5,n.n,t.n6)
      ,DECODE(t.lvl,6,n.n,t.n7)
      ,DECODE(t.lvl,7,n.n,t.n8)
      ,DECODE(t.lvl,8,n.n,t.n9)
      ,t.lvl+1
   FROM t,n
WHERE n.n NOT IN (n1,n2,n3,n4,n5,n6,n7,n8,n9)
      AND (t.lvl=1 AND n.n>t.n1 AND n.n+t.n1<=9
            OR (t.lvl=2 AND n.n - t.n1- t.n2 IN (0,1))
            OR (t.lvl=5 AND n.n = MOD(t.n4+ t.n5,10))
            OR t.lvl IN (3,4,6,7,8)
            )
)
SELECT n1||n7||n4||' + '||n2||n8||n5||' = '||n3||n9||n6
  FROM t
WHERE lvl=9
   AND n1*100+n7*10+n4 + n2*100+n8*10+n5 = n3*100+n9*10+n6
   ;

性能:
Elapsed: 00:00:00.20

哈哈。

dingjun123 · 发表于 2010-6-10 23:38

真有研究精神！佩服！
这个题目有没有类似地使用的案例呢？

newkid · 发表于 2010-6-10 23:55

把OO的改得好懂一些, 主要是前面P(3,9)的排列：

WITH t AS (SELECT REPLACE(SYS_CONNECT_BY_PATH(rn,','),',') x
         FROM (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=9)
         WHERE LEVEL=3
         CONNECT BY NOCYCLE rn<> PRIOR rn AND LEVEL<=3
      )
select /*+ RULE */ a.x||'+'||b.x||'='||c.x
from t a,t b,t c
where a.x+b.x=c.x and a.x<'500'
   and a.x<b.x
   and translate('123456789','$'||a.x||b.x||c.x,'$') is null
   ;

TRANSLATE的使用必须赞一下。

newkid · 发表于 2010-6-11 00:38

原帖由 dingjun123 于 2010-6-10 23:38 发表
真有研究精神！佩服！
这个题目有没有类似地使用的案例呢？

就是做着玩。我用的递归WITH虽然不比OO的好，但是通过这个例子演示了递归WITH的强悍之处：
在递归的过程中，通过行转列的办法随时可以引用前面各层次的数据。
CONNECT BY只有一个PRIOR操作符，只看到前一层的。其他数据必须先用SYS_CONNECT_BY_PATH先存起来，事后再解析再访问。这样的后果是有些组合本来可以尽早剪掉的，不得不遍历完再过滤。

newkid · 发表于 2010-6-11 02:43

再改一下，去掉了一次连接：

WITH t AS (SELECT REPLACE(SYS_CONNECT_BY_PATH(rn,','),',') x
         FROM (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=9)
         WHERE LEVEL=3
         CONNECT BY NOCYCLE rn<> PRIOR rn AND LEVEL<=3
      )
select a.x||'+'||b.x||'='||(a.x+b.x)
from t a,t b
where a.x<'500'
   and a.x<b.x
   AND a.x+b.x <1000
   and translate('123456789','$'||a.x||b.x||(a.x+b.x),'$') is null
   ;

奇怪的是性能并无提升，可能是原来已经很好了。但那个讨厌的RULE提示总算可以去掉了。

〇〇 · 发表于 2010-6-11 05:42

没看懂，没有判断a+b=c，结果是对的
已选择168行。

已用时间: 00: 00: 02.17
41#
已选择168行。

已用时间: 00: 00: 01.84

newkid · 发表于 2010-6-11 05:49

原帖由〇〇于 2010-6-11 05:42 发表
没看懂，没有判断a+b=c，结果是对的
已选择168行。

已用时间: 00: 00: 02.17
41#
已选择168行。

已用时间: 00: 00: 01.84

不需要判断了，我只要a+b就行，c是从a+b算出来的。这就是我能省掉一次连接的道理呀。

〇〇 · 发表于 2010-6-11 05:54

明白了，如果a||b||a+b符合1-9不重复就是解，真高级

〇〇 · 发表于 2010-6-11 06:03

把问题的数据量改大些，看看不同办法的性能差距
如果x是0-f不同的16进制数字
求符合axxx+bxxx+cxxx=xxxx的所有组合
其中a<b<c

〇〇 · 发表于 2010-6-11 07:33

貌似很慢，从执行计划看不出什么

WITH t AS (SELECT REPLACE(SYS_CONNECT_BY_PATH(rn,','),',') x
         FROM (SELECT to_char(ROWNUM-1,'fmx') rn FROM DUAL CONNECT BY ROWNUM<=16)
         WHERE LEVEL=4
         CONNECT BY NOCYCLE rn<> PRIOR rn AND LEVEL<=4
      )
select count(*) from(
select a.x||'+'||b.x||'+'||c.x||'='||to_char(to_number(a.x,'fmxxxx')+to_number(b.x,'fmxxxx')+to_number(c.x,'fmxxxx'),'fmxxxx')s
from t a,t b,t c
where to_number(a.x,'fmxxxx')<to_number('8000','fmxxxx')
   and to_number(a.x,'fmxxxx')<to_number(b.x,'fmxxxx')
   and to_number(b.x,'fmxxxx')<to_number(c.x,'fmxxxx')
   AND to_number(a.x,'fmxxxx')+to_number(b.x,'fmxxxx')+to_number(c.x,'fmxxxx') <=to_number('fedc','fmxxxx')
   and translate('0123456789abcdef','$'||a.x||b.x||to_char(to_number(a.x,'fmxxxx')+to_number(b.x,'fmxxxx')+to_number(c.x,'fmxxxx'),'fmxxxx'),'$') is null
   );

SQL> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3519778244

------------------------------------------------------------------------------------------------------------------
| Id  | Operation                         | Name                      | Rows  | Bytes | Cost (%CPU)| Time    |
------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT                   |                         |    1 |  6006 |    8 (0)| 00:00:01 |
| 1 |  TEMP TABLE TRANSFORMATION       |                         |    |    |          |       |
| 2 | LOAD AS SELECT                   |                         |    |    |          |       |
|*  3 | FILTER                         |                         |    |    |          |       |
|*  4 |    CONNECT BY WITHOUT FILTERING |                         |    |    |          |       |
| 5 |    COUNT                         |                         |    |    |          |       |
| 6 |    VIEW                         |                         |    1 |    3 |    2 (0)| 00:00:01 |
| 7 |       COUNT                      |                         |    |    |          |       |
|*  8 |       CONNECT BY WITHOUT FILTERING|                         |    |    |          |       |
| 9 |       FAST DUAL                |                         |    1 |    |    2 (0)| 00:00:01 |
|  10 | SORT AGGREGATE                   |                         |    1 |  6006 |          |       |
|  11 | NESTED LOOPS                   |                         |    1 |  6006 |    6 (0)| 00:00:01 |
|  12 |    NESTED LOOPS                   |                         |    1 |  4004 |    4 (0)| 00:00:01 |
|* 13 |    VIEW                         |                         |    1 |  2002 |    2 (0)| 00:00:01 |
|  14 |    TABLE ACCESS FULL          | SYS_TEMP_0FD9D6639_16B6486 |    1 |    3 |    2 (0)| 00:00:01 |
|* 15 |    VIEW                         |                         |    1 |  2002 |    2 (0)| 00:00:01 |
|  16 |    TABLE ACCESS FULL          | SYS_TEMP_0FD9D6639_16B6486 |    1 |    3 |    2 (0)| 00:00:01 |
|* 17 |    VIEW                         |                         |    1 |  2002 |    2 (0)| 00:00:01 |
|  18 |    TABLE ACCESS FULL             | SYS_TEMP_0FD9D6639_16B6486 |    1 |    3 |    2 (0)| 00:00:01 |
------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

3 - filter(LEVEL=4)
4 - filter("RN"<>PRIOR "RN" AND LEVEL<=4)
8 - filter(ROWNUM<=16)
  13 - filter(TO_NUMBER("A"."X",'fmxxxx')<TO_NUMBER('8000','fmxxxx'))
  15 - filter(TO_NUMBER("A"."X",'fmxxxx')<TO_NUMBER("B"."X",'fmxxxx'))
  17 - filter(TO_NUMBER("B"."X",'fmxxxx')<TO_NUMBER("C"."X",'fmxxxx') AND
            TO_NUMBER("A"."X",'fmxxxx')+TO_NUMBER("B"."X",'fmxxxx')+TO_NUMBER("C"."X",'fmxxxx')<=TO_NUMBER('fedc','fmx
            xxx') AND TRANSLATE('0123456789abcdef','$'||"A"."X"||"B"."X"||TO_CHAR(TO_NUMBER("A"."X",'fmxxxx')+TO_NUMBE
            R("B"."X",'fmxxxx')+TO_NUMBER("C"."X",'fmxxxx'),'fmxxxx'),'$') IS NULL)

已选择38行。

已用时间:  00: 00: 00.06

[转载] 趣味题

回复 #45 newkid 的帖子

回复 #47 newkid 的帖子