递归with真是个好东西

〇〇

6小时了，还没动静
SQL> with t as (
  2  select level*10 n from dual connect by level<=1E6)
  3  ,t1 as (select n n1, lead(n ,1) over (order by n desc) n2 from t )
  4  ,t2 as (select max(n1) n1, max(n2)n2  from t1 )
  5  , mgcd(a,b, a2, b2) as
  6  (select n1, n2, n1, n2 from t2
  7  union all
  8  select
  9  case when b2=0 then (select max(n) from t where n<a) else a end,
10  case when b2=0 then a2 else b end,
11  case when b2=0 then (select max(n) from t where n<a) else b2 end,
12  case when b2=0 then  a2 else mod(a2, b2) end
13  from mgcd where a is not null
14  )
15  cycle a,b,a2,b2 set iscycle to 'y' default 'n'
16  select min(a2) from mgcd where b2=0
17
SQL> /

又找到1个测试机器的好东西

tree_new_bee

原帖由 〇〇 于 2010-12-10 21:25 发表
6小时了，还没动静
SQL> with t as (
  2  select level*10 n from dual connect by level

你跟机器有仇啊？


1E6,我这里直接报内存不够。大概是pga太小。
5E3, 要9秒
1E4, 要35秒。
2E4, 要130秒
看样子参数加大一倍， 时间要4倍。 照这么推算， 1E5, 估计要一个小时。1E6如果不报错则要1000个小时， 也就是40天吧！

newkid

我写的：

最小公倍数：
WITH n AS (
SELECT 4 n FROM DUAL
UNION ALL SELECT 9 FROM DUAL
UNION ALL SELECT 6 FROM DUAL
UNION ALL SELECT 15 FROM DUAL
)
,n2 AS (SELECT ROWNUM id,COUNT(*) OVER() cnt,n FROM n)
,t (id,cnt,val,a,b,lcm) AS (
  SELECT id,cnt,n,0,1,n FROM n2 WHERE id=1
  UNION ALL
  SELECT DECODE(t.a,0,t.id+1,t.id)
        ,t.cnt
        ,n2.n
        ,DECODE(t.a,0,n2.n,MOD(t.b,t.a))
        ,DECODE(t.a,0,t.lcm,t.a)
         END
        ,DECODE(mod(t.b,t.a),0,t.lcm*t.val/t.a,t.lcm)
    FROM t,n2
   WHERE (t.id<t.cnt OR t.id=t.cnt AND t.a<>0)
         AND DECODE(t.a,0,t.id+1,t.id) = n2.id
)
SELECT lcm FROM t WHERE a=0 AND id=cnt;



       LCM
----------
       180


最大公约数：
WITH n AS (
SELECT 20 n FROM DUAL
UNION ALL SELECT 16 FROM DUAL
UNION ALL SELECT 18 FROM DUAL
UNION ALL SELECT 12 FROM DUAL
)
,n2 AS (SELECT ROWNUM id,COUNT(*) OVER() cnt,n FROM n)
,t (id,cnt,val,a,b,gcd) AS (
  SELECT id,cnt,n,0,1,n FROM n2 WHERE id=1
  UNION ALL
  SELECT DECODE(t.a,0,t.id+1,t.id)
        ,t.cnt
        ,n2.n
        ,DECODE(t.a,0,n2.n,MOD(t.b,t.a))
        ,DECODE(t.a,0,t.gcd,t.a)
        ,DECODE(mod(t.b,t.a),0,t.a,t.gcd)
    FROM t,n2
   WHERE (t.id<t.cnt OR t.id=t.cnt AND t.a<>0)
         AND DECODE(t.a,0,t.id+1,t.id) = n2.id
)
SELECT gcd FROM t WHERE a=0 AND id=cnt;


       GCD
----------
         2

如果是连续自然数则集合n可以忽略，下面是1~1E6的GCD:
WITH t (id,a,b,gcd) AS (
  SELECT 1,0,1,1 FROM DUAL
  UNION ALL
  SELECT DECODE(t.a,0,t.id+1,t.id)
        ,DECODE(t.a,0,t.id+1,MOD(t.b,t.a))
        ,DECODE(t.a,0,t.gcd,t.a)
        ,DECODE(mod(t.b,t.a),0,t.a,t.gcd)
    FROM t
   WHERE (t.id<1E6 OR t.id=1E6 AND t.a<>0)
)
SELECT gcd FROM t WHERE a=0 AND id=1E6;



       GCD
----------
         1

Elapsed: 00:01:43.66

当然这没什么意思。

我在新出的书中有一章专门写这个递归WITH（包括那个斐波那契数）, 另外还有很多例子散落在论坛的回帖中。

[ 本帖最后由 newkid 于 2010-12-11 03:59 编辑 ]

tree_new_bee

原帖由 newkid 于 2010-12-10 22:33 发表
我写的：

最小公倍数：

好！
lcm(a,b) = a*b/gcd(a,b)
lcm(a,b,c) = lcm(lcm(a,b), c) = lcm(a,b) * c / gcd(lcm(a,b), c)

newkid

关于这个gcd,lcm,如果你想自虐的话，我建议你再用MODEL写一遍

tree_new_bee

原帖由 newkid 于 2010-12-11 11:04 发表
关于这个gcd,lcm,如果你想自虐的话，我建议你再用MODEL写一遍

哈，又布置作业了。

with还没玩够， 先不急着玩model, 看着model 不如with舒服。

tree_new_bee

用上面的菲波纳契数列解euler project第2题(用通项公式就没意思了)

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

WITH t(a,b) AS (
SELECT 0,1 FROM DUAL
UNION ALL
SELECT b
      ,a+b
  FROM t
WHERE a+b<4000000
)
select sum(b) from t where mod(b,2)=0

SQL> /

    SUM(B)
----------
   4613732

Executed in 0.032 seconds

这个还可以改进：
通过观察fab数列，可以知道： 偶fab数每隔2个出现一个， 所以可以计算如下：
f(n) = f(n-1) + f(n-2)
= f(n-2) + f(n-3) + f(n-3) + f(n-4)
= 2*(f(n-3) + f(n-2) ) + f(n-4)
= 3* f(n-3) + 2*f(n-4)
= 3* f(n-3) + f(n-4) + f(n-5) + f(n-6))
= 4 * f(n-3) + f(n-6)

这样，优化的结果是：
WITH t(a,b) AS (
SELECT 0,2 FROM DUAL
UNION ALL
SELECT b
      ,a+4*b
  FROM t
WHERE a+4*b<4000000
)
select sum(b) from t


SQL> /

    SUM(B)
----------
   4613732

Executed in 0.016 seconds


不过，优化实际上没什么实质效果，两个语句在number精度范围内的任何数上运行，都几乎是同样的常数时间。

[ 本帖最后由 tree_new_bee 于 2010-12-11 14:31 编辑 ]

〇〇

newkid的gcd
SQL> WITH n AS (
  2  select level*10 n from dual connect by level <=1e4
  3  )
  4  ,n2 AS (SELECT ROWNUM id,COUNT(*) OVER() cnt,n FROM n)
  5  ,t (id,cnt,val,a,b,gcd) AS (
  6    SELECT id,cnt,n,0,1,n FROM n2 WHERE id=1
  7    UNION ALL
  8    SELECT DECODE(t.a,0,t.id+1,t.id)
  9          ,t.cnt
10          ,n2.n
11          ,DECODE(t.a,0,n2.n,MOD(t.b,t.a))
12          ,DECODE(t.a,0,t.gcd,t.a)
13          ,DECODE(mod(t.b,t.a),0,t.a,t.gcd)
14      FROM t,n2
15     WHERE (t.id<t.cnt OR t.id=t.cnt AND t.a<>0)
16           AND DECODE(t.a,0,t.id+1,t.id) = n2.id
17  )
18  SELECT gcd FROM t WHERE a=0 AND id=cnt;

       GCD
----------
        10

已用时间:  00: 00: 40.19

tnb的
SQL> with t as (
  2  select level*10 n from dual connect by level<=1E4)
  3  ,t1 as (select n n1, lead(n ,1) over (order by n desc) n2 from t )
  4  ,t2 as (select max(n1) n1, max(n2)n2  from t1 )
  5  , mgcd(a,b, a2, b2) as
  6  (select n1, n2, n1, n2 from t2
  7  union all
  8  select
  9  case when b2=0 then (select max(n) from t where n<a) else a end,
10  case when b2=0 then a2 else b end,
11  case when b2=0 then (select max(n) from t where n<a) else b2 end,
12  case when b2=0 then  a2 else mod(a2, b2) end
13  from mgcd where a is not null
14  )
15  cycle a,b,a2,b2 set iscycle to 'y' default 'n'
16  select min(a2) from mgcd where b2=0;

   MIN(A2)
----------
        10

已用时间:  00: 00: 21.92

SQL> 2
  2* select level*10 n from dual connect by level<=1E4)
SQL> c/1E/2E
  2* select level*10 n from dual connect by level<=2E4)
SQL> /

   MIN(A2)
----------
        10

已用时间:  00: 01: 26.16
SQL> 2
  2* select level*10 n from dual connect by level<=2E4)
SQL> c/2E/4E
  2* select level*10 n from dual connect by level<=4E4)
SQL> /

   MIN(A2)
----------
        10

已用时间:  00: 05: 45.83
SQL> 2
  2* select level*10 n from dual connect by level<=4E4)
SQL> c/4E/16E
  2* select level*10 n from dual connect by level<=16E4)
SQL> /

   MIN(A2)
----------
        10

已用时间:  01: 29: 33.37
SQL>

[ 本帖最后由 〇〇 于 2010-12-13 07:35 编辑 ]

tree_new_bee

原帖由 〇〇 于 2010-12-10 21:25 发表
6小时了，还没动静

OO， 前面测那个， 等到最终结果了吗？  多少时间？

〇〇

原帖由 tree_new_bee 于 2010-12-12 16:43 发表


OO， 前面测那个， 等到最终结果了吗？  多少时间？

还在执行看不到结果