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 работает с многомерными данными, а также с произвольной функцией расстояния, поэтому я предполагаю, что он использует что-то более общее. Но я не удивлюсь, если он окажется специализированным для определенных видов функций данных/расстояний.
