3

特定の文字列内で特定の文字が出現する回数をカウントする非常に単純な関数を作成しています。私には機能がありますが、これを行うためのより効率的な方法または好ましい方法があるかどうか疑問に思いました。

関数は次のとおりです。

size_t strchroc(const char *str, const char ch)
{ 
    int c = 0, i = 0;

    while(str[i]) if(str[i++] == ch) c++;
    return c;
}

私は個人的に、このコードをより効率的にする方法を考えることができません。そして、この機能をより効率的にする方法を誰かが知っているかどうか（学習のためだけに）疑問に思っていました。

（速度と最小限のリソースの使用という意味で効率的です）。

4

6 に答える 6

5

まず第一に、関数が本当に時間に敏感でない限り、過度に最適化しようとしないでください。提供されたものを使用してください。正確性を確認するのは簡単で、スマートになろうとはしません。

関数を本当に高速にする必要がある場合は、さらに最適化する方法がたくさんあります。多くの、本当に多くの方法。それらのいくつかは、文字列の特定のメモリ レイアウトを期待または想定しています (たとえば、文字列は単語境界に割り当てられ、割り当ては常に単語境界までパディングされます)。したがって、アルゴリズムはプロセッサ、コンパイラ、およびメモリ アロケータの一部の組み合わせで機能し、他の組み合わせでは惨めに失敗する可能性があるため、注意が必要です。

念のために、文字カウンターを高速化するいくつかの可能な方法をリストします。

  • 文字列を単語 (32 ビットまたは 64 ビット整数) ずつ読み取ります。L1キャッシングと投機的/順不同の実行のおかげで、必ずしも多くの助けにはなりません. これには、最後のワードのループ終了調整が必要です (NUL ターミネータの後のバイトのカウントミス)。ワード アラインされ、パディングされたメモリ アロケータでのみ使用します。
  • 条件を削除し、代わりに (配列への) すべての文字のカウントを計算し、必要な文字のカウントを返します。(これにより条件が削除され、文字列の長さが事前にわかっている場合は、優れたループ展開が可能になり、条件分岐の 1 つのポイントが削除されます。)
  • 文字列の長さが事前にわかっている場合 (別の場所で計算されている)、それを使用してループを展開できます。または、for ループとして記述し、適切な #pragma とコンパイラ オプションを適用して、コンパイラにループ展開を行わせるようにすることをお勧めします。
  • ルーチンをアセンブラで記述します。この方法に進む前に、すべてのコンパイラーの最適化を開始し、最初にルーチンを逆アセンブルします。コンパイラーが、知っているすべての潜在的なトリックと、知らなかったいくつかのトリックを既に使用していることに気付くでしょう。
  • 文字列が潜在的に非常に大きい (メガバイト) 場合 (ここでは推測しています)、OpenCL/CUDA 経由でグラフィックス カードを使用すると、潜在的な可能性があります。

等々。

しかし、実際に問題が発生した場合は、お持ちのものを使い続けることをお勧めします. これがおもちゃの問題であり、それを楽しむために最適化している場合は、先に進んでください。

サイクル シェービングは、CPU と命令セットを学習する楽しい方法ですが、プログラミング タスクの 99.999999...% では、努力する価値はありません。

于 2012-09-12T20:49:59.230 に答える
3

ポインターを使用して文字列を反復処理できます。少し努力*すれば、1 文字につき 1 回だけ使用できます。

size_t strchroc(const char *str, const char ch)
{ 
    size_t c = 0;
    char n;
    while ((n=*str++), ((n==ch)? ++c : 0), n)
        ;
    return c;
}

コンパイラがまったく同じコードに最適化できなかったわけではありませんが、楽しみのためです。

于 2012-09-12T18:30:08.697 に答える
1

strchr()関数を使用する前に(またはmemchr()長さがわかっている場合は) を使用する必要があります。一致する場合は、最初に一致した文字の位置から開始して、そこから移動できます。

文字列が非常に短いか、非常に早く一致しない限り、これははるかに高速です。

于 2012-09-12T19:46:07.190 に答える
0

簡単な低品質のベンチマークの後、任意の長さの文字列に対してこれで終わりました。

巨大な文字列 (1 億以上) ではあまり大きな違いは見られませんでしたが、短い文字列 (文、通常のテキスト ファイルなど) では約 25% の改善が見られました。

unsigned int countc_r(char *buf, char c)
{
    unsigned int k = 0;

    for (;;) {
        if (!buf[0]) break;
        if ( buf[0] == c) ++k;
        if (!buf[1]) break;
        if ( buf[1] == c) ++k;
        if (!buf[2]) break;
        if ( buf[2] == c) ++k;
        if (!buf[3]) break;
        if ( buf[3] == c) ++k;
        buf += 4;
    }

    return k;
}
于 2013-10-31T02:17:48.983 に答える
0

変数を取り除くことができますi。

size_t strchroc(const char *str, const char ch){ 
    size_t c = 0;
    while(*str != '\0') {
        if(*str == ch) c++;
        str++;
    }
    return c;
}
于 2012-09-12T18:27:48.710 に答える
0 
size_t count_the_string(const char *str, const char ch){
    size_t cnt ;
    for(cnt=0; *str; ) {
        cnt += *str++ == ch;
    }
    return cnt;
}

同等のdo { ...} while();バリアントの場合、GCC は @hakattack のソリューションに匹敵する条件付きジャンプなしでコードを生成します (もちろん、ループのジャンプは除きます)。

size_t count_the_string2(const char *str, const char ch){
    size_t cnt=0 ;
    do {
        cnt += *str == ch;
    } while (*str++);
    return cnt;
}
于 2012-09-12T18:41:29.643 に答える