各位版友好
今天我有n个点,求每一个点到直线L的距离,最终找出其中一点
且此点到直线L的距离最长
直观的来讲我只需要做n次并用max函数即可
但我希望速度能够更快
所以想请教各位是否有算法可以加速计算此部分 谢谢
作者:
yr (Sooner Born Sooner Bred)
2015-05-17 00:16:00那就边做算把 max 存著，这样快了一些 :p
我认为距离公式有乘除又有根号,计算量很大如果先做convex hull再对外围顶点做距离公式,取其最大值这样应该会比较快,但或许有更好的方式啦
作者:
EdisonX (卡卡兽)
2015-05-17 00:27:00分母部份应该可以省掉，只要算分子。
作者:
Leeng (Leeng)
2015-05-17 00:35:00是不是只要求哪个点就好，距离的值不care?其他的点也不care那就每次只要算|ax+by+c|；比前一个小就discard后面根号那一坨根本就不用算，或最后取完点后，算一次就好不能先排序吧 一排序就是NlogN 除非你在输入资料的时候
作者:
Leeng (Leeng)
2015-05-17 01:11:00就先建好，不过那也是要N量级想到一个啦 假如取index[i]会耗时的话 就用指标++ ....不过你的data可能是文件读进来的吧 那可能连阵列都不用存
作者:
Leeng (Leeng)
2015-05-17 01:14:00边读就能边算、边discard是写C/C++ ?
指标++和index[i]最佳化开下去是一样的东西我不认为有O(N)以下的方法平行处理吧 分k组个别求最大，在比较各组冠军再来就你真的嫌太慢还是只是想做?这种状况读档可能比计算慢
读档的部分在时间上我可以不在意,我只在意计算距离找点的部分我只是想试着看看没有更快的方式
作者:
Leeng (Leeng)
2015-05-17 01:20:00如果还有其他几何可能的话，只能有请高斯了
只求一次的话就直接算吧,也会对其他线求最大值那做个convex hull,第二次会快很多
还有你的档案是文字格式还是可直接序列化的二进制格式这两者速度会差上数百倍
我的n个点是时间序列,没有什么特别性质RealJack抱歉 不太懂你的意思
作者:
EdisonX (卡卡兽)
2015-05-17 01:54:00(1) 对 10K 个点找最近,是只会做一次还是会重复做 ?(2) 你的来源资料是你可以读得懂的文字档吗 ?(3) n个点是时间序列没错,已知是2维,还有没有特殊性质 ?结果上述的问题。然后平行化+1.抱歉修正一下, 是对 10K 个点找最远 @@
作者: LiloHuang (十年一刻) 2015-05-17 15:10:00
这类问题很适合用 GLSL 或者 OpenCL 来做平行计算我找到一个 GLSL 版本供你参考
http://goo.gl/SokaVC作者:
FRAXIS (喔喔)
2015-05-17 21:45:00依照我的经验 dis 的计算和 if condition 会造成 delay你可以手动用类似 software pipeling 的方法加快一点你可以试着用 profiling tool 去观察每个 instruction的时间 然后再思考怎么改进你的问题 O(n) 的时间是不能避免的了 但是或许可以减少outer loop 呼叫这 function 的次数..
作者: sulf (sulf) 2015-11-13 12:01:00
矩阵旋转，把直线当成新X轴，只要计算新的y座标比较