Выбор оптимального набора совпадающих элементов из списков

https://ru.wikipedia.org/wiki/Задача_поиска_ближайшего_соседа#Алгоритмы

п.4 только мешает. Если можно сразу сортируй по абсолютной величине sqrt(a1^2+a2^2+a3^2+….), тогда всё проще

Тут можно корень не извлекать

Перебором с минимальной оптимизацией будет норм. В общем случае, учитывая, что ты сравниваешь не по точному совпадению, а попаданию в окрестность, ты будешь иметь O(n^2) для худшего случая, как ни крути.

Поэтому бежишь по первому списку и бинарным поиском находишь ближайшие вектора по первой координате в нужной окрестности, потом тупо проверяешь все эти вектора. Думаю, что ты так и делал.

Если один список большой и редко обновляется, то я бы его загнал в R-дерево, только вместо Rectangle может быть использовал бы что то, что более близко к твоей функции близости векторов… Но это только если оптимизация по скорости действительно важна.

Если ты точно уверен что у тебя именно здесь узкое место, и это не голос внушённой преподавателями догмы «n² - плохо», то выбирай:

1. Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае. Если у координат разные распределения, может быть быстрее пересортировать но хорошей координате чем получить квадрат на плохой.

2. Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (32-дерево, хотя для него измерений уже многовато, rtree и другие про разбиение пространства). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и в худшем случае.

3. Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одну ячейку-кубик этой сетки. delta-окрестность вектора пересекается с 32 ячейками сетки. Соответственно, можно взять хэшмапу с ключами от координат кубика, и либо записать в неё каждый вектор 32 раза, либо делать к ней 32 запроса, таким образом получая вектора в delta-окрестности заданной точки за константу. Может иметь смысл взять сетку крупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.

Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за O(n) сделать, хотя это и даст неточное решение). Алсо имеет значение по какому списку итерироваться, а по какому строить структуру для лукапа, особенно если в них значительно различается распределение или размер. Алсо решения можно комбинировать, разделяя обособленные вектора и кучки.

Перебором с минимальной оптимизацией будет норм. В общем случае, учитывая, что ты сравниваешь не по точному совпадению, а попаданию в окрестность, ты будешь иметь O(n^2) для худшего случая, как ни крути.

С чего это n^2? Выше ведь уже правильно кидали ссылку на поиск ближайшего соседа. При ограничении на размерность пространства будет O(n log n)

Тут можно корень не извлекать

лучше извлечь.

Во первых абсолютная величина вектора скорее всего много где пригодится, не зря-же они вектора. Отчего не вычислить её сразу.

Во вторых после сравнения абс.величин по хорошему надо смотреть угол между векторами, и там всё равно корень нужен ;-)

Ну вот так вот, O(n^2), потому что сравнение не точное, было бы точное, то да, можно было бы за O(n log n).

Поиск в R-дереве в худшем случае дает O(n), а не O(log n).

Никто не сказал что вектора в евклидовом пространстве. Может там одна из размерностей какой-нить enum

Да, там 3 координаты это по сути углы, а 2 координаты - некоторые безразмерные коэффициенты

Задача, которую я решаю, это отождествление звезд на разлиных астрофото одного и того же участка неба. Для этого я для каждой звезды смотрю на ее размер и положение относительно других звезд. В итоге получаю дескриптор звезды - список 5-мерных векторов. А затем я считаю, что звезда одного изображения отождествляется со звездой другого изображения, если в их дескрипторах есть достаточное количество достаточно близких векторов.

Если можно придумать такую хеш-функцию, при которой несовпадение хешей гарантирует несовпадение векторов, то можно сильно срезать количество анализируемых векторов. Остальные можно обработать «в лоб».

Если можно придумать однозначную функцию «больше», «меньше», «равно» для этих векторов, то формируем два сортированных индекса по этой функции для каждого из этих списков. Потом линейно обходим по этим двум индексам отсеивая лишнее, через указанную функцию.

1. Округлить значения до нужной точности и перевести в integer (например домножив на 1024 или ещё какое число), чтобы «похожие» значения стали равны.

2. Трактовать пять значений как одно большое число.

3. Отсортировать оба массива.

Далее в отсортированных массивах легко найти одинаковые значения.

Вариант 2. Отсортировать оба массива по длине вектора. Далее будет известно, что похожие векторы будут иметь похожую длину, соответственно для каждого вектора из первого списка перебирать нужно будет не все векторы из второго списка, а только в небольшой окрестности. Но если у многих векторов длина совпадает, то этот алгоритм выродится в O(N^2).

Вариант 3, по сути разновидность варианта 2 - вместо длины вектора использовать любую другую функцию, сохраняющую близость векторов. Можно сумму координат, например.