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

Question

我是 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 循环的函数。在合理的时间内工作。当我将其更改为递归函数时，该过程在一个多小时内没有完成。

Answer 1

在没有更多信息的情况下，我的猜测是多个 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 但如果上述情况属实，则不必担心。