递归with真是个好东西

tree_new_bee

太疯狂了。

不过，看进度条似乎明天就能出来了， 只是不知进度条准不准。

〇〇

原帖由 tree_new_bee 于 2010-12-12 17:31 发表
太疯狂了。

不过，看进度条似乎明天就能出来了， 只是不知进度条准不准。

plsql求10,20~1E7的最大公约数

SQL> declare
  2  a number;
  3  b number;
  4  tmp number;
  5  gcd number;
  6  begin
  7  b:=10;
  8  for i in 2..1E6 loop
  9  a:=i*10;
10  b:=case i when 2 then b else gcd end;
11  while a<>0 loop
12  tmp:=a;
13  a:=mod(b,a);
14  b:=tmp;
15  end loop;
16  gcd:=b;
17  end loop;
18  dbms_output.put_line(gcd);
19  end;
20  /
10

PL/SQL 过程已成功完成。

已用时间:  00: 00: 02.02

tree_new_bee

原帖由 〇〇 于 2010-12-12 18:47 发表

plsql求10,20~1E7的最大公约数

PLSQL容易微调一些。

上面的代码，调整一下顺序，尽量让每次都是大数mod小数， 可以节省一半的mod操作。

declare
  a   number;
  b   number;
  tmp number;
  gcd number;
begin
  b := 20;
  for i in 2 .. 1E6 loop
    a := i * 10;
    --b := case i when 2 then b else gcd end;
    while b <> 0 loop
      tmp := b;
      b   := mod(a, b);
      a   := tmp;
    end loop;
    b:=a;
  end loop;
  dbms_output.put_line(b);
end;

改过后， 在我这里从1.9s, 降到0.7s

lastwinner

原帖由 tree_new_bee 于 10-12-10 13:05 发表

什么叫射一下？

流氓兔的流氓招数

〇〇

原帖由 tree_new_bee 于 2010-12-12 17:31 发表
太疯狂了。

不过，看进度条似乎明天就能出来了， 只是不知进度条准不准。

出来了

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

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

已用时间:  59: 31: 03.74

〇〇

原帖由 tree_new_bee 于 2010-12-12 17:31 发表
太疯狂了。

不过，看进度条似乎明天就能出来了， 只是不知进度条准不准。

怎么看出来的？

tree_new_bee

原帖由 〇〇 于 2010-12-13 07:46 发表

怎么看出来的？

这个需要很很internel的oracle知识和高深的数学知识才能做到了：

进度条当时显示的大约为满格的3/4左右， 而当时运行了2天， 所以剩余时间大概要半天左右。

newkid

原帖由 〇〇 于 2010-12-12 13:43 发表
newkid的gcd
SQL> WITH n AS (
  2  select level*10 n from dual connect by level  

我的写法每一步都会和集合n做连接，如果n很大, 效率就成问题。NB哥的好一些因为他只是在b2=0才会执行一个子查询。
如果集合是很有规律的，那么只要在递归的每一步生成新数据就行了，集合n没有必要：
WITH t (id,a,b,gcd) AS (
  SELECT 10,0,1,10 FROM DUAL
  UNION ALL
  SELECT DECODE(t.a,0,t.id+10,t.id)
        ,DECODE(t.a,0,t.id+10,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<1E5 OR t.id=1E5 AND t.a<>0)
)
SELECT gcd FROM t WHERE a=0 AND id=1E5;


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

Elapsed: 00:00:00.45


如果集合n不能省略，最好的办法就是把它变成hash表放在内存里直接访问，可惜ORACLE的递归WITH没有这高级功能。
改用MODEL, 引用效率高了，但是没办法精确控制迭代次数，不得不先构造一个笛卡尔积。
SELECT b
   FROM (SELECT *
           FROM (SELECT ROWNUM n
                       ,ROWNUM*10 val ---- 用另外的列存放要求公倍数的值。不一定是连续的自然数
                   FROM DUAL
                 CONNECT BY ROWNUM<=1e4)
               ,(SELECT ROWNUM col
                   FROM DUAL
                CONNECT BY ROWNUM<=30 ---- 假设辗转相除法迭代次数不超过30
                )
         MODEL IGNORE NAV RETURN UPDATED ROWS
         DIMENSION BY (n,col)
         MEASURES (val,0 a,val b)
         RULES AUTOMATIC ORDER (
                a[n>1,any] order by n,col = CASE WHEN cv(col)=1 THEN val[cv(),cv()]
                                                 WHEN a[cv(),cv()-1]<>0 THEN MOD(b[cv(),cv()-1],a[cv(),cv()-1])
                                                 ELSE 0
                                            END
               ,b[n>1,any] order by n,col = CASE WHEN cv(col)=1 THEN b[cv()-1,30]
                                                 WHEN a[cv(),cv()-1]<>0 THEN a[cv(),cv()-1]
                                                 ELSE b[cv(),cv()-1]
                                            END
                )
         )
WHERE n=1E4 and col=30;

         B
----------
        10

Elapsed: 00:00:11.73

〇〇

nice

tree_new_bee

看OO的2^1000的帖子：  http://www.itpub.net/viewthread. ... ;page=1#pid13982681
用递归做了两个任意大数相乘：


with t0 as (select
'1234567' arg1,
'87654321' arg2
from dual)
,t1 as (select rownum pos, substr(arg1, -rownum, 1) d from t0 connect by rownum<=length(arg1))
,t2 as (select 2 id , rownum pos, substr(arg2, -rownum, 1) d from t0 connect by rownum<=length(arg2))
,t3 as (select t1.pos+t2.pos-2 pos,  sum(t1.d*t2.d) p from t1 ,t2 group by t1.pos+t2.pos-2)
,t(r, d, m, str) as(
select 0, 0, 0, cast ('' as varchar2(4000))  from dual
union all
select
r+1,
p,
trunc((m+p)/10),
trunc((m+p)/10) ||mod(m+p,10) || substr(str,2)
from t, t3 where r=pos)
select  * from t where r = (select max(r) from t)

         R          D          M STR
---------- ---------- ---------- --------------------------------------------------------------------------------
        14          8          1 10821155183522114007


Executed in 0.078 seconds


想扩展到多个大数相乘， 还没头绪。

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