Sza*_*lcs 10 language-agnostic algorithm data-structures
tl; dr如何Nearest有效地实施Mathematica这样的东西？
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可以使用多维数据以及任意距离函数,所以我认为它使用了更通用的东西.但如果事实证明它专门用于某些类型的数据/距离函数,我不会感到惊讶.