关于上一个问题我想优化这个函数:
static
lvh_distance levenshtein_distance( const std::string & s1, const std::string & s2 )
{
const size_t len1 = s1.size(), len2 = s2.size();
std::vector<unsigned int> col( len2+1 ), prevCol( len2+1 );
const size_t prevColSize = prevCol.size();
for( unsigned int i = 0; i < prevColSize; i++ )
prevCol[i] = i;
for( unsigned int i = 0, j; i < len1; ++i )
{
col[0] = i+1;
const char s1i = s1[i];
for( j = 0; j < len2; ++j )
{
const auto minPrev = 1 + std::min( col[j], prevCol[1 + j] );
col[j+1] = std::min( minPrev, prevCol[j] + ( s1i == s2[j] ? 0 : 1 ) );
}
col.swap( prevCol );
}
return prevCol[len2];
}
一位用户评论说我可以将
s1i == s2[j] ? 0 : 1
替换为 ((s1i - s2[j]) & 0x80) >> 7
以防止条件跳转。这个技巧是错误的,用户删除了他的评论,但我想知道是否真的有办法做到这一点。
假设代码
s1i == s2[j] ? 0 : 1
确实给了你一个分支操作,你真的想避免,你可以简单地尝试以下操作:
!(s1i == s2[j])
这应该会产生相同的效果,并且可以帮助编译器删除分支。或者,你可以颠倒逻辑并写
s1i != s2[j]
与此类优化一样,永远无法保证这实际上会达到您希望的结果。优化器做了很多聪明的事情,试图预测它们对你的技巧将如何反应通常是很困难的。因此,即使在最好的情况下,您所能做的就是尝试不同的解决方案并比较生成的二进制代码。
为什么不使用以下内容:
!(s1i == s2[j])
或(s1i != s2[j])
,因为 bool 到 int 的转换是隐式的
不是一个实际的答案,而是解决一个难题。
创建一个数组
one_or_zero[UCHAR_MAX+1]
用1填充它,然后one_or_zero[0] = 0;
prevCol[j] + one_or_zero[s1i^s2[j]])
s1i==s2[j]
上的值为 0,否则将被添加到 prevCol[j]
上