从两个字典中查找最接近的可能值

Question

假设您有两个现有词典A和B

如果您已经从字典A和B中分别选择了值为A1 = 1.0和B1 = 2.0的两个初始项，是否有任何方法可以在字典A和B中找到任何两个不同的现有项，它们的值（即A2和B2）与A1和B1不同，也会最小化值(A2-A1)**2 + (B2-B1)**2？你知道吗

词典中的条目数是不固定的，可能超过100000条。你知道吗

编辑-这一点很重要：A和B的键是相同的，但是A和B中那些键对应的值是不同的。一个特定的密钥选择将产生一个有序对（A1，B1），它不同于任何其他可能的有序对（A2，B2）-不同的密钥有不同的有序对。例如，A和B都将具有键3,4，这将为dict A和2.0生成值1.0。然后将这一个键与其他所有可能的键进行比较，以找到另一个有序对（即A和B中的项的键和值），使它们之间的平方差最小化。你知道吗

Answer 1

您将需要一个专门的数据结构，而不是一个标准的Python字典。查找四叉树或kd树。你有效地最小化了两点之间的欧氏距离（你的目标函数距离欧氏距离只有一个平方根，你的字典a存储x坐标，by坐标）。计算几何人们已经研究了很多年了。你知道吗

好吧，也许我误读了你的问题，把问题弄得更难了。你是说你可以从A中选择任意值，从B中选择任意值，不管它们的键是否相同？例如，从A中选取的值可以是K:V（3,4）：2.0，从B中选取的值可以是（5,6）：3.0？或者它必须是A的（3,4）：2.0和B的（3,4）：6.0？如果是前者，问题很简单：只需遍历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始终足够大，能够找到至少一个满足您的约束的邻居。你知道吗