sql求解200万内质数各种算法点评

〇〇

lastwinner 发表于 2014-3-29 12:33
要这样说，那pl/sql里你采取小批量处理的策略，而不是一个一个去处理，会快更多

学newkid的办法：先保存在数组，再一次性插入表

私水流年

膜拜.... 各位ORACLE的前辈.

lanjuuff

厉害

〇〇

下面准备测试一下varray和index by table的性能差别

〇〇

〇〇 发表于 2014-5-22 15:08
下面准备测试一下varray和index by table的性能差别

稀疏index by table和删除节点后性能不相上下
SQL> exec pkg_newkid.LT(2000000)
148933
已用时间:  00: 00: 00.95
SQL> select count(case pkg_newkid.isprimLT(level)when 1 then 1 end) from dual connect by level<=1e5;

COUNT(CASEPKG_NEWKID.ISPRIMLT(LEVEL)WHEN1THEN1END)
--------------------------------------------------
                                              9592
已用时间:  00: 00: 00.33
SQL> c/5/6
  1* select count(case pkg_newkid.isprimLT(level)when 1 then 1 end) from dual connect by level<=1e6
SQL> /

COUNT(CASEPKG_NEWKID.ISPRIMLT(LEVEL)WHEN1THEN1END)
--------------------------------------------------
                                             78498
已用时间:  00: 00: 03.40
SQL> exec pkg_newkid.newkid(2000000)
已用时间:  00: 00: 00.89
SQL> select count(case pkg_newkid.isprim(level)when 1 then 1 end) from dual connect by level<=1e5;

COUNT(CASEPKG_NEWKID.ISPRIM(LEVEL)WHEN1THEN1END)
------------------------------------------------
                                            9592
已用时间:  00: 00: 00.36
SQL> select count(case pkg_newkid.isprim(level)when 1 then 1 end) from dual connect by level<=1e6;

COUNT(CASEPKG_NEWKID.ISPRIM(LEVEL)WHEN1THEN1END)
------------------------------------------------
                                           78498
已用时间:  00: 00: 03.57

〇〇

〇〇 发表于 2014-5-22 15:21
稀疏index by table和删除节点后性能不相上下
SQL> exec pkg_newkid.LT(2000000)
148933

varray与index by table的区别也几乎没有
SQL> exec pkg_newkid.LTV(2000000)
148933
已用时间:  00: 00: 01.06
SQL> select count(case pkg_newkid.isprimLTV(level)when 1 then 1 end) from dual connect by level<=1e5;

COUNT(CASEPKG_NEWKID.ISPRIMLTV(LEVEL)WHEN1THEN1END)
---------------------------------------------------
                                               9592
已用时间:  00: 00: 00.34
SQL> c/5/6
  1* select count(case pkg_newkid.isprimLTV(level)when 1 then 1 end) from dual connect by level<=1e6
SQL> /

COUNT(CASEPKG_NEWKID.ISPRIMLTV(LEVEL)WHEN1THEN1END)
---------------------------------------------------
                                              78498
已用时间:  00: 00: 03.37

〇〇

〇〇 发表于 2014-5-22 15:30
varray与index by table的区别也几乎没有
SQL> exec pkg_newkid.LTV(2000000)
148933

create or replace package pkg_newkid is
  TYPE t_row IS TABLE OF BINARY_INTEGER;
  V_RESULT T_row:=t_row();
V_RESULT2 T_row:=t_row();
type ty_i is varray(10000000) of int;
V_RESULT3 ty_i:=ty_i();
  function isprim (n number )
  return number;
  function isprimLT (n number )
  return number;
  function isprimLTV (n number )
  return number;
  
  PROCEDURE NEWKID(X IN NUMBER);
PROCEDURE LT(U IN NUMBER)  ;
PROCEDURE LTV(U IN NUMBER)  ;
end;
/
create or replace package body pkg_newkid is --用质数表

PROCEDURE NEWKID(X IN NUMBER) AS
  I NUMBER DEFAULT 1;
  J NUMBER DEFAULT 0;
  C NUMBER DEFAULT 1;
  lv_limit NUMBER := x;
  lv_upper1 NUMBER := (SQRT(lv_limit)-1)/2;
  lv_upper2 NUMBER := lv_limit/2-1;
  lv_step BINARY_INTEGER;
BEGIN
    v_result.EXTEND(lv_upper2);
    while i<lv_upper1 loop
          lv_step := i*2+1;
          j:=2*i*(i+1);
          while j<=lv_upper2 loop
                v_result.DELETE(j);
                j:=j+lv_step;
          end loop;
          i := v_result.NEXT(i);
    end loop;
END;

PROCEDURE LT(U IN NUMBER)  
AS  
   I NUMBER DEFAULT 3;  
   J NUMBER DEFAULT 0;  
   C NUMBER DEFAULT 1;  
BEGIN  
  v_result2.EXTEND(U);  
  while(i<sqrt(U)) loop  
if v_result2(i)=1 then --利用已经计算出的质数表
     goto n;  
   end if;  
   j:=i*(i-2);  
   while (j<U) loop  
    v_result2(j):=1;  
    j:=J+i+i;  
   end loop;  
   <<n>>  
   I:=i+2;  
  end loop;  
  for j in 1 .. U/2 loop  
if v_result2(j+j-1)is null then --只判断奇数
  c:=c+1;  
  end if;  
  end loop;  
  DBMS_OUTPUT.PUT_LINE(c);  
END;

PROCEDURE LTV(U IN NUMBER)  
AS  
   I NUMBER DEFAULT 3;  
   J NUMBER DEFAULT 0;  
   C NUMBER DEFAULT 1;  
BEGIN  
  v_result3.EXTEND(U);  
  while(i<sqrt(U)) loop  
if v_result3(i)=1 then --利用已经计算出的质数表
     goto n;  
   end if;  
   j:=i*(i-2);  
   while (j<U) loop  
    v_result3(j):=1;  
    j:=J+i+i;  
   end loop;  
   <<n>>  
   I:=i+2;  
  end loop;  
  for j in 1 .. U/2 loop  
if v_result3(j+j-1)is null then --只判断奇数
  c:=c+1;  
  end if;  
  end loop;  
  DBMS_OUTPUT.PUT_LINE(c);  
END;

function isprim (n number )
return number
is
begin
if n=2 then
return 1;
elsif mod(n,2)=0  then
return 0;
elsif v_result.exists((n-1)/2) then
return 1;
end if;
return 0;
end;

function isprimLT (n number )
return number
is
begin
if n=2 then
return 1;
elsif mod(n,2)=0  then
return 0;
elsif v_result2(n)is null then
return 1;
end if;
return 0;
end;

function isprimLTV (n number )
return number
is
begin
if n=2 then
return 1;
elsif mod(n,2)=0  then
return 0;
elsif v_result3(n)is null then
return 1;
end if;
return 0;
end;
end;
/

ozzylsf

不觉明历！

bingfengguan

分析问题循序渐进~慢慢学了

stilllovekk

看完这个帖子，我只想说，，，哪位版主收徒？