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

newkid

49楼和我思路差不多。为什么说维护走过的LIST开销更大？长度信息也不难获取吗，你有 pathtable(i) := len; 剩下的都是递减的。等会我有空来改改看。

tree_new_bee

原帖由 newkid 于 2010-12-15 22:28 发表
NB哥盖楼真快。40楼的“23以后的质数肯定不再需要”这个结论怎么得出来的？前面的D(N)>500怎么能保证凑出三角数来？

我先说一个性价比的概念： 性价比在这里指增加一个D(N)所需要花费的N的代价。

从性价比的角度出发， 要在D(N)比较大的情况下，N比较小， 就不可能出现前面小质数的数量为0， 而后面不为0的情况。

这样，在1..23都为1的情况下， 如果再增加新的质数29， 会让N增加的过快，一下子就增加到64亿以上。 前面的那些小质数任何一个加1都比加一个新质数的性价比高。 所以23以后的数字不需要考虑。

当然这里因为没有严格的分析， 所以只能算凭感觉。 当然也有可能一直到64亿都找不到解，那种情况就需要再加进去。


“前面的D(N)>500怎么能保证凑出三角数来？”
这里没有保证， 或者说找的根本就不一定是三角数。
这里找的是最先达到500个因数的数。  "最先达到500个因数的数"，一定小于等于 "最先达到500个因数的三角数"
找到这个数只是为了寻找一个好的循环开始点。

[ 本帖最后由 tree_new_bee 于 2010-12-15 23:13 编辑 ]

tree_new_bee

原帖由 newkid 于 2010-12-15 22:37 发表
49楼和我思路差不多。为什么说维护走过的LIST开销更大？长度信息也不难获取吗，你有 pathtable(i) := len; 剩下的都是递减的。等会我有空来改改看。

恩。
问题是对于一个数，走路径的过程没有保留踪迹， 所以没办法记录。除非再引入一个小list, 记录这个踪迹。
btw: 往回走的路径不是唯一能确定的， 不可逆。 不能倒推。


"为什么说维护走过的LIST开销更大？"
我做了profiler, 开销最大的部分就是mod操作和pathtable的操作。

newkid

原帖由 tree_new_bee 于 2010-12-15 23:01 发表


我先说一个性价比的概念： 性价比在这里指增加一个D(N)所需要花费的N的代价。

从性价比的角度出发， 要在D(N)比较大的情况下，N比较小， 就不可能出现前面小质数的数量为0， 而后面不为0的情况。

这样，在1..23都为1的情况下， 如果再增加新的质数29， 会让N增加的过快，一下子就增加到2亿以上。 前面的那些小质数任何一个加1都比加一个新质数的性价比高。 所以23以后的数字不需要考虑。

当然这里因为没有严格的分析， 所以只能算凭感觉。 当然也有可能一直到2亿都找不到解，那种情况就需要再加进去。

“前面的D(N)>500怎么能保证凑出三角数来？”
这里没有保证， 或者说找的根本就不一定是三角数。
这里找的是最先达到500个因数的数。  "最先达到500个因数的数"，一定小于等于 "最先达到500个因数的三角数"
找到这个数只是为了寻找一个好的循环开始点。

如果增加29, 前面的也不一定要全部用上啊？

newkid

原帖由 tree_new_bee 于 2010-12-15 23:07 发表


恩。
问题是对于一个数，走路径的过程没有保留踪迹， 所以没办法记录。除非再引入一个小list, 记录这个踪迹。
btw: 往回走的路径不是唯一能确定的， 不可逆。 不能倒推。


"为什么说维护走过的LIST开销更大？"
我做了profiler, 开销最大的部分就是mod操作和pathtable的操作。

我的意思就是引入一个小list.
看到你用bitand代替mod了，真的有用？

tree_new_bee

原帖由 newkid 于 2010-12-15 23:07 发表

如果增加29, 前面的也不一定要全部用上啊？

前面的不用，后面的用。 会减少很多增加因数的机会。

看我在38楼列出的创新高的因数列表就知道了。 为了让因数增加的最快， 一定要先增加或者尽量利用小因子， 后增加大因子。

比如在这一段：
60        12            1,2,3,4,6,5
120        16            1,2,3,4,6,5,8,10
180        18            1,2,3,4,6,5,8,10,9
240        20            1,2,3,4,6,5,8,10,12,20
在这之间有很多7的倍数的数字， 但他们不可能创出新高的数字， 为什么？ 因为加入1个7为那些数字贡献的因数太少，那种贡献不如多增加1个2或者3这样的小因子。

原帖由 newkid 于 2010-12-15 23:11 发表


我的意思就是引入一个小list.
看到你用bitand代替mod了，真的有用？

有效果。

SQL> declare
  2    x number;
  3  begin
  4    for i in 1..10000000 loop
  5      --if bitand(i,1)=1 then
  6      if mod(i,2)=1 then
  7              x:= x+1;
  8      end if;
  9    end loop;
10  end;
11  /

PL/SQL procedure successfully completed

Executed in 6.032 seconds

SQL>
SQL> declare
  2    x number;
  3  begin
  4    for i in 1..10000000 loop
  5      if bitand(i,1)=1 then
  6      --if mod(i,2)=1 then
  7              x:= x+1;
  8      end if;
  9    end loop;
10  end;
11  /

PL/SQL procedure successfully completed

Executed in 1.828 seconds

newkid

我试了一下保存路径确实不可行，因为有很多中间数据超过1000000，原来没想到这个问题。

tree_new_bee

原帖由 newkid 于 2010-12-15 23:39 发表
我试了一下保存路径确实不可行，因为有很多中间数据超过1000000，原来没想到这个问题。

用SQL做，想抛弃路径都不容易。 放在那儿，想利用还有不容易利用到。
用PLSQL做， 想保留路径反倒很麻烦。



我分析这个问题时， 做过一个6171的路径折线图， 可看到这种长路径的数在上面的时间是很长的。

图的坐标是对数坐标。



[ 本帖最后由 tree_new_bee 于 2010-12-16 01:02 编辑 ]

newkid

我忽然想到溢出的那些其实可以不管，试一下：

declare
  type tpathtable is table of NUMBER index by BINARY_INTEGER;
  pathtable tpathtable;
  maxchain    number := 0;
  maxchainnum number := 0;
  icopy       number;
  len         number;
  
  list tpathtable;
  l PLS_INTEGER;
begin
  pathtable(1) := 1;
  for i in 2 .. 1000000 loop
    if pathtable.exists(i) then
      null;
    else
      icopy := i;
      len   := 1;
      while icopy >= 1 loop
        if icopy<2147483647 AND pathtable.exists(icopy) then
           l := pathtable(icopy) + len;
           FOR j IN 1..len-1 LOOP
               IF list(j)<2147483647 THEN
                  pathtable(list(j)):= l-j;
               END IF;
           END LOOP;
           len := l - 1;
           exit;
        else
          list(len) := icopy;  ----- 保存路径
        end if;

        if bitand(icopy, 1) = 0 then
          icopy := icopy / 2;
        else
          icopy := icopy * 3 + 1;
        end if;
        len := len + 1;
      end loop;
   
      -- pathtable(i) := len;
   
      if len > maxchain then
        maxchain    := len;
        maxchainnum := i;
      end if;
    end if;
  end loop;
  dbms_output.put_line('number: ' || maxchainnum || ' chains: ' ||
                       maxchain);
  dbms_output.put_line('index table size:'||pathtable.count);
--  for i in 1 .. 100 loop
--    dbms_output.put_line('number: ' || i || ' chains: ' || pathtable(i));
--  end loop;

end;
/

number: 837799 chains: 525
index table size:2168223

PL/SQL procedure successfully completed.

Elapsed: 00:00:03.00

你的代码也是在3秒上下。保存路径的好处被数组的开销抵消了。原来100W大小的数组现在变成了2168223.

tree_new_bee

原帖由 newkid 于 2010-12-16 05:23 发表
保存路径的好处被数组的开销抵消了。原来100W大小的数组现在变成了2168223.

确实如此， 从两个代码的profiler可以看出。

我的代码：
时间        次数       
2,846        6226258        if icopy < 1000000 and pathtable.exists(icopy) and
3,166        5226260        if bitand(icopy, 1) = 0 then

你的代码：
时间        次数       
2,009        2600973        if icopy<2147483647 AND pathtable.exists(icopy) then
1,935        2168222        pathtable(list(j)):= l-j;
1,387        2168610        if bitand(icopy, 1) = 0 then

总体来说， bitand节省了一半以上的操作， 数组操作特别是数组的添加元素操作把这些好处抵消了。

另外，俄可以看到：对于exists操作，你的代码减少了一半多的比较次数，但时间并没有省一半， 可见当数组越大时开销越大。

所以， 可以这样改进一下：
观察上面58#我发的路径图， 可以看出， 路径的大部分节点都在起始数的20倍以内。 因此我们折中一下， 只保存这有很高几率被用到的部分。 把pathtable的上限从2147483647 减少到2000万。
这样调整后：

时间        次数       
1,938        2601991  if icopy<2147483647 AND pathtable.exists(icopy) then
1,720        2103857  pathtable(list(j)):= l-j;
1,378        2169628  if bitand(icopy, 1) = 0 then

这样， 仅仅增加了10000左右个bitand, 就减少了60000次pathtable的扩展操作。

不过这种调整只能算微调了， 总体影响不是太大。