Re: [問題] 多點到直線的距離
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/05/18 07:33)推噓0(0推 0噓 14→)留言14則, 3人參與討論串2/2 (看更多)
: let ax+b-y = 0
: for (i=1,i<10000,i++)
: {
: dis = abs(a*xpoint[i]+b-ypoint[i])
: if (dis>dismax)
: {
: dismax = dis
: point = i <-------這是我的目的 想要找哪一個點
: }
我假設你已經測試過了，這部份是 bottleneck，而且這些計算是必須的。
已經有人建議用平行化了，我這邊提供用單 CPU 的稍微加快的技巧。
dis 計算其實就只是 dot product + abs，這兩個指令應該可以直接由
硬體支援，你可以編譯成 assembly 檢查一下。
讀取 point 的時候是循序讀的，所以可以使用 prefetch，或許可以減少存取時間。
計算完 dis 之後立刻作 comparison 會造成 data hazard，pipeline就堵死了。
你可以改成類似這樣
dis = abs(a*xpoint[i]+b-ypoint[i]);
if (pre_dis > dismax) ....
pre_dis = dis;
這些技巧有沒有用，取決於你的機器和資料，而且就算變快效果應該也很有限。
又因為你沒有提供 profiling 的資訊，我也很難猜測到底是慢在哪個指令上，
只能憑我的經驗去猜而已。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 50.133.134.181
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1431905639.A.9A6.html
→
05/18 10:41, , 1F
05/18 10:41, 1F
→
05/19 00:06, , 2F
05/19 00:06, 2F
→
05/23 13:28, , 3F
05/23 13:28, 3F
→
05/23 19:24, , 4F
05/23 19:24, 4F
→
05/23 22:58, , 5F
05/23 22:58, 5F
→
05/23 23:01, , 6F
05/23 23:01, 6F
→
05/23 23:02, , 7F
05/23 23:02, 7F
→
05/23 23:03, , 8F
05/23 23:03, 8F
→
05/23 23:07, , 9F
05/23 23:07, 9F
→
05/23 23:08, , 10F
05/23 23:08, 10F
→
05/23 23:40, , 11F
05/23 23:40, 11F
→
05/23 23:40, , 12F
05/23 23:40, 12F
→
05/24 20:44, , 13F
05/24 20:44, 13F
→
05/24 20:44, , 14F
05/24 20:44, 14F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
