Euler Project 挨个做- 之二 (Q51-Q78)

〇〇

我运行了scala的代码，没什么优化 Q58很快，不到2秒，看来语言有时候真的很重要

tree_new_bee

原帖由 〇〇 于 2011-1-2 11:21 发表
我运行了scala的代码，没什么优化 Q58很快，不到2秒，看来语言有时候真的很重要

这个我觉得倒不是由于scala语言的优势造成的。
而是因为oracle的mod函数特别低效造成的。

把我#55的代码中isprim换成java版本的isprimj (两个版本算法基本相同)， 只要4.2秒。
如果全部都在java中来实现， 估计也应该与scala中的时间差不多。

tree_new_bee

原帖由 〇〇 于 2011-1-1 22:19 发表
tnb请把工具包放在1楼啊，便于学习..

放上去了。

tree_new_bee

Q59与其说是考验代码技巧， 不如说是考验对什么叫"普通英语文本"的常识。

先来一段笨拙的plsql代码， 这里对"普通英语"的认定， 是认为字母+空格应该占据全部字符的90%以上。

因为密文只有3k, 可以放到一个字符串中， 所以不再单独考虑读文件的环节。

declare
  i integer;
  cryptstr constant varchar2(4000)   :='79,59,12,2,79,35,8,28,20,以下略。。。' ;
  numlist t_numlist := new t_numlist();
  tmpstr varchar2(4000);
  c number;
  success boolean;
  newc number;
  newstr varchar2(4000);
  alpha number;
  sm number;
function xor(x IN NUMBER,y IN NUMBER) return number is
begin
         return (x + y) - BITAND(x, y)- BITAND(x, y);
end;

begin
  tmpstr:= cryptstr||',';
  while tmpstr is not null loop
      numlist.extend;
      numlist(numlist.count) := substr(tmpstr, 1, instr(tmpstr,',')-1);
      tmpstr := substr(tmpstr, instr(tmpstr,',')+1);            
  end loop;

  for c1 in 97..122 loop
  for c2 in 97..122 loop
  for c3 in 97..122 loop
      newstr:='';
      success := true;
      alpha:=0;
      sm:=0;
      for i in 1.. numlist.count loop
        c := case mod(i,3) when 1 then c1 when 2 then c2 when 0 then c3 end;
        PRAGMA INLINE(XOR, 'YES');
        newc := xor(numlist(i), c);
        if newc <32 or newc> 126 then
         success:=false;
         exit;
        end if;
        if (newc = 32) or (newc between 65 and 90) or (newc between 97 and 122 )then
          alpha := alpha+1;
        end if;
        sm := sm+newc;
        newstr:=newstr||chr(newc);        
      end loop;   
      if success and alpha/numlist.count > 0.9 then
           dbms_output.put_line('key:'||chr(c1)||chr(c2)||chr(c3));
           dbms_output.put_line('newstr:'||newstr);
           dbms_output.put_line('sum:'||sm);
      end if;
  end loop;
  end loop;
  end loop;
end;

key:god
newstr: (The Gospel of John, chapter 1) 1 In the beginning ................................
sum:107359

PL/SQL procedure successfully completed

Executed in 5.468 seconds

SQL>

[ 本帖最后由 tree_new_bee 于 2011-1-2 18:35 编辑 ]

〇〇

Q58 PLSQL版本
没什么优化的比tnb的sql+函数版本还慢

1. 
   
2. create or replace procedure Q58
   
3. as
   
4. side number:=3;
   
5. numbers number:=1;
   
6. primes number:=0;
   
7. percentage number:=100;
   
8. 
   
9. function is_prime(n number)
   
10. return number
    
11. as
    
12. i number:=3;
    
13. begin
    
14.    while i<=sqrt(n) LOOP
    
15.    if mod(n,i)=0 then
    
16.            return 0;
    
17.    end if;
    
18.    i:=i+2;
    
19.    end loop;
    
20.    return 1;
    
21. end;
    
22. 
    
23. begin
    
24. while percentage>=10  loop
    
25.       numbers:=numbers+4;
    
26.       if is_prime(side*side)=1 then primes:=primes+1;end if;
    
27.       if is_prime(side*side-side+1)=1 then primes:=primes+1;end if;
    
28.       if is_prime(side*side-2*side+2)=1 then primes:=primes+1;end if;
    
29.       if is_prime(side*side-3*side+3)=1 then primes:=primes+1;end if;
    
30.       percentage:=(100*primes)/numbers;
    
31.       /* printf("%d %d\n",side,percentage);*/
    
32.       side:=side+2;
    
33. end loop;
    
34. dbms_output.put_line(side-2);
    
35. end;
    
36. /   
    

复制代码

1. 
   
2. create or replace procedure Q58b
   
3. as
   
4. side number:=3;
   
5. numbers number:=1;
   
6. primes number:=0;
   
7. percentage number:=100;
   
8.   TYPE t_row IS TABLE OF BINARY_INTEGER;
   
9.   V_RESULT T_row:=t_row();
   
10. 
    
11. PROCEDURE NEWKIDI(X IN NUMBER) AS --newkid改写的筛法求质数，利用v_result.DELETE删除合数
    
12.   I NUMBER DEFAULT 1;
    
13.   J NUMBER DEFAULT 0;
    
14.   C NUMBER DEFAULT 1;
    
15.   lv_limit NUMBER := x;
    
16.   lv_upper1 NUMBER := (SQRT(lv_limit)-1)/2;
    
17.   lv_upper2 NUMBER := lv_limit/2-1;
    
18.   lv_step BINARY_INTEGER;
    
19. BEGIN
    
20.     v_result.EXTEND(lv_upper2);
    
21.     while i<lv_upper1 loop
    
22.           lv_step := i*2+1;
    
23.           j:=2*i*(i+1);
    
24.           while j<=lv_upper2 loop
    
25.                 v_result.DELETE(j);
    
26.                 j:=j+lv_step;
    
27.           end loop;
    
28.           i := v_result.NEXT(i);
    
29.     end loop;
    
30. --DBMS_OUTPUT.PUT_LINE(v_result.COUNT+1); -- 把2算进去
    
31. END;
    
32. 
    
33. function is_prime(n number)
    
34. return number
    
35. as
    
36. i number:=1;
    
37. begin
    
38.    if n in(2,3,5,7) then return 1; end if;
    
39.    while i*2+1<=sqrt(n) LOOP
    
40.    if mod(n,i*2+1)=0 then
    
41.            return 0;
    
42.    end if;
    
43.    i:=v_result.NEXT(i);
    
44.    end loop;
    
45.    return 1;
    
46. end;
    
47. 
    
48. begin
    
49. NEWKIDI(100000);       
    
50. while percentage>=10  loop
    
51.       numbers:=numbers+4;
    
52.       if is_prime(side*side)=1 then primes:=primes+1;end if;
    
53.       if is_prime(side*side-side+1)=1 then primes:=primes+1;end if;
    
54.       if is_prime(side*side-2*side+2)=1 then primes:=primes+1;end if;
    
55.       if is_prime(side*side-3*side+3)=1 then primes:=primes+1;end if;
    
56.       percentage:=(100*primes)/numbers;
    
57.       side:=side+2;
    
58. end loop;
    
59. dbms_output.put_line(side-2);
    
60. end;
    
61. /   
    

复制代码

SQL> @d:\app\q58

过程已创建。

已用时间:  00: 00: 00.02
SQL> exec q58
26241

PL/SQL 过程已成功完成。

已用时间:  00: 00: 34.77
SQL> @d:\app\q58b

过程已创建。

已用时间:  00: 00: 00.06
SQL> exec q58b
26241

PL/SQL 过程已成功完成。

已用时间:  00: 00: 13.42

〇〇

比较了下tnb和newkid的筛法产生质数函数，貌似有差距，但不知道是否因为复制到外部造成的
SQL> select count(*) from table(pkg_prim2.seive_numlist(1000000));

  COUNT(*)
----------
     78498

已用时间:  00: 00: 01.23
SQL> /

  COUNT(*)
----------
     78498

已用时间:  00: 00: 01.22

1. 
   
2. CREATE OR REPLACE PROCEDURE NEWKIDI(X IN NUMBER) AS --newkid改写的筛法求质数，利用v_result.DELETE删除合数
   
3.   TYPE t_row IS TABLE OF BINARY_INTEGER;
   
4.   V_RESULT T_row:=t_row();
   
5.   I NUMBER DEFAULT 1;
   
6.   J NUMBER DEFAULT 0;
   
7.   C NUMBER DEFAULT 1;
   
8.   lv_limit NUMBER := x;
   
9.   lv_upper1 NUMBER := (SQRT(lv_limit)-1)/2;
   
10.   lv_upper2 NUMBER := lv_limit/2-1;
    
11.   lv_step BINARY_INTEGER;
    
12. BEGIN
    
13.     v_result.EXTEND(lv_upper2);
    
14.     while i<lv_upper1 loop
    
15.           lv_step := i*2+1;
    
16.           j:=2*i*(i+1);
    
17.           while j<=lv_upper2 loop
    
18.                 v_result.DELETE(j);
    
19.                 j:=j+lv_step;
    
20.           end loop;
    
21.           i := v_result.NEXT(i);
    
22.     end loop;
    
23. DBMS_OUTPUT.PUT_LINE(v_result.COUNT+1); -- 把2算进去
    
24. j:=1;
    
25. /*
    
26. for i in 1..v_result.COUNT loop
    
27. DBMS_OUTPUT.PUT_LINE(j*2+1);
    
28. j:=v_result.next(j);       
    
29. end loop;
    
30. */
    
31. END;
    
32. /
    

复制代码

过程已创建。

已用时间:  00: 00: 00.02
SQL> exec newkidi(1000000)
78498

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.34
SQL>

tree_new_bee

原帖由 〇〇 于 2011-1-2 18:08 发表
比较了下tnb和newkid的筛法产生质数函数，貌似有差距，但不知道是否因为复制到外部造成的

不是。
是因为我额外的多执行了几次遍历数组的循环。
另外， seive_numlist和seive_indextable两个为了共享一段代码， 也增添了一些额外的开销。

〇〇

加上了输出确实还是newkid的快

1. 
   
2. create or replace  FUNCTION seive_numlist(maxnum NUMBER) RETURN t_numlist IS
   
3.     i      INTEGER;
   
4.     RESULT t_numlist := NEW t_numlist();
   
5.   TYPE t_row IS TABLE OF BINARY_INTEGER;
   
6.   V_RESULT T_row:=t_row();
   
7.     PROCEDURE NEWKID(X IN NUMBER) AS --newkid改写的筛法求质数，利用v_result.DELETE删除合数
   
8.   I NUMBER DEFAULT 1;
   
9.   J NUMBER DEFAULT 0;
   
10.   C NUMBER DEFAULT 1;
    
11.   lv_limit NUMBER := x;
    
12.   lv_upper1 NUMBER := (SQRT(lv_limit)-1)/2;
    
13.   lv_upper2 NUMBER := lv_limit/2-1;
    
14.   lv_step BINARY_INTEGER;
    
15. BEGIN
    
16.     v_result.EXTEND(lv_upper2);
    
17.     while i<lv_upper1 loop
    
18.           lv_step := i*2+1;
    
19.           j:=2*i*(i+1);
    
20.           while j<=lv_upper2 loop
    
21.                 v_result.DELETE(j);
    
22.                 j:=j+lv_step;
    
23.           end loop;
    
24.           i := v_result.NEXT(i);
    
25.     end loop;
    
26. --DBMS_OUTPUT.PUT_LINE(v_result.COUNT+1); -- 把2算进去
    
27. end;
    
28.   BEGIN
    
29.     newkid(maxnum);
    
30.       result.extend(v_result.COUNT+1);
    
31.       result(1):=2;
    
32.       i:=1;
    
33.      for j in 2..result.COUNT loop
    
34.        RESULT(j) := i*2+1;
    
35.       i := v_result.next(i);
    
36.     END LOOP;
    
37.     RETURN RESULT;
    
38.   END;
    
39. /
    

复制代码

tree_new_bee

继续解59题。
#64对"普通英语文本"的认定， 是认为字母+空格应该占据全部字符的90%以上。 这种做法比较低效。
更好的认定方法是： 在正常的英语文本中， 数量最多的是空格， 并且这种多是绝对性的多， 在任何较长的片段都是最多的， 甚至几十按照隔几个挑一个字符的方法， 挑出来的字符串中也一定是空格最多。
因此， 我们可以从1/4/7... 的字符中找出最多的，假定它是空格， 然后破解对应的key,  再 2/5/8... 和3/6/9...中同样的方法找出第二个第三个key

用这样的方法， 甚至不需要题目给出的条件: 3个"小写字母"。

这次纯粹用SQL来解决， 虽然写的依然是冗长了一些：

with t as (select '79,59,12,2,79,35,8,28,20,2,以下略。。。。。。' str
from dual)
,t1 as (select cast(','||str||',' as varchar2(4000)) str from t)
,td as (select rownum d from t1 connect by rownum<=length(translate(str, ','||str, ',')) )
,tall as (select /*+ MATERIALIZE */ d, instr(str, ',', 1,d), instr(str, ',', 1,d+1)-1,
      substr(str, instr(str, ',',1, d)+1,instr(str, ',', 1,d+1)-instr(str, ',', 1,d)-1) crypt
      from t1,td where d<length(translate(str, ','||str, ',')))
,tchar as (select level c from dual where level>=97 connect by level<=122)
,tspace as (select mod(d,3) seq ,crypt,count(*) cnt from tall group by  mod(d,3),crypt)
,tspace2 as (select seq, substr(max(to_char(cnt, 'FM0000')||crypt),5) sp from tspace  group by seq)
,tkey as (select seq, (sp+32) - BITAND(sp,32)*2 key from tspace2 )
,tdecrypt as (select d, (crypt + key) - BITAND(crypt, key) * 2 decrypt
from tall, tkey where mod(d,3)=seq)
select sum(decrypt) from tdecrypt


SUM(DECRYPT)
------------
      107359

Executed in 2.187 seconds


其中tspace2的写法，是刚刚从http://www.itpub.net/thread-1383362-1-1.html 贴子里，newkid那里偷来的。

tree_new_bee

原帖由 〇〇 于 2011-1-2 18:32 发表
加上了输出确实还是newkid的快

仔细看了看， 原来newkid在循环的时候，使用了已有的筛查结果， 所以效率会高很多。
另外， 按照奇数的序号来处理， 节省了一半数组维护操作的开销。 newkid装修大师写出的东西真的是精干到了极致。

把测试数据从100万加到500万， newkid的函数运行时间增加了5倍， 已经基本上近似线性关系了。


"加上了输出确实还是newkid的快",  在输出时，结果集已经很小了，那个时候对数组的扩展已经相比整体性能已经可以忽略了。


我的工具库里的装备又升级了。

[ 本帖最后由 tree_new_bee 于 2011-1-3 00:44 编辑 ]