[討論] 平行化計算質數數量
*感謝版友EricTCartman和Schottky的建議 採用Sieve法來取質數*
*更新Sieve法的benchmark*
問題：計算小於N的質數數量.
接續問題：改成平行化. 且注意load-balance.
版本1(非平行化): 所有質數不會被小於自己的質數整除
用一個vector存所有小於N的質數,
M=[2..N], 只要確認所有小於M的質數無法整除就好,
最後回傳總數
版本2(非平行化): 所有質數不會被小於自己的整數整除
M=[2..N], 只確認所有小於M/2的數字無法整除
版本3(平行化): 將版本2用pthread實現
版本4(非平行化): Sieve法:質數的合數必不是質數
版本5(非平行化): 同上 只是將目標函式抽取出來
版本6(平行化): 將版本5以lock-free方式平行化且改為任何數的合數必不是質數
可編譯版本可以看下面這個gist
https://gist.github.com/noahleft/27c52232932db6c77e78d78e09d2420d
Benchmark: N=1M
版本1: 22.82 sec
版本2:128.62 sec
版本3: 72.73 sec
Benchmark: N=100M
版本4: 10.18 sec
版本5: 10.43 sec
版本6: 5.78 sec
值得注意的是我有試著用mux方式去實作"選擇下一個質數",
然而對這個題目而言,使用lock的成本太高
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.216.124 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1625367765.A.505.html
→
07/04 11:41,
2年前
, 1F
07/04 11:41, 1F
推
07/04 11:42,
2年前
, 2F
07/04 11:42, 2F
→
07/04 11:42,
2年前
, 3F
07/04 11:42, 3F
→
07/04 11:43,
2年前
, 4F
07/04 11:43, 4F
→
07/04 11:54,
2年前
, 5F
07/04 11:54, 5F
※ 編輯: noahleft (118.166.216.124 臺灣), 07/04/2021 15:21:20
→
07/05 19:43,
2年前
, 6F
07/05 19:43, 6F
→
07/05 19:43,
2年前
, 7F
07/05 19:43, 7F