J'ai deux fichiers de données, chacun d'entre eux contient un grand nombre de points en 3 dimensions (le fichier A stocke environ 50 000 points, le fichier B stocke environ 500 000 points). Mon but est de trouver pour chaque point (a) dans le fichier A le point (b) dans le fichier B qui a la plus petite distance à (a). Je stocke les points dans deux listes comme ceci:Trouver le point 3D le plus proche
Liste A nœuds:
(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],
... ]
Liste B données:
(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],
...]
Ma première approche a consisté à parcourons simplement la première et deuxième liste avec une boucle imbriquée et calculer la distance entre tous les points comme ceci:
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 <= dist <= dist_max) and (dist < shortest_distance):
shortest_distance = dist;
shortest_data = entry[3];
outfile.write(node[0] + ', ' + str('%10.5f' % shortest_data + '\n'));
outfile.close();
J'ai reconnu que le nombre de boucles que Python doit exécuter est beaucoup trop important (~ 25 000 000 000), j'ai donc dû fixer mon code. J'ai essayé d'abord calculer toutes les distances avec compréhensions de liste mais le code est encore trop lent:
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];
Pour être honnête, à ce stade, je ne sais pas lequel des deux approches est mieux, de toute façon, aucun des deux possibilités semblent réalisables. Je ne suis même pas sûr s'il est possible d'écrire un code qui calcule toutes les distances dans un temps acceptable. Y a-t-il encore une autre façon de résoudre mon problème sans calculer toutes les distances?
Edit: J'ai oublié de mentionner que je suis en cours d'exécution sur Python 2.5.1 et ne suis pas autorisé à installer ou d'ajouter de nouvelles bibliothèques ...
