Population C++ de la carte non ordonnée utilisant le multithread

Question

Je me demandais s'il y avait un moyen d'accélérer la population d'une carte non ordonnée appelée (path_from_startend). La carte non ordonnée a toujours une clé unique.

#pragma omp parallel for 
    for (int i=start_index;i<end_index;++i){  
     for (int j=start_index;j<end_index;++j){ 
      string key= to_string(unique_locations[i])+to_string(unique_locations[j]); 
      //dont compute path to itself 
      if (i==j){ 
      } 
      else {    
        vector <unsigned> path = pathbot.FindPath(unique_locations[i],unique_locations[j],turn_penalty); 
        path_from_startend.insert(make_pair(key,path)); 

      } 
     } 

    } 

Answer 1

Vous pouvez essayer si le modèle suivant vous permet de gagner en vitesse. Vous remplissez essentiellement des cartes partielles que vous fusionnez ensuite dans toute la carte. L'accélération dépend beaucoup de la durée de construction et d'insertion des éléments. Si vos éléments sont peu coûteux à construire et à insérer, votre accélération peut même être négative, car pour chaque carte partielle, elle doit parcourir toute la carte à la recherche de doublons.

#pragma omp parallel 
{ 
    std::unordered_map < std::string, std::vector <unsigned> > partial; 

    #pragma omp for 
    for (int i = start_index; i < end_index; ++i) 
    {  
    for (int j = start_index; j < end_index; ++j) 
    { 
     std::string key = std::to_string(unique_locations[i]) 
         + std::to_string(unique_locations[j]); 

     //dont compute path to itself 
     if (i != j) 
     {    
     std::vector<unsigned> path = pathbot.FindPath(unique_locations[i], 
                 unique_locations[j], 
                 turn_penalty); 
     partial.insert(std::make_pair(key,path)); 
     } 
    } 
    } 

    #pragma omp critical 
    path_from_startend.insert(partial.begin(),partial.end()); 
}