10

在我的自定义物理引擎中，最大的瓶颈是从空间分区（2D 网格）中获取所有物体的方法，并返回一个只包含指向 body 的唯一指针的集合。

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;
}

使用分析器表明瓶颈在于“包含”方法。

显然， anstd::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;
}

为什么“正确”的容器比 a 慢std::vector？

有什么办法可以进一步加快这种方法的速度吗？

4

5 回答 5

5

我能想到的有两种可能：

  1. 您的数据元素数量足够少，因此线性搜索比哈希加比较查找更快。
  2. 您正在使用相同的contains函数来查找 中的元素unordered_set，而不是使用成员函数find。
于 2013-04-08T13:16:32.903 回答
1

如果重复实体的数量与其他实体相比没有那么高，一种选择可能是将所有实体推入向量中，然后删除重复实体。但这需要 astd::sort后跟一个erase(std::unique, end).

但它可能值得一试，考虑到你的向量似乎胜过 a std::unordered_set，它没有像 a 一样的内存位置和微不足道的访问std::vector。

于 2013-04-08T13:31:03.850 回答
0

我不确定我是否正确理解了这个问题，但似乎std::vector/上的查找会更慢std::find，但迭代可能比 with 更快std::unordered_set。如果是这种情况，并且您不受内存限制的限制，则可以混合使用两种方法：

保持 astd::unordered_set和 astd::vector与元素。在 内部查找std::unordered_set以确定元素是否已经存在，如果不存在，则将其添加到两个容器中。最后迭代std::vector.

请注意，您可以向两个容器提供有关它们将包含的“预期”元素数量的提示，这将减少内存分配/重新散列的数量。

于 2013-04-08T13:40:55.383 回答
0

我遇到了一个类似的问题，其中线性搜索比哈希加比较查找更快。（支持马克的第一个答案）。

我尝试使用 BFS 来改善网格的 CPU 体素化。std::unordered_set用于标记访问的体素。但是，unordered_set它比线性迭代空间慢 100%。通过轮廓比较，我发现如果活动体素与所有访问体素的比率高于3%. 否则，BFS withunordered_set更好。

于 2018-07-09T20:39:06.037 回答
-2

这是您在 std 文档中找到的内容：

“unordered_set 容器比 set 容器更快地通过它们的键访问单个元素，尽管它们通常对于通过其元素的子集进行范围迭代的效率较低。”

好吧，因为 find 方法最终会遍历相当多的元素，这可能就是原因......

也许如果你使用了一个 costum 散列函数，你应该改进它以使其更快......只有我能想到的......

于 2013-04-08T13:22:42.443 回答