Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Nouveau membre du Club
    Inscrit en
    février 2013
    Messages
    64
    Détails du profil
    Informations forums :
    Inscription : février 2013
    Messages : 64
    Points : 39
    Points
    39

    Par défaut Optimisation: lecture itérative d'un grand vecteur

    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

  2. #2
    Expert confirmé
    Inscrit en
    mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : mars 2005
    Messages : 1 431
    Points : 4 179
    Points
    4 179

    Par défaut

    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) ?

  3. #3
    Nouveau membre du Club
    Inscrit en
    février 2013
    Messages
    64
    Détails du profil
    Informations forums :
    Inscription : février 2013
    Messages : 64
    Points : 39
    Points
    39

    Par défaut

    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.

  4. #4
    Expert confirmé
    Inscrit en
    mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : mars 2005
    Messages : 1 431
    Points : 4 179
    Points
    4 179

    Par défaut

    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.

  5. #5
    Nouveau membre du Club
    Inscrit en
    février 2013
    Messages
    64
    Détails du profil
    Informations forums :
    Inscription : février 2013
    Messages : 64
    Points : 39
    Points
    39

    Par défaut

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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 4
    Dernier message: 15/07/2007, 00h07
  2. Réponses: 2
    Dernier message: 01/03/2007, 18h05
  3. optimiser lecture fichier image
    Par cheho dans le forum C++
    Réponses: 17
    Dernier message: 15/09/2006, 14h14
  4. Optimisation lecture d'un fichier en binaire
    Par User dans le forum VB 6 et antérieur
    Réponses: 3
    Dernier message: 13/10/2005, 21h08

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo