Oracle-要素数
需要:200 w以内の素数の素数を求めるのは1と自身の整除することしかできない数で、1は素数ではありません
一.SQL版
まず2 wでテストします
実行レコード:
簡単な論理的な最適化により、CPUは32秒から0.57秒に多くの不要なデータ計算時間を計算することが少なくなり、性能が大幅に向上した.
2 wを200 wに調整
実行レコード
実行時間は4分13秒から8.13秒に最適化され、パフォーマンスが大幅に向上しました.
一.SQL版
まず2 wでテストします
-- 1 ， ， not exists
WITH t AS
(SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1),
t1 AS
(SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1)
SELECT count(*)
FROM t
WHERE NOT EXISTS (SELECT t1.rn
FROM t1
WHERE t1.rn != t.rn
AND MOD(t.rn, t1.rn) = 0);
--
WITH t AS
(SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1),
t1 AS
(SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1)
SELECT count(*)
FROM t
WHERE NOT EXISTS (SELECT t1.rn
FROM t1
WHERE t1.rn < t.rn
AND MOD(t.rn, t1.rn) = 0);
-- ， t1
-- where
WITH t AS
(SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1),
t1 AS
(SELECT rownum+1 rn FROM dual CONNECT BY rownum <= sqrt（20000） -1)
SELECT count(*)
FROM t
WHERE NOT EXISTS (SELECT t1.rn
FROM t1
WHERE t1.rn <= sqrt(t.rn)
AND MOD(t.rn, t1.rn) = 0);
実行レコード:
scoot@orcl>-- 1 ， ， not exists
scoot@orcl>WITH t AS
2 (SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1),
3 t1 AS
4 (SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1)
5 SELECT count(*)
6 FROM t
7 WHERE NOT EXISTS (SELECT t1.rn
8 FROM t1
9 WHERE t1.rn != t.rn
10 AND MOD(t.rn, t1.rn) = 0);
COUNT(*)
----------
2262
: 00: 00: 32.19
scoot@orcl>
scoot@orcl>
scoot@orcl>--
scoot@orcl>WITH t AS
2 (SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1),
3 t1 AS
4 (SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1)
5 SELECT count(*)
6 FROM t
7 WHERE NOT EXISTS (SELECT t1.rn
8 FROM t1
9 WHERE t1.rn < t.rn
10 AND MOD(t.rn, t1.rn) = 0);
COUNT(*)
----------
2262
: 00: 00: 24.42
scoot@orcl>
scoot@orcl>
scoot@orcl>-- ， t1
scoot@orcl>-- where
scoot@orcl>WITH t AS
2 (SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 20000 -1),
3 t1 AS
4 (SELECT rownum+1 rn FROM dual CONNECT BY rownum <= sqrt（20000） -1)
5 SELECT count(*)
6 FROM t
7 WHERE NOT EXISTS (SELECT t1.rn
8 FROM t1
9 WHERE t1.rn <= sqrt(t.rn)
10 AND MOD(t.rn, t1.rn) = 0);
COUNT(*)
----------
2262
: 00: 00: 00.57
scoot@orcl>
簡単な論理的な最適化により、CPUは32秒から0.57秒に多くの不要なデータ計算時間を計算することが少なくなり、性能が大幅に向上した.
2 wを200 wに調整
-- 2w 200w
WITH t AS
(SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 2000000 -1),
t1 AS
(SELECT rownum+1 rn FROM dual CONNECT BY rownum <= sqrt（2000000） -1)
SELECT count(*)
FROM t
WHERE NOT EXISTS (SELECT t1.rn
FROM t1
WHERE t1.rn <= sqrt(t.rn)
AND MOD(t.rn, t1.rn) = 0);
-- ，
-- ， minus， 2 20w ，
-- 2
WITH t AS (
SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (2000000)/2-1
)
,t_prime AS (
SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (2000000)/2-1
UNION ALL
SELECT 2 FROM DUAL
)
SELECT COUNT(*)
FROM (SELECT rn from t_prime
MINUS
SELECT t1.rn * t2.rn
FROM t t1, t t2
WHERE t1.rn <= t2.rn
AND t1.rn <= (SELECT SQRT(2000000) FROM DUAL)
AND t1.rn * t2.rn <2000000
);
-- ， 3 、5、7
WITH t0 AS
(SELECT 2*rownum+1 rn FROM dual CONNECT BY rownum <= 1000000 -1),
t AS
(select rn from t0 where mod(rn,3) != 0 and mod(rn,5) != 0 and mod(rn,7) != 0 )
SELECT COUNT(*)+1+3 --2，3，5，7
FROM (SELECT rn from t
MINUS
SELECT t1.rn * t2.rn
FROM t t1, t t2
WHERE t1.rn <= t2.rn
AND t1.rn BETWEEN 9 AND (SELECT SQRT(2000000) FROM DUAL)
AND t1.rn * t2.rn <2000000
);
--
WITH t0 AS (
SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (2000000)/2-1-1
),
t as(SELECT rn from t0
where mod(rn,3)<>0
and mod(rn,5)<>0
and mod(rn,7)<>0
and mod(rn,11)<>0
and mod(rn,13)<>0
and mod(rn,17)<>0
and mod(rn,19)<>0
and mod(rn,23)<>0
and mod(rn,29)<>0
)
SELECT COUNT(*)+10 --2,3,5,7,11,13,17,19,23,29
FROM (SELECT rn from t
MINUS
SELECT t1.rn * t2.rn
FROM t t1, t t2
WHERE t1.rn <= t2.rn
AND t1.rn BETWEEN 31 AND (SELECT SQRT(2000000) FROM DUAL)
AND t1.rn * t2.rn <2000000
);
実行レコード
scoot@orcl>-- 2w 200w
scoot@orcl>WITH t AS
2 (SELECT rownum+1 rn FROM dual CONNECT BY rownum <= 2000000 -1),
3 t1 AS
4 (SELECT rownum+1 rn FROM dual CONNECT BY rownum <= sqrt（2000000） -1)
5 SELECT count(*)
6 FROM t
7 WHERE NOT EXISTS (SELECT t1.rn
8 FROM t1
9 WHERE t1.rn <= sqrt(t.rn)
10 AND MOD(t.rn, t1.rn) = 0);
COUNT(*)
----------
148933
: 00: 04: 13.83
scoot@orcl>--
scoot@orcl>-- ， minus， 2 20w ，
scoot@orcl>-- 2
scoot@orcl>WITH t AS (
2 SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (2000000)/2-1
3 )
4 ,t_prime AS (
5 SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (2000000)/2-1
6 UNION ALL
7 SELECT 2 FROM DUAL
8 )
9 SELECT COUNT(*)
10 FROM (SELECT rn from t_prime
11 MINUS
12 SELECT t1.rn * t2.rn
13 FROM t t1, t t2
14 WHERE t1.rn <= t2.rn
15 AND t1.rn <= (SELECT SQRT(2000000) FROM DUAL)
16 AND t1.rn * t2.rn <2000000
17 );
COUNT(*)
----------
148933
: 00: 02: 04.74
scoot@orcl>
scoot@orcl>
scoot@orcl>
scoot@orcl>
scoot@orcl>-- ， 3 、5、7
scoot@orcl>WITH t0 AS
2 (SELECT 2*rownum+1 rn FROM dual CONNECT BY rownum <= 1000000 -1),
3 t AS
4 (select rn from t0 where mod(rn,3) != 0 and mod(rn,5) != 0 and mod(rn,7) != 0 )
5 SELECT COUNT(*)+1+3 --2，3，5，7
6 FROM (SELECT rn from t
7 MINUS
8 SELECT t1.rn * t2.rn
9 FROM t t1, t t2
10 WHERE t1.rn <= t2.rn
11 AND t1.rn BETWEEN 9 AND (SELECT SQRT(2000000) FROM DUAL)
12 AND t1.rn * t2.rn <2000000
13 );
COUNT(*)+1+3--2，3，5，7
------------------------
148933
: 00: 00: 14.23
scott@orcl>WITH t0 AS (
2 SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (2000000)/2-1-1
3 ),
4 t as(SELECT rn from t0
5 where mod(rn,3)<>0
6 and mod(rn,5)<>0
7 and mod(rn,7)<>0
8 and mod(rn,11)<>0
9 and mod(rn,13)<>0
10 and mod(rn,17)<>0
11 and mod(rn,19)<>0
12 and mod(rn,23)<>0
13 and mod(rn,29)<>0
14 )
15 SELECT COUNT(*)+10 --2,3,5,7,11,13,17,19,23,29
16 FROM (SELECT rn from t
17 MINUS
18 SELECT t1.rn * t2.rn
19 FROM t t1, t t2
20 WHERE t1.rn <= t2.rn
21 AND t1.rn BETWEEN 31 AND (SELECT SQRT(2000000) FROM DUAL)
22 AND t1.rn * t2.rn <2000000
23 )
24 /
COUNT(*)+10--2,3,5,7,11,13,17,19,23,29
--------------------------------------
148933
: 00: 00: 08.13
実行時間は4分13秒から8.13秒に最適化され、パフォーマンスが大幅に向上しました.