Sweet Snippet 之 指数函数优化
本文简述了一些关于指数函数优化的测试结论
自己平日工作中需要使用指数函数(pow)的情况不多,偶有遇到,可能也就是调用一下标准库函数了:
// return x^y
float pow_std(float x, float y)
{
return std::pow(x, y);
}
后来想到在自己的使用场景中,其实指数参数(y)都仅会是正整数罢了,遂尔想到可以简单优化(特化)一下,于是有了下面的代码:
// return x^y(y is unsigned int)
float pow_uint_mul(float x, unsigned int y)
{
float result = 1.0f;
for (unsigned int i = 0; i < y; ++i)
{
result *= x;
}
return result;
}
简单测了一下性能,确实是比标准实现快了不少,优化故事本来到此就可以结束了,没想自己还是"本能"的从遍历联想到了分治,于是又有了下面的代码:
// return x^y(y is unsigned int)
float pow_uint_recur(float x, unsigned int y)
{
if (y == 0)
{
return 1.0f;
}
else
{
const bool is_odd = ((y & 1) != 0);
if (is_odd)
{
const auto result = pow_uint_recur(x, (y - 1) / 2);
return result * result * x;
}
else
{
const auto result = pow_uint_recur(x, y / 2);
return result * result;
}
}
}
可惜上述代码虽然做了分治处理,但是递归(函数调用)成本一眼望去还是不容小觑,又简单测试了一把,果不其然,代码效率还不如遍历版本,于是最后又有了一个分治的迭代版本:
// return x^y(y is unsigned int)
float pow_uint_iter(float x, unsigned int y)
{
if (y == 0)
{
return 1.0f;
}
else
{
float result = x;
unsigned int base_pow = 1;
while (base_pow * 2 < y)
{
result *= result;
base_pow *= 2;
}
for (auto i = base_pow; i < y; ++i)
{
result *= x;
}
return result;
}
}
最后测试了一下,诚然,上述版本确实在效率上优于遍历版本了,但是相对的,实现上也更复杂,维护性应该也是几个版本中最差的,综合来看,除非你的使用场景特殊(譬如指数参数很大),否则我还是更推荐上面的遍历版本(pow_uint_mul) ~
