请教一个加速算法问题
一个 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
