请教一个加速算法问题
一个 list 含有 N 个三维空间的点,坐标以三元 tuple 形式列出,精确到小数点后第四位,例如:
[
(1.2345, 2.3456, 3.4567),
(4.5678, 5.6789, 6.7890),
...
]
现在要写一个程序,将上述点根据 “近似坐标” 分组,就是说,如果两个点的三个坐标分量,各自的偏差绝对值都 <= 0.001,就认为这两个点是同一个点,例如
(1.2345, 2.3456, 3.4567) 和
(1.2346, 2.3450, 3.4563)
是同一个点,因为 |dx| = 0.0001, |dy| = 0.0006, |dz| = 0.0004 都不超过 0.001
只要有一个坐标的偏差绝对值超过 0.001,这两个点一定不同。
注意,在上述条件下,可能会出现这样的情况:点A 和 点B 同一组,点B 和 点C 同一组,但 点A 和 点C 不同组。
我们不考虑这样的BUG,而是当发现 A 和 B 一组时立即把 B 归入 A,不再检测 B 和 C 是否同组。
如果 N 很小,这个程序不难写,双重循环搞定;但是我的 N 很大很大,可能超过100万,必须采用更高效的算法,您有什么好的解法吗?谢谢!
回答:
数据量比较大,从两个方面优化,优化算法,提高运行速度
算法
- 简单粗暴的算法是,将p[0]与p[1]~p[N]比较,然后p[1]与p[2]~p[N]比较,这样比较的次数是(N-1)+(N-2)+ ... + 2 + 1 = N*(N-1),复杂度O(n^2)
- 进一步考虑,如果将这些点先排序(优先级x>y>z,其实怎样的顺序都可以),那么可能合并的点必定是相邻的,或者说是距离接近的。那么只需要做两两比较就可以了(如果p[m]与p[m+1]合并,那么继续p[m]与p[m+2]比较),比较次数是N-1,排序算法也会耗时,选用适当的排序算法,复杂度O(NLogN),O(NLogN)+O(N) => O(NLogN), 整体上是比setp1省时的
- 运行速度
Cython编译成C加速,数据分割后用多线程加速等等,网上很多资料可以参考,这里就不展开了。
以上是 请教一个加速算法问题 的全部内容, 来源链接: utcz.com/a/165716.html