3

この関数を最適化したかった前の質問:

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ジャンプを防ぐために に置き換えることができるとコメントしました。トリックが間違っていて、ユーザーはコメントを削除しましたが、実際にそれを行う方法があるかどうか疑問に思っています。

4

3 に答える 3

2

以下を使用しない理由: !(s1i == s2[j])または(s1i != s2[j])bool から int への変換が暗黙的であるため

于 2013-04-22T11:41:34.583 に答える