各位版友好
今天我有n個點,求每一個點到直線L的距離,最終找出其中一點
且此點到直線L的距離最長
直觀的來講我只需要做n次並用max函數即可
但我希望速度能夠更快
所以想請教各位是否有演算法可以加速計算此部分 謝謝

那就邊做算把 max 存著，這樣快了一些 :p

這部分我有做了

我認為距離公式有乘除又有根號,計算量很大如果先做convex hull再對外圍頂點做距離公式,取其最大值這樣應該會比較快,但或許有更好的方式啦

分母部份應該可以省掉，只要算分子。

是不是只要求哪個點就好，距離的值不care?其他的點也不care那就每次只要算|ax+by+c|；比前一個小就discard後面根號那一坨根本就不用算，或最後取完點後，算一次就好不能先排序吧 一排序就是NlogN 除非你在輸入資料的時候

抱歉 剛剛才想到排序這樣做不行Orz

就先建好，不過那也是要N量級想到一個啦 假如取index[i]會耗時的話 就用指標++ ....不過你的data可能是文件讀進來的吧 那可能連陣列都不用存

不好意思 這部分我不太懂你的意思是指?

邊讀就能邊算、邊discard是寫C/C++ ?

指標++和index[i]最佳化開下去是一樣的東西我不認為有O(N)以下的方法平行處理吧 分k組個別求最大，在比較各組冠軍再來就你真的嫌太慢還是只是想做?這種狀況讀檔可能比計算慢

讀檔的部分在時間上我可以不在意,我只在意計算距離找點的部分我只是想試著看看沒有更快的方式

如果還有其他幾何可能的話，只能有請高斯了

只求一次的話就直接算吧,也會對其他線求最大值那做個convex hull,第二次會快很多

你的n個點有任何特殊性質嗎?像照著某種順序給?

還有你的檔案是文字格式還是可直接序列化的二進制格式這兩者速度會差上數百倍

我的n個點是時間序列,沒有甚麼特別性質RealJack抱歉 不太懂你的意思

(1) 對 10K 個點找最近,是只會做一次還是會重覆做 ?(2) 你的來源資料是你可以讀得懂的文字檔嗎 ?(3) n個點是時間序列沒錯,已知是2維,還有沒有特殊性質 ?結果上述的問題。然後平行化+1.抱歉修正一下, 是對 10K 個點找最遠 @@

改用C 平行處理 SIMD 能用的方法大概就這些

這類問題很適合用 GLSL 或者 OpenCL 來做平行計算我找到一個 GLSL 版本供你參考 http://goo.gl/SokaVC

依照我的經驗 dis 的計算和 if condition 會造成 delay你可以手動用類似 software pipeling 的方法加快一點你可以試著用 profiling tool 去觀察每個 instruction的時間 然後再思考怎麼改進你的問題 O(n) 的時間是不能避免的了 但是或許可以減少outer loop 呼叫這 function 的次數..

感謝各位版友的幫助 我會試著你們給的建議測試看看

矩陣旋轉，把直線當成新X軸，只要計算新的y座標比較