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

Question

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

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慢？

我有没有办法进一步加速这个方法？

- Vittorio Romeo

---

性能分析结果仅适用于“包含”操作？请记住，搜索集合可能更快，但插入速度比向量慢。 - user995502

我猜你没有犯这样的错误，但是为了确保确实如此，你在尝试使用std::unordered_map时没有使用std::find，对吗？ - Christian Rau

@ChristianRau 不，我已经删除了“包含”部分。 - Vittorio Romeo

@Vee 是的，这就是我在向量版本中所说的，“find”可能是瓶颈。然而，在设置版本中，“insertion”可能会成为瓶颈。 - user995502

虽然我上面评论中的问题可能一开始有点愚蠢，但似乎许多回答者对于在 std::unordered_set 上进行一些可能的迭代还很困惑。因此，如果您可以在现有的 std::vector 代码旁边包含您的 std::unordered_set 解决方案，这可能有助于澄清事情。 - Christian Rau

Answer 1

我能想到两个可能性：

1. 数据元素数量较少，线性搜索比哈希加比较查找更快。
2. 您在查找unordered_set中的元素时使用了相同的contains函数，而没有使用成员函数find。

- Mark B

---

我只关心返回一个唯一Body*集合，因此我没有在unordered_set中使用"contains"或"find"。我只使用了insert函数，并期望它只包含唯一的元素。 - Vittorio Romeo

Answer 2

如果与其他元素相比，重复体的数量并不算太高，那么一个选项可能是将所有体推入向量，然后删除重复项。但这需要进行std :: sort，然后进行erase(std::unique, end)。

但考虑到您的向量似乎比std :: unordered_set更好，它没有像std :: vector那样的内存局部性和微不足道的访问。

- Christian Rau

---

我尝试了一下，但性能比我目前拥有的要慢。 - Vittorio Romeo

Answer 3

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

维护一个包含元素的std::unordered_set和一个std::vector。在std::unordered_set中查找以确定元素是否已经存在，如果不存在，则将其添加到两个容器中。最后遍历std::vector。

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

- David Rodríguez - dribeas

---

我猜std::unique_set应该是一个std::unordered_set？除此之外，我认为他没有必要迭代std::unordered_set，至少在问题中的代码片段（以及他进行分析并想要加速的代码片段）中不需要。这只是std::vector+std::find与std::unordered_set::insert的比较，所以在你的情况下，他将具有与现有的std::unordered_set解决方案相同的开销，和向量插入的开销。 - Christian Rau

@ChristianRau：是的，unordered（需要立即加入咖啡因！） - David Rodríguez - dribeas

Answer 4

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

我尝试使用BFS来改进网格的CPU体素化。使用std::unordered_set标记已访问的体素。然而，unordered_set比线性迭代空间慢100%。通过分析比较，我发现如果活动体素占所有访问体素的比率高于3%，则线性搜索更快。否则，使用unordered_set的BFS更好。

- Tiantian Xie

Answer 5

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

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

由于find方法最终将循环遍历大量元素，这可能就是原因...

也许如果您使用了自定义哈希函数，您应该改进它以使其更快...这是我能想到的唯一一件事...

- Mppl

---

然而，当使用 unordered_map 时，根本没有必要使用 std::find（并且 OP 已经确认没有犯这种愚蠢的错误）。 - Christian Rau

如果你真的需要更好的性能，我所能想到的唯一数据容器就是某种哈希表。- 呃...你的意思是...像std::unordered_set这样的吗？ - Christian Rau

是的，你说得对... 无序集合确实是一个哈希表... 我错了。 - Mppl