优化数学指标计算函数

Question

我做了一个函数，它计算由XY点构成的多边形上任意点所属的点的索引。

这是一个可视化的表示：

这就是我做的功能：

stock GetNodeIndexFromPolygonIndex(polygonid,Polygon_Size)
{
    new polid = (polygonid - (polygonid % 2));
    new mid = Polygon_Size/2;
    if(polid > mid)
    {
        polid /= 2;
        return (mid - (++polid));
    }
    else
    {
        polid /= 2;
        if(polid == 0)
        {
            return 0;
          }
        return --polid;
    }
}

这里有什么我可以优化的吗？在单线程应用程序上一次运行最坏的情况下，这个函数将被调用2000次。我希望这是尽可能最佳的。已经开始了吗？

Answer 1

首先，我对典当一无所知。

它有侧写器吗？可以使用任何分析器吗？如果是的话，就用它吧。

如果没有，至少编写一些测试单元来测量执行时间。

我将假设典型的语言元素。我将假设polygonid > 0和Polygon_Size > 0，因为我不知道(也没有在短时间内发现) /和%对负数的行为。

据我所知，在编译器和执行之间有一个虚拟机。这使得事情变得更加复杂，但是，我们将假设那里没有什么特别的事情发生。

一些优化可能不会改变什么，因为编译器已经做了。我无法预测或测试它。

话虽如此，我还是会一行行地选择。我不知道你是否能改变算法，因为像Cygal一样，我不明白确切的目的。

new polid = (polygonid - (polygonid % 2));

这使得polid成为下一个最小的偶数？%相当昂贵，您可以使用polygonid & 1代替polygonid % 2或new polid = polygonid & (max_value - 1)来设置所有位，但最后一位设置为零。max_value -1应预先计算.

new mid = Polygon_Size/2;

更改为：new mid = Polygon_Size >> 1 --这很可能是编译器完成的，但我们不知道，所以让我们试试吧。

polid /= 2;

这是在两个分支中计算的。它可以帮助在分支之前做到这一点：

new polid_half = polid >> 1;
...

return (mid - (++polid));

这取决于语言细节。可能是++polid作为增量前操作符加载polid，将其更新为一个，并将polid存储回。我们不打算使用修改的polid，所以我们可以尝试return (mid - polid + 1)，假设++polid与普通的+相比不是一些神奇的快速特殊指令。

    if(polid == 0)
    {
        return 0;
    }

只有在多边形为0或1时才会发生这种情况。如果经常发生这种情况，您应该在开始时立即返回，保存其余的：

if (polygonid < 2 )  //assuming polygonid > 0
    return 0;

并移除其他分支中的支票。

    return --polid;

和以前一样，return polid - 1可能会更好

根据分支预测处理的不同，最好只有一个返回点，而不是每个分支中的一个。您可以引入一个返回值，并根据当前逻辑设置它。

我会尝试一次又一次的改变，并分析每一步。所有这些都可以是：

stock GetNodeIndexFromPolygonIndex(polygonid,Polygon_Size)
{
    if (polygonid < 2 )  //assuming polygonid > 0
        return 0;
    new result = 0;
    new polid = polygonid & (max_value - 1); //polid is a bad name
    new polid_half = polid >> 1;
    new mid = Polygon_Size >> 1;
    if(polid > mid)
        result = mid - polid_half + 1;
    else
        result = polid_half - 1;
    return result;
}