title: Find nearest 3D point
body: <p>I have two data files, each of them contain a big number of 3-dimensional points (file A stores approximately 50,000 points, file B stores approximately 500,000 points). My goal is to find for every point (a) in file A the point (b) in file B which has the smallest distance to (a). I store the points in two lists like this:</p>
  
  <p>List A <em>nodes</em>:</p>
  
  <pre><code>   (ID        X       Y         Z)
  [  ['478277', -107.0, 190.5674, 128.1634],
     ['478279', -107.0, 190.5674, 134.0172],
     ['478282', -107.0, 190.5674, 131.0903],
     ['478283', -107.0, 191.9798, 124.6807],
                                         ... ]
  </code></pre>
  
  <p>List B <em>data</em>:</p>
  
  <pre><code>   (X        Y        Z        Data)
  [  [-28.102, 173.657, 229.744, 14.318],
     [-28.265, 175.549, 227.824, 13.648],
     [-27.695, 175.925, 227.133, 13.142],
                                       ...]
  </code></pre>
  
  <p>My first approach was to simply iterate through the first and second list with a nested loop and compute the distance between every points like this:</p>
  
  <pre><code>outfile = open(job[0] + '/' + output, 'wb');
  
  dist_min = float(job[5]);
  dist_max = float(job[6]);
  
  dists = [];
  
  for node in nodes:
  
    shortest_distance = 1000.0;
    shortest_data = 0.0;
  
    for entry in data:
      dist = math.sqrt((node[1] - entry[0])**2 + (node[2] - entry[1])**2 + (node[3] - entry[2])**2);
      if (dist_min &lt;= dist &lt;= dist_max) and (dist &lt; shortest_distance):
        shortest_distance = dist;
        shortest_data = entry[3];
  
    outfile.write(node[0] + ', ' + str('%10.5f' % shortest_data + '\n'));
  
  outfile.close();
  </code></pre>
  
  <p>I recognized that the amount of loops Python has to run is way too big (~25,000,000,000), so I had to fasten my code. I tried to first calculate all distances with list comprehensions but the code still is too slow:</p>
  
  <pre><code>p_x = [row[1] for row in nodes];
  p_y = [row[2] for row in nodes];
  p_z = [row[3] for row in nodes];
  
  q_x = [row[0] for row in data];
  q_y = [row[1] for row in data];
  q_z = [row[2] for row in data];
  
  dx = [[(px - qx) for px in p_x] for qx in q_x];
  dy = [[(py - qy) for py in p_y] for qy in q_y];
  dz = [[(pz - qz) for pz in p_z] for qz in q_z];
  
  dx = [[dxxx * dxxx for dxxx in dxx] for dxx in dx];
  dy = [[dyyy * dyyy for dyyy in dyy] for dyy in dy];
  dz = [[dzzz * dzzz for dzzz in dzz] for dzz in dz];
  
  D = [[(dx[i][j] + dy[i][j] + dz[i][j]) for j in range(len(dx[0]))] for i in range(len(dx))];
  D = [[(DDD**(0.5)) for DDD in DD] for DD in D]; 
  </code></pre>
  
  <p>To be honest, at this point, I do not know which of the two approaches is better, anyway, none of the two possibilities seem feasible. I'm not even sure if it is possible to write a code which calculates all distances in an acceptable time. Is there even another way to solve my problem without calculating all distances?</p>
  
  <p><em>Edit: I forgot to mention that I am running on Python 2.5.1 and am not allowed to install or add any new libraries...</em></p>