我正在尝试在 Haskell 中实现一个 kdtree(参见 implementation)，但我在实现最近邻算法(参见第 46 行)时试图变得聪明并利用 Haskell 的惰性。
虽然它在技术上是正确的，但是:
minimumBy (compare `on` qd q) vs == head . nearestNeighbours (kdtree 5 vs) $ q
==> True
基于 kdtree 的版本要慢得多(标准:5.38 毫秒对 138.44 毫秒，有 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"
(需要-K100M，因为测试集是从 500k 点创建的)
在为 github 创建测试集时我注意到，在正态分布点上，kdtree 搜索比线性搜索运行得快很多......可能我的问题不是算法......但我的测试集:(
最佳答案
最后，这是一个跟踪评估顺序的问题。我在 github 上上传了最新版本.
看看line 74 : 只有当第一个列表的第一个条目不符合“没有更好的候选者”标准时，才会评估第二个列表。
Apropos 标准，我做了一些 benchmarking kd-tree 确实更快。
您如何看待这个解决方案？我认为代码非常简洁易读。是否有任何明显的性能损失？
关于haskell - 如何在 Haskell 中实现快速、惰性的 KDTree？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20119826/