PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 多點到直線的距離

看板Prob_Solve (計算數學 Problem Solving)作者 (小天)時間9年前 (2015/05/16 22:46), 9年前編輯推噓9(9推 0噓 43→)
留言52則, 9人參與, 最新討論串1/2 (看更多)
各位版友好 今天我有n個點,求每一個點到直線L的距離,最終找出其中一點 且此點到直線L的距離最長 直觀的來講我只需要做n次並用max函數即可 但我希望速度能夠更快 所以想請教各位是否有演算法可以加速計算此部分 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 113.61.182.113 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1431787607.A.711.html
→
05/17 00:16, , 1F
那就邊做算把 max 存著，這樣快了一些 :p
05/17 00:16, 1F
→
05/17 00:19, , 2F
這部分我有做了
05/17 00:19, 2F
推
05/17 00:25, , 3F
我認為距離公式有乘除又有根號,計算量很大
05/17 00:25, 3F
→
05/17 00:26, , 4F
如果先做convex hull再對外圍頂點做距離公式,取其最大值
05/17 00:26, 4F
→
05/17 00:27, , 5F
這樣應該會比較快,但或許有更好的方式啦
05/17 00:27, 5F
→
05/17 00:27, , 6F
分母部份應該可以省掉，只要算分子。
05/17 00:27, 6F
推
05/17 00:35, , 7F
是不是只要求哪個點就好，距離的值不care?其他的點也不care
05/17 00:35, 7F
對 值不care 所以我沒有計算分母 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 <-------這是我的目的 想要找哪一個點 } } 這是我的程式碼 不知道是否有任何地方可以讓他計算速度變更快
→
05/17 00:36, , 8F
那就每次只要算|ax+by+c|；比前一個小就discard
05/17 00:36, 8F
→
05/17 00:37, , 9F
後面根號那一坨根本就不用算，或最後取完點後，算一次就好
05/17 00:37, 9F
※ 編輯: firingmoon (113.61.182.113), 05/17/2015 01:07:32
推
05/17 01:09, , 10F
不能先排序吧 一排序就是NlogN 除非你在輸入資料的時候
05/17 01:09, 10F
→
05/17 01:09, , 11F
抱歉 剛剛才想到排序這樣做不行Orz
05/17 01:09, 11F
推
05/17 01:11, , 12F
就先建好，不過那也是要N量級
05/17 01:11, 12F
→
05/17 01:12, , 13F
想到一個啦 假如取index[i]會耗時的話 就用指標++ ....
05/17 01:12, 13F
→
05/17 01:14, , 14F
不過你的data可能是文件讀進來的吧 那可能連陣列都不用存
05/17 01:14, 14F
→
05/17 01:14, , 15F
不好意思 這部分我不太懂你的意思是指?
05/17 01:14, 15F
→
05/17 01:14, , 16F
邊讀就能邊算、邊discard
05/17 01:14, 16F
→
05/17 01:14, , 17F
是寫C/C++ ?
05/17 01:14, 17F
→
05/17 01:14, , 18F
對 data是從文件讀進來,再丟去陣列 但這部分比較
05/17 01:14, 18F
→
05/17 01:14, , 19F
不care
05/17 01:14, 19F
→
05/17 01:15, , 20F
我是用C#
05/17 01:15, 20F
→
05/17 01:15, , 21F
指標++和index[i]最佳化開下去是一樣的東西
05/17 01:15, 21F
→
05/17 01:16, , 22F
我不認為有O(N)以下的方法
05/17 01:16, 22F
→
05/17 01:17, , 23F
平行處理吧 分k組個別求最大，在比較各組冠軍
05/17 01:17, 23F
→
05/17 01:18, , 24F
再來就你真的嫌太慢還是只是想做?
05/17 01:18, 24F
→
05/17 01:19, , 25F
這種狀況讀檔可能比計算慢
05/17 01:19, 25F
→
05/17 01:19, , 26F
讀檔的部分在時間上我可以不在意,我只在意計算距離
05/17 01:19, 26F
→
05/17 01:20, , 27F
找點的部分
05/17 01:20, 27F
→
05/17 01:20, , 28F
我只是想試著看看沒有更快的方式
05/17 01:20, 28F
推
05/17 01:20, , 29F
如果還有其他幾何可能的話，只能有請高斯了
05/17 01:20, 29F
推
05/17 01:25, , 30F
只求一次的話就直接算吧,也會對其他線求最大值那做個
05/17 01:25, 30F
→
05/17 01:26, , 31F
convex hull,第二次會快很多
05/17 01:26, 31F
→
05/17 01:31, , 32F
你的n個點有任何特殊性質嗎?像照著某種順序給?
05/17 01:31, 32F
推
05/17 01:31, , 33F
還有你的檔案是文字格式還是可直接序列化的二進制格式
05/17 01:31, 33F
→
05/17 01:32, , 34F
這兩者速度會差上數百倍
05/17 01:32, 34F
→
05/17 01:49, , 35F
我的n個點是時間序列,沒有甚麼特別性質
05/17 01:49, 35F
→
05/17 01:51, , 36F
RealJack抱歉 不太懂你的意思
05/17 01:51, 36F
→
05/17 01:54, , 37F
(1) 對 10K 個點找最近,是只會做一次還是會重覆做 ?
05/17 01:54, 37F
→
05/17 01:54, , 38F
(2) 你的來源資料是你可以讀得懂的文字檔嗎 ?
05/17 01:54, 38F
→
05/17 01:55, , 39F
(3) n個點是時間序列沒錯,已知是2維,還有沒有特殊性質 ?
05/17 01:55, 39F
→
05/17 01:55, , 40F
結果上述的問題。然後平行化+1.
05/17 01:55, 40F
→
05/17 01:56, , 41F
抱歉修正一下, 是對 10K 個點找最遠 @@
05/17 01:56, 41F
(1)只做一次 (2)讀得懂 基本上這部分不用太在意 (3)沒有特殊,單純就a[1],a[2],a[3]......... ※ 編輯: firingmoon (113.61.182.113), 05/17/2015 02:01:33
→
05/17 02:04, , 42F
改用C 平行處理 SIMD 能用的方法大概就這些
05/17 02:04, 42F
推
05/17 15:10, , 43F
這類問題很適合用 GLSL 或者 OpenCL 來做平行計算
05/17 15:10, 43F
→
05/17 15:21, , 44F
我找到一個 GLSL 版本供你參考 http://goo.gl/SokaVC
05/17 15:21, 44F
推
05/17 21:45, , 45F
依照我的經驗 dis 的計算和 if condition 會造成 delay
05/17 21:45, 45F
→
05/17 21:46, , 46F
你可以手動用類似 software pipeling 的方法加快一點
05/17 21:46, 46F
→
05/17 21:47, , 47F
你可以試著用 profiling tool 去觀察每個 instruction
05/17 21:47, 47F
→
05/17 21:47, , 48F
的時間 然後再思考怎麼改進
05/17 21:47, 48F
→
05/17 21:48, , 49F
你的問題 O(n) 的時間是不能避免的了 但是或許可以減少
05/17 21:48, 49F
→
05/17 21:48, , 50F
outer loop 呼叫這 function 的次數..
05/17 21:48, 50F
→
05/18 10:39, , 51F
感謝各位版友的幫助 我會試著你們給的建議測試看看
05/18 10:39, 51F
→
11/13 12:01, , 52F
矩陣旋轉，把直線當成新X軸，只要計算新的y座標比較
11/13 12:01, 52F
‣ 更多 firingmoon 的文章
文章代碼(AID): #1LLrXNSH (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 firingmoon 的文章
文章代碼(AID): #1LLrXNSH (Prob_Solve)