我可以优化具有3个for循环和4个ifs的代码吗？

Question

我又发了一个帖子

在这里,我问如何在三维空间中创建一个立方体素节点的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值与从寄存器中读取的值不同,这意味着它无法从循环中消除数组查找条件),所以通常最好手动进行简单的优化:

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语句.紧密循环中的分支可能比您预期的更昂贵.我可以想出一些消除它的方法:

• 正如我在代码中描绘的那样,可以诱导？:运算符计算中心值的不同向量索引(因此它被写入下一个向量元素,因此在下一次迭代时会再次被覆盖).这将消除分支,但总体上可能会或可能不会更快.
• 拆分循环,以便在'resol'值之前和之后有单独的循环.这有点尴尬,有很多较小的循环,整体效率可能较低.但它会消除内部的if语句,所以它也可能更快.
• 允许将中心点添加到向量中,然后忽略它,或者在循环之后将其删除(这将是一个有点昂贵的操作,可能会或可能不会得到回报.如果你使用deque可能会更便宜而不是矢量.

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

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

请注意,我建议的大部分内容都符合"它可能不会更快,但......".您必须不断地对每个变更进行分析和基准测试,以确保您实际上提高了性能.

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