时间戳

首页 > 解决方案 > C++中的递归函数和性能

c++ - C++中的递归函数和性能

问题描述

我是 C++ 新手，如果有人帮助我验证以下功能或帮助我改进它，我将不胜感激。

void RecursiveKnn(std::set<PointId> &refSet, const PointId &id, const KD3Index &kid, int const lvl)
{
    if (refSet.find(id) == refSet.end())
        refSet.insert(id);

    if (lvl < m_knn)
    {
        auto ids = kid.neighbors(id, 7);
        for (auto x : ids)
        {
            if (x == id)
                continue;
            RecursiveKnn(refSet, x, kid, lvl+1);
        }
    }
}

我编写了一个递归函数来运行和生成一组分层对象。基本上，从一个对象开始，获取下一个/附近的对象等等，以达到下一个级别。除此之外，我还想避免重复。级别限制在 3 - 4 级，预计不会再进一步​​。

这个函数被称为数百万次，并且需要永远运行。如果有人可以提出任何改进建议，我将不胜感激。在我的脑海中，我确信std::set使用的数据结构不正确，但我不知道该使用什么。

编辑：原因，我发现功能有性能问题是这样的。起初我有一个带有 3 个嵌套 for 循环的函数。在合理的时间内工作。当我将其更改为递归函数时，该过程没有完成一个多小时。

标签： c++performance

解决方案

如果没有更多信息，我的猜测是多个 PointId 可以是具有相同 PointId 的邻居，即使存在父/子关系也是如此。

换句话说，此代码在有向无环图上执行深度优先搜索，但没有像典型的深度优先搜索那样检查重访。这意味着您将多次探索相同的节点，这是非常低效的。

改变

if (refSet.find(id) == refSet.end())
    refSet.insert(id);

至

if (refSet.find(id) != refSet.end())
    return;
refSet.insert(id);

此外，您应该使用 std::unordered_set 而不是 std::set ，但如果上述情况属实，那么这是一个较小的问题。

推荐阅读