python - 从两个字典中找到最接近的可能值

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。

编辑 - 这很重要:A 和 B 的键是相同的，但是对应于 A 和 B 中的键的值B 不同。特定的 key 选择将产生不同于任何其他可能的顺序对 (A2,B2) 的有序对 (A1,B1)——不同的 key 具有不同的顺序对。例如，A 和 B 都有键 3,4，这将产生 1.0 的值对于字典 A 和 2.0 对于 B。然后将这个键与所有其他可能的键进行比较，以找到另一个有序对(即 A 和 B 中的项的键和值)，从而最小化它们之间的平方差。

Answer 1

您需要专门的数据结构，而不是标准的 Python 字典。查找四叉树或 kd 树。您有效地最小化了两点之间的欧几里德距离(您的目标函数与欧几里德距离仅相差一个平方根，并且您的字典 A 存储 x 坐标，B 存储 y 坐标。)。计算几何人多年来一直在研究这个问题。

好吧，也许我误读了您的问题并使它变得比实际更难。你是说你可以从 A 中选择 任何 值，从 B 中选择 任何 值，而不管它们的键是否相同？比如A的pick可以是K:V(3,4):2.0，B的pick可以是(5,6):3.0？或者它必须是 (3,4):2.0 来自 A 和 (3,4):6.0 来自 B？如果是前者，问题就很简单:只需遍历 A 中的值并找到最接近 A1 的值；然后遍历 B 的值并找到最接近 B1 的值。如果是后者，我的第一段就是正确答案。

你的评论说你想解决的是更难的问题，所以这里再补充一点。 Sedgewick 的幻灯片解释了静态网格、二维树和四叉树的工作原理。 http://algs4.cs.princeton.edu/lectures/99GeometricSearch.pdf .幻灯片 15 到 29 主要解释了二维树，幻灯片 27 到 29 涵盖了最近邻问题的解决方案。由于您有算法找到的点必须与查询点既不共享 x 坐标也不共享 y 坐标的约束，因此您可能必须自己实现算法或修改现有实现。一种替代策略是使用 kNN 数据结构(k 个最近邻居，而不是单个最近邻居)，对 k 进行试验，并希望您选择的 k 总是足够大以找到至少一个满足您的约束的邻居。