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更快吗？

回答

相关问题