点赞，谢谢！

我觉得你这个简化是对的。你可以做个实验验证一下，并且做个对比实验看看加速了多少。这是个很好的改进，点赞。

@Peter_Chen, @ZhangJ 有可能这个简化不如原版速度快，原因可能有：1. 原版代码中case1和case2的计算量都很少，很多情况在case1&2就退出了。2. 原版代码是通过numpy实现的，简化版是循环和if else，这些在python效率太低了。3. 简化版其实不必计算norm，算norm有一个开根号，是很慢的操作，所以算平方就可以了。

要验证原版和简化版哪个快，应该在cpp下对比才能排除干扰因素。希望你们，或者其他人能够做个可靠的评测，我对这个还挺期待的。谢谢！

好问题。可以用稀疏矩阵的特征值分解。也可以考虑不做gram matrix，转而设计一个\phi函数，做线性PCA。

1. 和聚类没有任何关系。冲突是无法避免的，所以要解决conflict，解决的办法就是@COSTAR回答的第二点。能否将距离较近的点落在同一个container这个是无法保证的，而且这么做对于voxel grid downsamle也没有任何意义。

2. 我也不理解你说的少9900个点是什么意思。downsample当然就是要少输出点。

假设你的voxel grid是1000x1000x1000，有10000个点。遍历这个voxel grid需要1000x1000x1000次，每一次还要查找哪些点落在了这个格子。运算量有多少？再想想，排序需要的运算量是10000 log(10000)。

@torww 你打算用什么数据结构来实现字典呢？你可以去看看各种形式的“map”（比如python的dict背后是什么数据结构），在这些数据结构里面，插入和查找一个key需要多少时间复杂度，空间复杂度。

比如你会说hash table的插入、查找的时间复杂度是O(1)。但是这个O(1)需要什么样的空间代价呢，出现冲突了怎么办？理论上你需要和voxel grid一样大的hash table才能保证不会冲突，而实际上需要比voxel grid大很多的hash table才能保证无冲突，即O(1)。这样的空间代价是很大的，因为一个voxel grid可以有1000*1000*1000这种级别。这里有个概念，hash table的load factor。那我用小一点的hash table，load factor就会很高，导致hash table的实际复杂度远高于O(1).

时间复杂度是一个方面，空间复杂度也很重要。因为内存的分配和访问是需要时间的。因此，做排序是最简单快速的实现方法。

@torww 最后题外话那里可能需要讨论一下。在建voxel grid的时候，是不知道哪个空哪个不空的，所以还是需要把hash table建的比M大。或者2D,2.5D，室内应用时候M不大，但是像自动驾驶这种，M是很恐怖的。