使用多線程的無序映射的C++羣體

我想知道是否有一種方法來加速稱爲（path_from_startend）的無序映射的人口。無序地圖總是有一個唯一的密鑰。使用多線程的無序映射的C++羣體

#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)); 

      } 
     } 

    }

來源

2017-04-02 Marian Daniel

由於線程之間共享'path_from_startend'，因此插入操作必須進入臨界區。那麼問題是，'pathbot.FindPath'需要很長時間嗎？否則，這是毫無意義的，因爲你有效地填充地圖（由於關鍵部分）。 –

FindPath是一個確實需要一點時間（毫秒）的A *算法。 –

然後我的答案應該可以幫到你。我更新了它，以匹配您的代碼。 –

你可以試試下面的模式是否會讓你獲得一些速度。你基本上是填充部分地圖，然後你合併到整個地圖中。加速很大程度上取決於元素的構建和插入需要多長時間。如果你的元素構造和插入很便宜，那麼你的加速甚至可能是負的，因爲對於每個局部地圖，它必須通過整個地圖搜索重複。

#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()); 
}

來源

2017-04-02 02:57:36

感謝這些指針，它的確讓我的時間減少了很多。但是，正如@Jeremy提到的那樣，我發現： 1）使用字符串作爲關鍵字非常昂貴 2）我可以稍微改變算法，使其成爲O（n）操作而不是O（n^2） –

使用多線程的無序映射的C++羣體

回答

相關問題