 |
VFP 愛用者社區
本討論區為 Visual Foxpro 愛用者經驗交流的地方, 請多多利用"搜尋"的功能, 先查看看有無前例可循, 如果還有不懂的再發問. 部份主題有附加檔案, 須先註冊成為社區居民才可以下載.
|
| 上一篇主題 :: 下一篇主題 |
| 發表人 |
內容 |
garfield
Site Admin
註冊時間: 2003-01-30
文章: 2158
第 1 樓
|
|
| 回頂端 |
|
 |
garfield
Site Admin
註冊時間: 2003-01-30
文章: 2158
第 2 樓
|
 發表於: 星期三 五月 06, 2015 9:09 pm 文章主題: |
 |
|
根據相關資料再來做做另一個用質數來運算的方式, 數字越大速度快越多.
| 代碼: |
mmax = 10000
mcount=0
CLEAR
mstart = SECONDS( )
FOR i=2 TO mmax
m=INT(i/2)
FOR j=2 TO m
IF i/j = INT(i/j)
EXIT
endif
NEXT
IF j>m
mcount=mcount+1
?? TRANSFORM(i),','
endif
NEXT
? '從 2 到 '+tran(mmax)+' 中總共有'+tran(mcount)+' 個質數', SECONDS( )-mstart
*****************
mcount=0
*CLEAR
?
mstart = SECONDS( )
mpc=1
DIMENSION mprime[mpc]
? '2 ,'
mprime[mpc]=2
FOR i=3 TO mmax
FOR j=1 TO mpc
IF i/mprime[j] = INT(i/mprime[j] )
exit
ENDIF
NEXT
IF j>mpc
mpc=mpc+1
DIMENSION mprime[mpc]
mprime[mpc]=i
mcount=mcount+1
?? TRANSFORM(i),','
ENDIF
NEXT
? '第二種算法:從 2 到 '+tran(mmax)+' 中總共有'+tran(mcount+1)+' 個質數', SECONDS( )-mstart
|
_________________
利用>>搜尋<<的功能會比問的還要快得到答案. |
|
| 回頂端 |
|
|
perry
註冊時間: 2014-07-20
文章: 203
第 3 樓
|
| 發表於: 星期三 五月 06, 2015 10:38 pm 文章主題: |
|
|
用 crea curs ... inse into curs 可不必重複定義陣列,應可再快些!!!
| 代碼: |
mmax=10000
mcount=0
*CLEAR
?
mstart = SECONDS( )
mpc=1
sele 0
priv p_l,p_f
p_f='z'+righ(sys(2015),7)
p_l=len(allt(str(mmax)))
crea curs (P_F) (tryno n(p_l))
? '2 ,'
inse into (P_F) valu (2)
FOR i=3 TO mmax
sele (p_f)
go top
scan
IF i%tryno = 0
exit
ENDIF
if recno()=recc()
inse into (p_f) valu (i)
mcount=mcount+1
?? TRANSFORM(i),','
endi
ends
NEXT
wait wind '第3種算法:從 2 到 '+tran(mmax)+' 中總共有'+tran(mcount+1)+' 個質數 , '+str(SECONDS( )-mstart,10,3)
use in (p_f)
|
|
|
| 回頂端 |
|
|
ckp6250
註冊時間: 2004-07-30
文章: 1645
第 4 樓
|
| 發表於: 星期四 五月 07, 2015 9:41 am 文章主題: |
|
|
目前看來 , 是 perry 的方法最快了
不知還有沒有更快的? |
|
| 回頂端 |
|
|
syntech
註冊時間: 2003-05-16
文章: 4215
來自: Taipei,Taiwan
第 5 樓
|
| 發表於: 星期四 五月 07, 2015 9:58 am 文章主題: |
|
|
能不能用網頁問 GOOGLE "2~N 中的質數".
然後從網頁結果中取出答案.
這應該比自己算要快. XD
_________________
如果公司有下列困擾:
1. 找不到便宜,快速,簡易的 生產排程軟體
2. 不知道如何快速排定 採購計劃
3. 成本抓不準,自己算比軟體算有用
4. 想學習系統規劃,想找系統架構的顧問
請聯絡我們,也許我們幫得上忙 |
|
| 回頂端 |
|
|
garfield
Site Admin
註冊時間: 2003-01-30
文章: 2158
第 6 樓
|
| 發表於: 星期四 五月 07, 2015 10:00 am 文章主題: |
|
|
陣列有限制只能65000 , 最終還是要用perry的方法,
不過在65000個質數的範圍內用陣列是比cursor檔要快一些, 因為array是用記憶體在跑, cursor是用暫存檔.
第二種算法會慢主要是差在多做了一個運算,
IF i/mprime[j] = INT(i/mprime[j] )
改成
IF i%mprime[j] = 0
集思廣益才能進步.
_________________
利用>>搜尋<<的功能會比問的還要快得到答案. |
|
| 回頂端 |
|
|
ckp6250
註冊時間: 2004-07-30
文章: 1645
第 7 樓
|
| 發表於: 星期四 五月 07, 2015 10:35 am 文章主題: |
|
|
借花獻佛!
【微調】一下perry的程式
mmax越大,比如到100000時,速度快了約3秒
數組越多,差異越大
| 代碼: |
mmax=10000
mcount=0
*CLEAR
?
mstart = Seconds( )
mpc=1
Sele 0
Priv p_l,p_f
p_f='z'+Righ(Sys(2015),7)
p_l=Len(Allt(Str(mmax)))
Crea Curs (p_f) (tryno N(p_l))
? '2 ,'
Inse Into (p_f) Valu (2)
For i=3 To mmax Step 2
Sele (p_f)
Go Top
Scan WHILE i%tryno <> 0 For Recno()=Reccount()
Inse Into (p_f) Valu (i)
mcount=mcount+1
?? Transform(i),','
Ends
Next
? '第3-1種算法:從 2 到 '+Tran(mmax)+' 中總共有'+Tran(mcount+1)+' 個質數 , ',Str(Seconds( )-mstart,10,3)
Use In (p_f)
|
|
|
| 回頂端 |
|
|
garfield
Site Admin
註冊時間: 2003-01-30
文章: 2158
第 8 樓
|
| 發表於: 星期四 五月 07, 2015 11:14 am 文章主題: |
|
|
再查一下google資料後運算再進化
| 代碼: |
mmax = 1000000
mdisplay=.f.
*CLEAR
?
mstart = SECONDS( )
mpc=2
DIMENSION mprime[mpc]
IF mdisplay
? '2 ,3 ,'
endif
mprime[1]=2
mprime[2]=3
FOR i=5 TO mmax step 2 &&--step 2 參考 ckp6250 所說的, 又快了10%
msqrt = sqrt(i) &&--最多算到平方根就好
j=2 &&--已經去掉2的倍數, 所以從3算起
mfound =.t.
DO WHILE mprime[j]<= msqrt
IF i%mprime[j] = 0
mfound = .f.
exit
ENDIF
j=j+1
enddo
IF mfound
mpc=mpc+1
DIMENSION mprime[mpc]
mprime[mpc]=i
IF mdisplay
?? TRANSFORM(i),','
endif
ENDIF
NEXT
? '第四種算法:從 2 到 '+tran(mmax)+' 中總共有'+tran(mpc)+' 個質數', SECONDS( )-mstart
|
_________________
利用>>搜尋<<的功能會比問的還要快得到答案. |
|
| 回頂端 |
|
|
garfield
Site Admin
註冊時間: 2003-01-30
文章: 2158
第 9 樓
|
| 發表於: 星期四 五月 07, 2015 12:04 pm 文章主題: |
|
|
算到1000萬已經有 664579個質數, 怎麼用陣列不會出問題,
難到單一陣列只有限制 2GB 而非 65000
https://msdn.microsoft.com/en-us/library/3kfd3hw9(v=vs.80).aspx
Maximum # of elements per array.
Normal: 2 gigabytes
Member array: 2 gigabytes
Array of member objects: 65,000
[/quote]
_________________
利用>>搜尋<<的功能會比問的還要快得到答案. |
|
| 回頂端 |
|
|
perry
註冊時間: 2014-07-20
文章: 203
第 10 樓
|
| 發表於: 星期五 五月 08, 2015 12:26 am 文章主題: |
|
|
小測 陣列及crea curs 2種方法差不多快!!
vfp 6.0 陣列沒法測到 100萬= ='''
測800000 好像crea curs 比較快@@
| 代碼: |
mmax = 800000
*CLEAR
?
mstart = SECONDS( )
mpc=1
sele 0
priv p_l,p_f,p_tf
p_f='z'+righ(sys(2015),7)
p_l=len(allt(str(mmax)))
p_tf=.t.
crea curs (P_F) (tryno n(p_l))
inse into (P_F) valu (2)
mcount=0
FOR i=3 TO mmax step 2
msqrt = int(sqrt(i))
if i#msqrt*msqrt &&能�}平方整數必不是質數!!
sele (p_f)
go top
p_tf=.t.
scan whil tryno<= msqrt
IF i%tryno = 0
p_tf=.f.
exit
ENDIF
ends
if p_tf
Inse Into (p_f) Valu (i)
mcount=mcount+1
endi
endi
NEXT
wait wind '第3種算法:從 2 到 '+tran(mmax)+' 中總共有'+tran(mcount+1)+' 個質數 , '+str(SECONDS( )-mstart,10,3)
use in (p_f)
|
|
|
| 回頂端 |
|
|
ckp6250
註冊時間: 2004-07-30
文章: 1645
第 11 樓
|
| 發表於: 星期五 五月 08, 2015 9:27 am 文章主題: |
|
|
實測支持perry
在1000000及10000000的二個測試範圍下
perry改良後的方法比garfield的方法平均快20%-25%
而且,數值越大,差異越大 |
|
| 回頂端 |
|
|
ckp6250
註冊時間: 2004-07-30
文章: 1645
第 12 樓
|
| 發表於: 星期五 五月 08, 2015 9:39 am 文章主題: |
|
|
perry的程式再微調一下
和garfield的方法平均快35%-38%
同樣 , 數值越大,差異越大
| 代碼: |
mmax = 1000000
*CLEAR
?
mstart = Seconds( )
mpc=1
Sele 0
Priv p_l,p_f,p_tf
p_f='z'+Righ(Sys(2015),7)
p_l=Len(Allt(Str(mmax)))
p_tf=.T.
Crea Curs (p_f) (tryno N(p_l))
Inse Into (p_f) Valu (2)
mcount=0
For i=3 To mmax Step 2
msqrt = Int(Sqrt(i))
If i#msqrt*msqrt &&能?}平方整數必不是質數!!
Sele (p_f)
Go Top
p_tf=.T.
Scan Whil tryno<= msqrt For i%tryno = 0 &&微調這一行
p_tf=.F.
Exit
Ends
If p_tf
Inse Into (p_f) Valu (i)
mcount=mcount+1
Endi
Endi
Next
Wait Wind '第3種算法:從 2 到 '+Tran(mmax)+' 中總共有'+Tran(mcount+1)+' 個質數 , '+Str(Seconds( )-mstart,10,3)
Use In (p_f)
|
|
|
| 回頂端 |
|
|
garfield
Site Admin
註冊時間: 2003-01-30
文章: 2158
第 13 樓
|
| 發表於: 星期五 五月 08, 2015 1:57 pm 文章主題: |
|
|
陣列運算再進化, 快了160%
| 代碼: |
mmax = 1000000
mstart = SECONDS( )
mpc=2
DIMENSION mprime[2]
mprime[1]=2
mprime[2]=3
mendpoint = 2
FOR i=5 TO mmax STEP 2
msqrt = sqrt(i) &&--最多算到平方根
IF msqrt > mprime[mendpoint]
mendpoint = mendpoint+1 &&--減低比對次數, 記憶最多比對到那一個質數
endif
mfound =.t.
*!* FOR EACH mvar IN mprime
*!* DO case
*!* CASE mvar>msqrt
*!* exit
*!* case i%mvar = 0
*!* mfound = .f.
*!* exit
*!* ENDcase
*!* endfor
mfound =.t.
FOR j=2 TO mendpoint
IF i%mprime[j] = 0
mfound = .f.
exit
ENDIF
next
IF mfound
mpc=mpc+1
DIMENSION mprime[mpc]
mprime[mpc]=i
ENDIF
NEXT
? '第四種算法再進化:從 2 到 '+tran(mmax)+' 中總共有'+tran(mpc)+' 個質數', SECONDS( )-mstart
|
_________________
利用>>搜尋<<的功能會比問的還要快得到答案. |
|
| 回頂端 |
|
|
ckp6250
註冊時間: 2004-07-30
文章: 1645
第 14 樓
|
| 發表於: 星期五 五月 08, 2015 3:01 pm 文章主題: |
|
|
garfield的陣列運算再再進化,大約再快了6%-10%
| 代碼: |
mmax = 1000000
mstart = Seconds( )
mpc=2
Dimension mprime[mmax/5] && 一次取足 , 免除多次�]定
mprime[1]=2
mprime[2]=3
mendpoint = 2
For i=5 To mmax Step 2
msqrt = Sqrt(i) &&--最多算到平方根
If msqrt > mprime[mendpoint]
mendpoint = mendpoint+1 &&--減低比對次數, 記憶最多比對到那一個質數
Endif
mfound =.T.
For j=2 To mendpoint
If i%mprime[j] = 0
mfound = .F.
Exit
Endif
Next
If mfound
mpc=mpc+1
*!* Dimension mprime[mpc] && 一次取足 , 免除多次�]定
mprime[mpc]=i
Endif
Next
? '第四種算法再進化:從 2 到 '+Tran(mmax)+' 中總共有'+Tran(mpc)+' 個質數', Seconds( )-mstart
|
|
|
| 回頂端 |
|
|
perry
註冊時間: 2014-07-20
文章: 203
第 15 樓
|
| 發表於: 星期五 五月 08, 2015 6:54 pm 文章主題: |
|
|
將第2組 for ... next 中 的 if mprime[j]<=msqrt 移出
把判斷變成執行1次大大提昇運算效能^^
模仿garfield 大大寫的,雖然比不上,
但crea curs 運算己達極限,無法減少迴圈判斷次數= ='''
| 代碼: |
mmax=1000000
CLEAR
priv p_l,p_f,p_tf,i,j,l_no,l_no1,mcount,mstart
mstart = SECONDS( )
sele 0
p_f='z'+righ(sys(2015),7)
p_l=len(allt(str(mmax)))
p_tf=.t.
crea curs (P_F) (tryno n(p_l))
inse into (P_F) valu (2)
inse into (P_F) valu (3)
mcount=2
l_no=3
l_no1=2
sele (p_f)
FOR i=5 TO mmax step 2
p_tf=.t.
go 2
for j=2 to l_no1
if i%tryno=0
p_tf=.f.
exit
endi
skip
next
if p_tf
mcount=mcount+1
Inse Into (p_f) Valu (i)
endi
if sqrt(i+2)>l_no
l_no1=l_no1+1
go l_no1
l_no=tryno
endi
next
wait wind '第3種算法:從 2 到 '+tran(mmax)+' 中總共有'+tran(mcount)+' 個質數 , '+str(SECONDS( )-mstart,10,3)
use in (p_f)
|
|
|
| 回頂端 |
|
|
|
|
您 無法 在這個版面發表文章
您 無法 在這個版面回覆文章
您 無法 在這個版面編輯文章
您 無法 在這個版面刪除文章
您 無法 在這個版面進行投票
您 無法 在這個版面附加檔案
您 無法 在這個版面下載檔案
|
|
常見問題
搜尋
會員列表
會員群組
會員註冊
個人資料
登入檢查您的私人訊息
登入
