c++ - 我可以优化具有 3 个 for 循环和 4 个 if 的代码吗？

Question

我发了一个帖子

here在那里我询问了如何在 3 维空间中创建立方体素节点的 26 个邻居。我得到了一个很好的答案并实现了它。

为此我添加了一些 MIN MAX 位置检查。

我想知道是否有办法，与 3 个 for 循环和 4 个(如果使用)相关，来缩短这段代码的执行时间。我在另一篇文章中读到，当使用 while 循环时速度更快，但它是在一篇非特定语言的文章中。

这是真的吗？如果是的话，你能不能在我的代码中帮我解决这个问题，因为我很幸运？有没有一种方法可以递归地实现它并使其更快？

这是我的代码:

...
std::vector<Pos> Create26Neighbor(Pos somePos, double resol) 
{
    std::vector <Pos> vect1;
    Pos  m_MinPos(0.0,0.0,0.0);
    Pos  m_MaxPos(5.0,4.0,5.0);

    for (double dz = somePos.m_pPos[2] - resol; dz <= somePos.m_pPos[2] + resol; dz+=resol)
    {
        if (dz>m_MinPos.m_pPos[2] && dz<m_MaxPos.m_pPos[2])
        {
            for (double dy = someCPos.m_pPos[1] - resol; dy <= someCPos.m_pPos[1] + resol; dy+=resol)
            {
                if (dy>m_MinPos.m_pPos[1] && dy<m_MaxPos.m_pPos[1])
                {
                    for (double dx = somePos.m_pPos[0] - resol; dx <= somePos.m_pPos[0] + resol; dx+=resol)
                    {
                        if (dx>m_MinPos.m_pPos[0] && dx<m_MaxPos.m_pPos[0])
                        {
                            // all 27
                            if ((dx != somePos.m_pPos[0]) || (dy != somePos.m_pPos[1]) || (dz != somePos.m_pPos[2]))
                            {
                                Pos tempPos(dx,dy,dz);
                                vect1.push_back(tempPos);
                            }
                        }
                    }
                }
            }
        }
    }
    return vect1;
}
....

Answer 1

首先，去掉 if 语句。不需要他们。您可以将它们合并到循环条件中。其次，避免每次迭代都重新计算循环条件。是的，编译器可能会优化它，但它通常对浮点优化非常保守(并且它可能会以不同的方式处理从内存读取的 fp 值和从寄存器读取的 fp 值，这意味着它不能从循环条件中消除数组查找)，因此通常最好手动进行简单的优化:

std::vector<Pos> Create26Neighbor(Pos somePos, double resol) 
{
    std::vector <Pos> vect1(27); // Initialize the vector with the correct size.
    Pos  m_MinPos(0.0,0.0,0.0);
    Pos  m_MaxPos(5.0,4.0,5.0);

    double minz = std::max(somePos.m_pPos[2] - resol, m_MinPos.m_pPos[2]);
    double maxz = std::min(somePos.m_pPos[2] + resol, m_MaxPos.m_pPos[2];
    int i = 0;
    for (double dz = min; dz <= max; dz+=resol)
    {
        double miny = std::max(somePos.m_pPos[1] - resol, m_MinPos.m_pPos[1]);
        double maxy = std::min(somePos.m_pPos[1] + resol, m_MaxPos.m_pPos[1];
        for (double dy = miny; dy <= maxy; dy+=resol)
        {
            double minx = std::max(somePos.m_pPos[0] - resol, m_MinPos.m_pPos[0]);
            double maxx = std::min(somePos.m_pPos[0] + resol, m_MaxPos.m_pPos[0];

            for (double dx = minx; dx <= maxx; dx+=resol)
            {
                ++i;
                // If we're not at the center, just use 'i' as index. Otherwise use i+1
                int idx = (dx != somePos.m_pPos[0] || dy != somePos.m_pPos[1] || dz != somePos.m_pPos[2]) ? i : i+1;
                vec1[idx] = Pos(dx, dy, dz); // Construct Pos on the spot, *might* save you a copy, compared to initilizing it, storing it as a local variable, and then copying it into the vector.
              }
        }
    }
    return vect1;
}

我要考虑的最后一点是内部 if 语句。紧密循环中的分支机构可能比您预期的成本更高。我可以想出很多方法来消除它:

• 正如我在代码中描绘的那样，可以诱导 ?: 运算符为中心值计算不同的 vector 索引(因此它被写入下一个 vector 元素，因此在下一次迭代中再次被覆盖)。这将消除分支，但总体上可能会或可能不会更快。
• 拆分循环，以便在“resol”值之前和之后有单独的循环。这有点尴尬，有很多更小的循环，而且整体效率可能较低。但它会消除内部 if 语句，因此它也可能更快。
• 允许将中心点添加到 vector 中，之后要么忽略它，要么在循环之后将其删除(这是一个有点昂贵的操作，可能会或可能不会得到返回。如果你这样做可能会更便宜使用双端队列而不是 vector 。

并确保编译器展开内部循环。手动展开它也可能有所帮助。

最后，很大程度上取决于 Pos 的定义方式。

请注意，我建议的大部分内容都符合“它可能不会更快，但是......”。您必须不断分析和基准化您所做的每项更改，以确保您确实在提高性能。

根据您愿意走多远，您可以将所有内容合并到一个循环中(在整数上运行)，并在每次迭代中即时计算 Pos 坐标。