3

C++ STL 文字列の部分文字列を検索するための find メソッドが、文字列を単純にO(n)渡すよりも高速である理由に少しショックを受けました。ここに 2 つの異なる関数があります: で見つかった 2 番目の関数が最初の関数 (十分に最適化されている) よりも速いのはなぜstr1ですかstr2? 最初の関数がわずかに異なるタスクを実行することはわかっていますが、それでも と を渡すだけでstr1ありstr2 (O(n))、2 番目の関数はO(n^2)で検索str1する必要がある場合がありますstr2。ほんとに？なんで？皆さん、何か考えはありますか？前もって感謝します。

PS関数はより大きなプロジェクトの一部です。私のコードでは、2 つの文字列を比較するために何度も呼び出されます。2 番目の関数を使用すると、コード全体の実行時間はほぼ半分 (135 秒 VS 235 秒) になります。

bool Is_Included1(string str1, string str2)
{
    size_t i,s;
    s=str1.size();
    if (s<=str2.size())
    {
        for (i=0;i<s;i++)
            if (str1[i]!=str2[i])
                return false;
        return true;
    }
    return false;
}


bool Is_Included2(string str1, string str2)
{
    size_t i;
    if (str1.size()<=str2.size())
    {
        i=str2.find(str1);
        if (i==0)
            return true;
        else
            return false;
    }
    return false;
}
4

3 に答える 3

2

違いは、配列アクセサー[i]とポインター演算です。

str1[i]との使用str2[i]が主な違いです。これらのアクセサーは通常、基になるポインター演算を使用するだけでなく、最適化も行いません。const char* c1 = str1.cstr()そして、++c1; ++c2それらを反復処理します (これは、STL 実装が内部で行うことです)。

一般に、基盤となるハードウェアは、配列よりもポインターを反復処理する方が優れています。場合によっては、コンパイラは配列演算の代わりにポインター演算を使用するようにループを最適化できますがstd::string、複雑なオーバーロードされた の実装を使用するためoperator[]、基本的に常にarrayBase+offsetループの各反復で実行することになります。

これを試して：

bool Is_Included1(string str1, string str2)
{
    size_t i,s;
    s=str1.size();
    if (s<=str2.size())
    {
        const char* c1 = str1.c_str();
        const char* c2 = str2.c_str();
        for (i=0;i<s;i++, c1++, c2++)
            if (*c1!=*c2)
                return false;
        return true;
    }
    return false;
}

STL リファレンス実装と比較してみてください。

int i（STLバージョンは、さらに最適化して完全に使用を削除できるため、おそらくまだ少し高速であることに注意してください）

于 2013-05-10T12:37:35.080 に答える
2

GCC 4.7.2 での実装を追跡しました。その複雑さは O(nm) で、n、m は 2 つの文字列の長さです。

n.size() が m.size() より小さいと仮定すると、m の可能な開始点 i ごとに、最初に n[0] と m[i] (traits_type::eq) を比較し、次に traits_type::compare を呼び出します。これは実際に __builtin_memcmp() を実行します。

これは正確な実装ではありませんが、アルゴリズムを示しています。

for (size_t i=0; i<m.size(); ++i) {
    if (traits_type::eq(n[0], m[i]) &&
        traits_type::compare(n[1], m[i+1], n.size()-1) == 0) {
            return i;
    }
}
return -1;

アルゴリズムの時間順が悪いのは、__builtin_memcmp() が文字を 1 つずつ比較しないため、予想よりも高速になるためだと思います。

ちなみに、関数を頻繁に呼び出す場合は、値渡しではなく、2 つの文字列の const 参照を渡す必要があります。これにより、不要なコピーが発生します。

次のように：

bool Is_Included2(const string& str1, const string& str2)
{
    if (str1.size() > str2.size()) return false;
    return str2.find(str1) == 0;
}
于 2013-05-10T12:26:11.273 に答える