22

私は2つの機能の速度を見つけることにしました：

  • strcmp-string.hで定義されている標準の比較関数
  • xstrcmp-私が作成したのと同じパラメーターを持ち、同じことを行う関数。

これが私のxstrcmp関数です：

int xstrlen(char *str)
{
    int i;
    for(i=0;;i++)
    {
        if(str[i]=='\0')
            break;
    }
    return i;
}

int xstrcmp(char *str1, char *str2)
{
    int i, k;
    if(xstrlen(str1)!=xstrlen(str2))
        return -1;
    k=xstrlen(str1)-1;
    for(i=0;i<=k;i++)
    {
        if(str1[i]!=str2[i])
            return -1;
    }
    return 0;
}

すべてをユーザー定義にしたいので、strlenに依存したくありませんでした。

それで、私は結果を見つけました。strcmpは1ミリ秒あたり364回の比較を行い、私のxstrcmpは1ミリ秒あたりわずか20回の比較を行いました（少なくとも私のコンピューターでは！）

なぜそうなのか誰にも分かりますか？xstrcmp関数はそれ自体を非常に高速にするために何をしますか？

4

6 に答える 6

35 
if(xstrlen(str1)!=xstrlen(str2))    //computing length of str1
    return -1;                      
k=xstrlen(str1)-1;                  //computing length of str1 AGAIN!

あなたはstr1TWICEの長さを計算しています。これが、関数がゲームに負ける理由の1つです。

また、の実装はxstrcmp、（ほとんどの）標準ライブラリで定義されているものと比較して非常に単純です。たとえば、xstrcmp一度に1バイトを比較しますが、実際には、適切なアラインメントを利用して一度に複数のバイトを比較したり、実際の比較の前にメモリブロックをアラインメントするための前処理をほとんど行うことができません。

于 2012-07-17T12:34:19.760 に答える
27

strcmp およびその他のライブラリ ルーチンは、経験豊富なエンジニアによってアセンブリまたは特殊な C コードで記述され、さまざまな手法が使用されます。

たとえば、アセンブリの実装では、一度に 4 バイトをレジスタに読み込み、そのレジスタを (32 ビット整数として) 他の文字列の 4 バイトと比較します。一部のマシンでは、アセンブリの実装によって 8 バイト以上が読み込まれる場合があります。比較の結果、バイトが等しいことが示された場合、実装は次の 4 バイトに進みます。比較によってバイトが等しくないことが示された場合、実装は停止します。

この単純な最適化でも、対処すべき問題がいくつかあります。文字列アドレスが 4 バイトの倍数でない場合、プロセッサには 4 バイトをロードする命令がない可能性があります (多くのプロセッサでは、4 バイトの倍数にアラインされたアドレスを使用するために 4 バイトのロードが必要です)。プロセッサによっては、実装で低速の非整列ロードを使用するか、整列ロードを実行してレジスタ内のバイトをシフトし、比較対象のバイトを整列させる特殊なコードを記述する必要がある場合があります。

実装が一度に 4 バイトをロードする場合、それらのバイトがセグメント フォールト (読み取り不能なアドレスをロードしようとしたためエラー) を引き起こす可能性がある場合、終端の null 文字を超えてバイトをロードしないようにする必要があります。

4 バイトに終端のヌル文字が含まれている場合、2 つの文字列で現在の 4 バイトが等しい場合でも、実装はそれを検出し、それ以上のバイトの比較を続行しないようにする必要があります。

これらの問題の多くは、詳細なアセンブリ命令を必要とし、使用される命令を正確に制御する必要はありません。使用される正確な手法は、プロセッサ モデルごとに異なり、アーキテクチャごとに大きく異なります。

于 2012-07-17T12:47:04.643 に答える
5

strlenのより高速な実装：

//Return difference in addresses - 1 as we don't count null terminator in strlen.
int xstrlen(char *str)
{
    char* ptr = str;
    while (*str++);
    return str - ptr - 1;
}

//Pretty nifty strcmp from here:
//http://vijayinterviewquestions.blogspot.com/2007/07/implement-strcmpstr1-str2-function.html
int mystrcmp(const char *s1, const char *s2)
{
    while (*s1==*s2)
    {
        if(*s1=='\0')
            return(0);
        ++s1;
        ++s2;
    }
    return(*s1-*s2);
}

時間があれば、後でもう一方をやります。また、これらのほとんどはアセンブリ言語で行われるか、他の最適化された手段を使用して行われることに注意してください。これは、記述できる最高のSrightC実装よりも高速です。

于 2012-07-17T12:48:17.047 に答える
4

コードの問題（すでに指摘されています）を除けば、少なくともgcc-C-libsでは、メモリアクセスパターンが高度に最適化されているため、ほとんどの場合、 str-mem関数と-関数はわずかに高速です。

SOに関するトピックについてはすでにいくつかの議論がありました。

于 2012-07-17T12:34:26.927 に答える
2

これを試して：

int xstrlen(const char* s){
  const char* s0 = s;
  while(*s) s++;
  return(s - s0);
}

int xstrcmp(const char* a, const char* b){
  while(*a && *a==*b){a++; b++;}
  return *a - *b;
}

これはおそらく、ループ展開によって高速化される可能性があります。

于 2012-07-17T12:50:04.100 に答える
1

1. アルゴリズム

strcmp の実装には、より優れたアルゴリズムがある可能性があります。strlen を呼び出す必要はまったくありません。strlen を呼び出すたびに、文字列全体が繰り返し処理されます。シンプルだが効果的な実装をオンラインで見つけることができます。おそらく、次のような場所から始めましょう。

// Adapted from http://vijayinterviewquestions.blogspot.co.uk
int xstrcmp(const char *s1, const char *s2)
{
  for (;*s1==*s2;++s1,++s2)
  {
    if(*s1=='\0') return(0);
  }
  return(*s1-*s2);
}

これですべてができるわけではありませんが、ほとんどの場合、シンプルで機能するはずです。

2. コンパイラの最適化

ばかげた質問ですが、コンパイル時にすべての最適化スイッチをオンにしたことを確認してください。

3. より洗練された最適化

ライブラリを作成する人は、4 バイトまたは 8 バイトの int を一度にロードして比較し、全体が一致する場合は個々のバイトのみを比較するなど、より高度な手法を使用することがよくあります。このケースに何が適切かを知るには専門家である必要がありますが、スタック オーバーフローの最も効率的な実装について議論している人々を見つけることができます (リンク?)

一部のプラットフォーム用の一部の標準ライブラリ関数は、コンパイラが検出できるよりも効率的な実装があることをコーダーが認識できる場合、アセンブリで手書きされる場合があります。現在、これはますますまれになっていますが、一部の組み込みシステムでは一般的かもしれません。

4. 標準ライブラリを使用したリンカの「ごまかし」

一部の標準ライブラリ関数では、リンカーは関数の特定の内部構造について詳しく知るように設計されているため、コードで関数を呼び出すよりも少ないオーバーヘッドでプログラムにそれらを呼び出させることができる場合があります (リンク?)この場合は当てはまりますが、おそらく当てはまらないでしょうが、それはあなたが考えなければならない種類のものです.

5. OK、OK、それはわかりましたが、独自の strcmp を実装する必要があるのはいつですか?

私の頭の上から、これを行う唯一の理由は次のとおりです。

  • あなたは方法を学びたいです。これは正当な理由です。
  • 十分な標準ライブラリがないプラットフォーム向けに書いています。これはほとんどありません。
  • 文字列の比較は、コードの重大なボトルネックであることが測定されており、文字列に固有の何かを知っているため、単純なアルゴリズムよりも効率的に比較できることを意味します。(たとえば、すべての文字列が 8 バイト アラインで割り当てられているか、すべての文字列に N バイトのプレフィックスが割り当てられています。) これは、非常にありそうもないことです。

6. でも…

OK、なぜ strlen に頼るのを避けたいのですか? コードサイズが気になりませんか？コードまたは実行可能ファイルの移植性について?

正当な理由がある場合は、別の質問を開いてください。より具体的な回答があるかもしれません。明らかな何かが欠けている場合は申し訳ありませんが、特に改善したいことがない限り、通常は標準ライブラリに依存する方がはるかに優れています。

于 2012-07-18T12:23:03.967 に答える