tl;dr Mathematica 的Nearest 之类的东西如何有效地实现？
Mathematica有一个函数叫做 Nearest这将采用“事物”列表(它们可以是数字、n 维空间中的坐标、字符串等)，并将返回一个 NearestFunction 对象。此对象是一个函数，当应用于 x 时，将返回距离 x 最接近某个距离度量的列表元素。距离度量可以作为参数传递给 Nearest:默认情况下，它对数值数据使用欧几里得距离，对字符串使用某种编辑距离。
示例(这有望使问题更清楚):
nf = Nearest[{92, 64, 26, 89, 39, 19, 66, 58, 65, 39}];
nf[50] 将返回 58，最接近 50 的元素。 nf[50, 2] 将返回 {58, 39}，两个最接近的元素。
问题:什么是实现此功能的有效方法？ NearestFunction 可能在内部使用哪种数据结构？为不同类型的数据计算最近元素的最佳可能复杂度是多少？
对于一个简单的数字列表，对它们进行排序并进行二分查找是可行的，但是 Nearest 适用于多维数据以及任意距离函数，所以我想它使用了更通用的东西。但如果它专门用于某些类型的数据/距离函数，我不会感到惊讶。
最佳答案
对于性能良好的距离函数，有许多专门为此优化的数据结构。对于多维数据，k-d tree (和其他 binary space partitioning trees )可以给出优秀的 nearest-neighbor searches ，通常在亚线性时间内。您可能还想查看 metric trees ，它们是优化的树结构，以支持最近邻搜索的方式在某些度量空间中存储点。根据特定的度量空间(欧氏距离、编辑距离等)，不同的数据结构可能或多或少是合适的。
对于行为没有限制的任意距离函数(例如，甚至没有像三角不等式这样的东西)，那么你能做的最好的就是线性搜索，因为距离函数可能对所有点都是无限的除了集合中的一个特定点。
希望这对您有所帮助!
关于algorithm - 有效地从集合中检索最近元素的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9463165/