Euler Project 挨个做 - 之一(Q1-50)

〇〇

数组要是预先申请空间会不会改善

newkid

原帖由 〇〇 于 2010-12-16 09:23 发表
数组要是预先申请空间会不会改善

我这里用的是INDEX BY数组，其实是很稀疏的，但是它的下标竟然一度溢出，超过了PLS_INTEGER的精度。所以无法预先申请。

tree_new_bee

原帖由 〇〇 于 2010-12-16 09:23 发表
数组要是预先申请空间会不会改善

index by table 是用类似hash的方法来管理的稀疏数组(猜测的， 没查文档确认)， 人为预留空间不仅仅是在预留时浪费很多空间， 而且大大增加了hash值冲突的机会， 使得整个数组的查询操作开销加大。

原帖由 newkid 于 2010-12-16 09:28 发表

但是它的下标竟然一度溢出，超过了PLS_INTEGER的精度。所以无法预先申请。

对于测试结果中的837799， 他曾经到过的最高节点是： 56991483520 ！

tree_new_bee

关于这个Collatz问题， 可以到这里扩展阅读一下：
http://blog.sina.com.cn/s/blog_4dd633660100n495.html
共有连续八篇文章。

因为文中用二进制来展现Collatz数，所以也许可以为我们用二进制解决问题带来帮助。

〇〇

原帖由 tree_new_bee 于 2010-12-15 19:52 发表
现在增加一点人肉成分：
对于偶数，没什么好分析的。
来看奇数n：
奇数n的下一步是3n+1, 3n+1一定是偶数， 所以再下一步一定是(3n+1)/2
假设n=2k+1
则n的下两步是(3n+1)/2 = (3*(2k+1)+1)/2 = (6k+4)/2 = 3k+2
而3k+2 > 2k+1
这就意味着： 所有3n+2形式的数字，都处于它之前的某个奇数的路径上， 因此可以忽略。

忽略这些数，可以节省1/3的循环时间。


declare
  maxchain    number := 0;
  maxchainnum number := 0;
  icopy       number;
  icopy2      number;
  len         number;
  i           number;
begin
  for k in 0 .. 1000000/3-1 loop
    for j in 0..1 loop
      i:= 3*k+j;
      icopy := i;
      len   := 1;
      while icopy > 1 loop
        if bitand(icopy, 1) = 0 then
          icopy := icopy / 2;
        else
          icopy := icopy * 3 + 1;
        end if;
        len := len + 1;
      end loop;
   
      if len > maxchain then
        maxchain    := len;
        maxchainnum := i;
      end if;
    end loop;   
  end loop;
  dbms_output.put_line('number: ' || maxchainnum || ' chains: ' ||
                       maxchain);
end;


number: 837799 chains: 525

PL/SQL procedure successfully completed

Executed in 55.157 seconds

(85-55)/85 = 35%,  果然节省了1/3左右的时间。

编译器本地编译优化
SQL> exec threen;
number: 837799 chains: 525

PL/SQL 过程已成功完成。

已用时间:  00: 00: 57.79
SQL> ALTER PROCEDURE threen COMPILE PLSQL_CODE_TYPE = NATIVE;

过程已更改。

已用时间:  00: 00: 00.17
SQL> exec threen;
number: 837799 chains: 525

PL/SQL 过程已成功完成。

已用时间:  00: 00: 47.60

貌似你的比ｎｅｗｋｉｄ的机器好优化 three_tnb.sql (8.58 KB, 下载次数: 24)

2010-12-16 10:54 上传

点击文件名下载附件

[ 本帖最后由 〇〇 于 2010-12-16 10:54 编辑 ]

tree_new_bee

原帖由 〇〇 于 2010-12-16 10:42 发表

貌似你的比ｎｅｗｋｉｄ的机器好优化

看样子似乎是因为数组操作变成机器代码不会有更多的改善， 而单纯的循环/bitand这样的操作受益更多。

tree_new_bee

Q15: Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?
Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.



How many routes are there through a 20×20 grid?


别的题都是考虑好比较理想的方案后才发的帖子， 这个还没想好， 先一步一步贴。

tree_new_bee

注意， 题中把示例图称为2*2的grid, 我倒觉得这应该算是3*3的grid. 为了避免混淆，我在解题的时候把参数都定义为n+1. n代表原题定义的参数， n+1表示我理解的参数。


先来用最直观的方法来解。

with targ as (select 7+1 arg from dual)
,tree as (select rownum x from dual connect by rownum<=2)
, t (step, r, c,path) as
(select 0 step, 1 r, 1 c, cast ('' as varchar2(2000))  from dual
union all
select
step+1,
case when (x=2 and r< arg) or c=arg then  r+1 else r end,
case when (x=1 and c< arg) or r=arg then  c+1 else c end,
path || '|' || r || ',' || c
from t, tree,targ where step<arg*2 )
cycle step,r,c set iscycle to 'y' default 'n'
--select distinct path from t,targ where step = arg*2
select count(distinct path) from t,targ where step = arg*2

COUNT(DISTINCTPATH)
-------------------
              12870

Executed in 18.11 seconds


8+1的参数下， 要18秒， 9+1以上的不敢尝试了。


上面的代码中，Tree表是为了制造2叉数， 使从每个节点开始分别选择向右(1)和向下走(2)。

tree_new_bee

上面的稍稍改进一下， 就是一旦走到右边和上边，就没有选择了，就可以终止往下走了。 增加一个stop列， 表示终止递归。

with targ as (select 8+1 arg from dual)
,tree as (select rownum x from dual connect by rownum<=2)
, t (step, r, c,path, stop) as
(select 0 step, 1 r, 1 c, '', 0  from dual
union all
select
step+1,
case when (x=2 and r< arg) or c=arg then  r+1 else r end,
case when (x=1 and c< arg) or r=arg then  c+1 else c end,
path || '|' || r || ',' || c ,
case when r=arg or c= arg then 1 else 0 end
from t, tree,targ where step<arg*2-1 and stop = 0)
cycle step,r,c set iscycle to 'y' default 'n'
select count(distinct path) from t,targ where stop = 1


COUNT(DISTINCTPATH)
-------------------
              12870

Executed in 2.61 seconds

tree_new_bee

下面， 仔细的观察一些原题中的示例图， 可以看出， 不同的路径选择，其实就是选择不同的水平线段的组合。(当然垂直线段也可以)
这样， 只要确定不同的水平线段的组合，就确定了整个路径。

对于水平线从上到下进行编号：
1  1  1
2  2  2
3  3  3
4  4  4

因为不能回溯，所以后面的线段不能比前面的线段位置高。

用这样的思路来实现：

with targ as (select 8 arg from dual)
,tree as (select arg, rownum n from targ connect by rownum<=arg+1)
, t ( r, d , path) as
(select 0, 0, cast('' as varchar2(2000)) from dual
union all
select
r+1,
n,
path || '>' ||n
from t,tree where r < arg and n >= d)
select count(*) from t,targ where r=arg

  COUNT(*)
----------
     12870

Executed in 0.922 seconds


在8+1的参数下已经很快了， 用10+1来试试：

  COUNT(*)
----------
    184756

Executed in 23.266 seconds


10+1竟然还是要20多秒，离20+1的参数还早着呢！