std :: vector比std :: unordered_set更快嗎？

在我的自定義物理引擎中，最大的瓶頸是從空間分區（2D網格）獲取所有主體的方法，並返回一個只包含唯一指向主體的指針的集合。std :: vector比std :: unordered_set更快嗎？

template<typename T, typename V> bool contains(const T& mContainer, const V& mValue) 
{ 
    return std::find(std::begin(mContainer), 
        std::end(mContainer), mValue) != std::end(mContainer); 
} 

const vector<Body*>& GridInfo::getBodiesToCheck() 
{ 
    bodiesToCheck.clear(); 
    for(auto& query : queries) 
     for(auto& body : *query) 
      if(!contains(bodiesToCheck, body)) bodiesToCheck.push_back(body); 
    return bodiesToCheck; 
}

使用探查器顯示瓶頸在「contains」方法中。

顯然，std::unordered_set將是這裏的「理想」解決方案。但是，它比當前的解決方案慢很多。我也試過google::dense_hash_set，這比std::unordered_set快，但仍然比當前的解決方案慢。

const unordered_set<Body*>& GridInfo::getBodiesToCheck() 
{ 
    bodiesToCheck.clear(); 
    for(auto& query : queries) 
     for(auto& body : *query) 
      /*if(!contains(bodiesToCheck, body))*/ bodiesToCheck.insert(body); 
    return bodiesToCheck; 
}

爲什麼比std::vector慢「正確」的容器？

有什麼辦法可以進一步加速這個方法嗎？

來源

2013-04-08 Vittorio Romeo

性能分析結果僅適用於'contains'？記住搜索設置可能會更快，但插入比向量慢。 – 2013-04-08 13:16:04

我假設你沒有犯這樣的錯誤，但只是爲了真正確定，你在嘗試'std :: unordered_map'時沒有使用'std :: find'，是嗎？ – 2013-04-08 13:18:56

@stardust_ Profiler將「getBodiesToCheck（）」方法顯示爲瓶頸。如果我使用std :: vector版本，getBodiesToCheck（）（瓶頸瓶頸：P）中的瓶頸就是調用「contains」 – 2013-04-08 13:21:30

有兩種可能性，我能想到的：

你有足夠的少量數據元素的一個線性搜索比散加比較快的查找。
您正在使用相同的contains函數來查找unordered_set中的元素，而不是使用成員函數find。

來源

2013-04-08 13:16:32

因爲我只關心返回一個獨特的Body *集合，所以我沒有在unordered_set上使用「contains」或「find」。我只是用插件期待它只填充獨特的元素。 – 2013-04-08 13:22:38

-2

這裏是你的STD文檔中查找：

「unordered_set容器是比集集裝箱快了他們的密鑰才能訪問單個元素，但它們通常用於範圍迭代效率較低，通過的子集，其元素「。

好，因爲find方法最終會遍歷了相當數量的元素可能這就是原因...

也許，如果你已經使用了costum哈希函數，你應該改進它，使之更快...只有我能想到的東西...

來源

2013-04-08 13:22:42 Mppl

但是，當再次使用'unordered_map'時，絕對不需要'std :: find'（並且OP確認沒有做這種愚蠢的錯誤）。 – 2013-04-08 13:27:01

*「如果你真的需要更好的性能，我能想到的唯一數據容器就是某種散列表」* - 呃......你的意思是......像一個'std :: unordered_set'？ – 2013-04-08 13:34:22

是的，你是對的......無序集確實是一個哈希表......我的壞。 – Mppl 2013-04-08 13:44:23

如果重複的身體數量與其他人相比不是那麼高，一個選項可能是將所有身體推入矢量中，然後刪除重複數據。但是這需要std::sort，然後是erase(std::unique, end)。

但是值得一試，考慮到你的矢量似乎超過了std::unordered_set，它不具有相同的內存地址和像std::vector一樣的微不足道的訪問。

來源

2013-04-08 13:31:03

我試過了，但性能比我目前的要慢。 – 2013-04-08 13:32:41

我猜downvote將保持不解釋？ – 2013-04-15 13:22:29

我不確定我是否正確理解問題，但似乎std::vector/std::find上的查找速度會較慢，但迭代速度可能會快於std::unordered_set。如果是這種情況，並且您不受內存限制的限制，則可以混合使用兩種方法：

同時維護包含元素的std::unordered_set和std::vector。在std::unordered_set內查找以確定元素是否已經存在，如果不存在，則將其添加到兩個容器中。最後遍歷std::vector。

請注意，您可以向兩個容器提供關於它們將包含的「預計」數量的元素的提示，這將減少內存分配/重新散列的次數。

來源

2013-04-08 13:40:55

我想'std :: unique_set'應該是一個'std :: unordered_set'？除此之外，我不認爲他需要遍歷'std :: unordered_set'，至少不需要在代碼片段中（以及他所描述的並且想要加速的代碼片段）。它只是'std :: vector + std :: find' vs'std :: unordered_set :: insert'，所以在你的情況下，他會有像現有的'std :: unordered_set'解決方案*和*開銷一個向量插入。 – 2013-04-08 13:45:56

@ChristianRau：是的，「無序」（需要馬上注入咖啡因！） – 2013-04-08 13:47:46

std :: vector比std :: unordered_set更快嗎？

回答

相關問題