Discussion :

[Grasshoper]

Bonsoir à toutes et tous,

J'ai écris un petit programme en C++ pour simuler un modèle, que je fais tourner en local pour le moment avec un vieux compilateur (Parallélisation & le compilateur efficace & exécution sur cluster prévus par la suite). J'ai réalisé un petit profilage et clairement ce qui prends beaucoup (j'insiste! ) de temps de calcul est une simple opération de parcours d'un 'grand' (de l'ordre de 10^14 voire beaucoup plus) vecteur de double.
Ce vecteur 'double * L_positions' est indexé linéairement et contient des localisations spatiales (2D). Je cherche à trouver la localisation 'loc' qui est la plus proche de 'pos'.
Je répète cette opération un grand nombre de fois (de l'ordre de 10^7 environ voire plus).

Je ne suis pas un expert en C++, mais voici ce que j'ai réalisé pour le moment, que me conseilleriez-vous de faire en particulier pour en améliorer la rapidité d'exécution ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
double min_dis = L_size *1.41421356237 +1;
for(int i=0; i < n; i++)
if(Tools().eucli_distance(pos->x ,pos->y, L_positions[i], L_positions[i+n]) < min_dis) {
    loc->x = L_positions[i];
    loc->y = L_positions[i+n];
    min_dis = Tools().eucli_distance(pos->x ,pos->y, L_positions[i], L_positions[i+n]);
}

avec:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
double Tools::eucli_distance(const double x1, const double y1, const double x2, const double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

avec une structure

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
struct Point2D          //Helper to stock 2D locations.
{ double x; double y; };

Merci par avance,

Bien à vous,

Grass

[Matt_Houston]

Pour commencer évite sqrt et compare directement les carrés des distances : si a * a < b * b est vérifié alors a < b l'est aussi.

Ensuite, peut-être partitionner l'espace et répartir tes points dans des « buckets » qui correspondent à des régions spatiales. Enfin, as-tu vraiment besoin de traiter une si grosse quantité de données en une fois (peut-être que oui, mais c'est bien de se poser la question) ?

[Grasshoper]

Merci pour ces informations utiles! je vais donc renvoyer sqrt() aux oubliettes
Je travaille sur des questions d'échelles temporelles et spatiales en temps long et il me faut malheureusement beaucoup d'observations pour confronter les théories.
J'avais effectivement commencé par travailler sur un fenêtrage de l'espace pour me concentrer sur des points en particulier, mon soucis étant que je dois quand même savoir quels points sont dans quel région de l'espace. Du coup il me faut parcourir 'L_locations', sauf si une solution alternative existe, mais je ne sais pas.

[Matt_Houston]

On espère bien que diverses méthodes ont déjà été proposées, le problème n'est pas nouveau.. Reste à déterminer celle(s) qui colle(nt) à ton cas d'utilisation.

Si tu optes pour un simple partitionnement (un octree, par exemple), c'est au moment de leur ajout dans la collection que tu peux choisir de trier les points par appartenance à une région. Par la suite, à chaque recherche tu peux écarter tous les points qui ne sont pas dans les régions adjacentes à la position considérée.

[Grasshoper]

Merci pour ce lien, plein de belles options!
Je coche comme résolu!
Merci