Поиск ближайших возможных значений из двух словарей

Question

Давайте предположим, что у вас есть два существующих словарей A и B

Если вы уже остановили свой выбор на первые два элементов из словарей A и B со значениями A1 = 1.0 и B1 = 2.0, соответственно, есть ли способ найти любые два разных существующих предмета в словарях A и B, каждый из которых имеет разные значения (то есть A2 и B2) от A1 и B1, а также минимизирует значение (A2-A1)**2 + (B2-B1)**2?

Количество элементов в словаре нефиксировано и может превышать 100 000.

Edit - Это важно: ключи для A и B одинаковы, но значения, соответствующие этим ключам в A и B различны. Определенный выбор ключа даст упорядоченную пару (A1, B1), которая отличается от любой другой возможной пары ордеров (A2, B2) - разные ключи имеют разные пары ордеров. Например, оба A и B будут иметь ключ 3,4, и это даст значение 1.0 для dict A и 2.0 для B. Затем этот один ключ сравнивается с любым другим ключом, который может найти другую упорядоченную пару (то есть как ключ, так и значения элементов в A и B), что минимизирует квадраты различий между ними.

Answer 1

Вам понадобится специализированная структура данных, а не стандартный словарь Python. Посмотрите на квадратное дерево или kd-дерево. Вы эффективно сводите к минимуму евклидово расстояние между двумя точками (ваша целевая функция - всего лишь квадратный корень от евклидова расстояния, а ваш словарь A хранит x-координаты, B y-координаты.). Люди вычислительной геометрии изучали это в течение многих лет.

Возможно, я неверно истолковал ваш вопрос и делал его труднее, чем он есть. Вы говорите, что вы можете выбрать любое значение от A и любое значение от B, независимо от того, являются ли их ключи одинаковыми? Например, выбор из A может быть K: V (3,4): 2,0, а выбор из B может быть (5,6): 3,0? Или это должно быть (3,4): 2,0 от A и (3,4): 6,0 от B? Если первое, проблема проста: просто пробегите значения от A и найдите ближайший к A1; затем пробегите значения из B и найдите ближайший к B1. Если последний, мой первый абзац был правильным ответом.

Ваш комментарий говорит, что сложнее проблема, которую вы хотите решить, так что вот немного больше. Слайды Sedgewick объясняют, как работают статическая сетка, 2d-дерево и квадро-дерево. http://algs4.cs.princeton.edu/lectures/99GeometricSearch.pdf. Слайды с 15 по 29 объясняют главным образом 2d-дерево, с 27 по 29, охватывающее решение проблемы ближайшего соседа. Поскольку у вас есть ограничение на то, что точка, найденная алгоритмом, не должна делиться ни координатой x, ни y с точкой запроса, вам, возможно, придется реализовать алгоритм самостоятельно или изменить существующую реализацию. Одна из альтернативных стратегий - использовать структуру данных kNN (k ближайших соседей, в отличие от одного ближайшего соседа), экспериментировать с k и надеяться, что ваш выбранный k всегда будет достаточно большим, чтобы найти хотя бы одного соседа, который соответствует вашему ограничению.