Finding the closest possible values from two dictionaries
<p>Let's suppose you have two existing dictionaries <code>A</code> and <code>B</code></p>

<p>If you already choose an initial two items from dictionaries <code>A</code> and <code>B</code> with values <code>A1 = 1.0</code> and <code>B1 = 2.0</code>, respectively, is there any way to find any two different existing items in the dictionaries <code>A</code> and <code>B</code> that each have different values (i.e. <code>A2</code> and <code>B2</code>) from <code>A1</code> and <code>B1</code>, and would also minimize the value <code>(A2-A1)**2 + (B2-B1)**2</code>?</p>

<p>The number of items in the dictionary is unfixed and could exceed 100,000.</p>

<p>Edit - This is important: the keys for <code>A</code> and <code>B</code> are the same, but the values corresponding to those keys in <code>A</code> and <code>B</code> are different. A particular choice of key will yield an ordered pair (A1,B1) that is different from any other possible order pair (A2,B2)âdifferent keys have different order pairs. For example, both <code>A</code> and <code>B</code> will have the key <code>3,4</code> and this will yield a value of <code>1.0</code> for dict <code>A</code> and <code>2.0</code> for <code>B</code>. This one key will then be compared to every other key possible to find the other ordered pair (i.e. both the key and values of the items in <code>A</code> and <code>B</code>) that minimizes the squared differences between them. </p>

<p>You'll need a specialized data structure, not a standard Python dictionary. Look up quad-tree or kd-tree. You are effectively minimizing the Euclidean distance between two points (your objective function is just a square root away from Euclidean distance, and your dictionary A is storing x-coordinates, B y-coordinates.). Computational-geometry people have been studying this for years.</p>

<p>Well, maybe I am misreading your question and making it harder than it is. Are you saying that you can pick <em>any</em> value from A and <em>any</em> value from B, regardless of whether their keys are the same? For instance, the pick from A could be K:V (3,4):2.0, and the pick from B could be (5,6):3.0? Or does it have to be (3,4):2.0 from A and (3,4):6.0 from B? If the former, the problem is easy: just run through the values from A and find the closest to A1; then run through the values from B and find the closest to B1. If the latter, my first paragraph was the right answer.</p>

<p>Your comment says that the harder problem is the one you want to solve, so here is a little more. Sedgewick's slides explain how the static grid, the 2d-tree, and the quad-tree work. <a href="http://algs4.cs.princeton.edu/lectures/99GeometricSearch.pdf" rel="nofollow">http://algs4.cs.princeton.edu/lectures/99GeometricSearch.pdf</a> . Slides 15 through 29 explain mainly the 2d-tree, with 27 through 29 covering the solution to the nearest-neighbor problem. Since you have the constraint that the point the algorithm finds must share neither x- nor y-coordinate with the query point, you might have to implement the algorithm yourself or modify an existing implementation. One alternative strategy is to use a kNN data structure (k nearest neighbors, as opposed to the single nearest neighbor), experiment with k, and hope that your chosen k will always be large enough to find at least one neighbor that meets your constraint.</p>

python python-2.7 dictionary