我试图在Haskell中实现kdtree(请参阅implementation)，但是我试图变得聪明，并在实现最近邻居算法时利用Haskells的惰性(请参见第46行)。
尽管从技术上讲是正确的，但它是:
minimumBy (compare `on` qd q) vs == head . nearestNeighbours (kdtree 5 vs) $ q
==> True
基于kdtree的版本要慢得多(标准:5.38ms与138.44ms，具有500k数据点)。我首先认为这是由于
ordMerge(第59行)中的模式匹配过于严格，但是我重写了它，并且根据我的理解，现在仅应根据需要评估bs。如果是这种情况，该算法应仅下降到匹配的存储桶，并在检查当前最佳最近邻居确实是最佳候选者时上升。
我做了一些分析，
nearestNeighhbors被调用了约800次。给定8和100个测试用例的树深度，这听起来很合理，不是吗？刚刚将我的代码上传到github:https://github.com/fhaust/threesg
这应该使您开始:
git clone https://github.com/fhaust/threesg
cd threesg
cabal sandbox init
cabal install --enable-benchmarks --enable-tests
cabal test
cabal bench --benchmark-options="+RTS -K100M -RTS"
(因为需要从500k点创建测试集，所以需要
-K100M)在为github创建测试集时，我注意到，在正态分布点上，kdtree搜索的运行速度比线性搜索快得多……可能我的问题不是算法……而是我的测试集:(
最佳答案
最后，这是一个跟踪评估顺序的问题。我在github上上传了最新版本。
看一看line 74:仅当第一个列表的第一个条目与“没有更好的候选者”标准不匹配时，才评估第二个列表。
按照条件，我确实更快地完成了benchmarking和kd-tree ist。
您如何看待该解决方案？我认为代码非常简洁易读。有明显的性能损失吗？