C言語関係掲示板

過去ログ

No.５５４．小文字を大文字に変換する

[戻る]　[ホームページ]
No.4992
注意：演習１０ー２の二問目にある問題の解答より
投稿者---偽ギルガメッシュ(2003/02/04 22:43:42)


ここのHPにある演習１０ー２の二問目にある問題の私なりの解答ですが・・・
#include <stdio.h>

main()
{
 char sentence[]="AbcDefGHij1234lmNOP";
 char *s_pointer;

 s_pointer=sentence;

 printf("%s\n",sentence);

 while(*s_pointer!='\0')
    {
          *s_pointer=(*s_pointer)-32*((96<*s_pointer)&&(*s_pointer<123));  /*注意*/
       
      s_pointer++;
     }

    printf("%s\n",sentence);

return 0;

}


うえのプログラムについてですが、/*注意*/と書いた所の前後を


  if((96<*s_pointer)&&(*s_pointer<123))
  {
   *s_pointer=*s_pointer-32;
  }


にした場合とで、できたEXEファイルの処理の終わる速さに差は出るのでしょうか。
あと、答えとしては、良いでしょうか。
No.4995
Re:注意：演習１０ー２の二問目にある問題の解答より
投稿者---SSA(2003/02/05 02:58:05)


>　確かに膨大なステップ数になってきた時のことを考えれば毎回無条件に
>演算処理をするよりは早くなるでしょう。

少し細かい話をば^^ 関心のある方だけ、どうぞ。

これはCPUアーキテクチャおよびコンパイラ次第だと思います。
コンパイラが最適化をかけてしまうので、この程度のコードではもしかすると
どちらも同じコードになる可能性すらありますが、もし馬鹿正直に元のとおりの
アセンブラコードが吐かれたとすると、if文を使わない方が分岐命令がなくなる
ため、高速化されるかもしれません。(CPUの分岐予測次第)

確かに毎回演算しない方が早い可能性もありますが、それは文字列中にどれだけ
英小文字があるかどうかにも依存しますし、演算と言ってもおそらくsub命令が
たった1つあるだけで(*s_pointerはレジスタに乗っているでしょう)、分岐予測
ミスのペナルティの方が大きいような気がします。

それから、可読性の点では
  if (('a' <= *s_pointer) && (*s_pointer <= 'z')) {
    *s_pointer = *s_pointer - ('A' - 'a');
  }

の方が一般的かと思いました。まあ、こちらは主観によりますが、直値をその
まま書くべきではないと思います。では、失礼致します。
No.5001
Re:注意：演習１０ー２の二問目にある問題の解答より
投稿者---stosd(2003/02/05 12:54:20)


ご自分で実行してみましたか？自分の望む実行結果が出れば問題ありません。
/*注意*/と書かれた行は速度、見た目の両方の点から標準関数のtoupperが理想的です。
    *s_pointer = (*s_pointer) - 32 * ((96 < *s_pointer) && (*s_pointer < 123));  /*注意*/

                    ↓

    *s_pointer = toupper(*s_pointer);


一番重いのは乗除算で、コンパイル後のコードでも乗除算は遅い部類に属しますので、実際のプログラミングで、特にループ中での使用は極力避けた方がいいです。洗練されたコンパイラなら別のコードに置き換えてくれる可能性もありますが、コンパイラに依存したコードはあまり良いものとは言えません。

参項までに、配列参照の形にすると速度の点で効率よくなります。
#include <stdio.h>

/* 'a'〜'z'の領域に'A'〜'Z'を格納しておく */
char    buf[256] = {
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,
    /* 0x61 */
    'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P',
    'Q','R','S','T','U','V','W','X','Y','Z'
};

int    main(void)
{
    char    *p = "abcdefghijklmnopqrstuvwxyz";

    while(*p)
        printf("%c",buf[*p++]);

    printf("\n");

    return 0;
}

'a'〜'z'に該当する領域に'A'〜'Z'を格納しておけば、変換対象の文字をインデックスにして配列を参照するだけで済みますので、変換のための演算をする必要はまったく無くなります。
No.5002
Re:注意：演習１０ー２の二問目にある問題の解答より
投稿者---偽ギルガメッシュ(2003/02/05 14:25:18)


　勉強になりました。
　stost様のプログラムをみたとき、どうなっているのか、仕組みがわからず、実行して、ようやく理解しました。
　なぜか、私の無知と怠惰をさらけ出したみたいで、恥ずかしい・・・。
　
　この掲示板は、私にとって、まさにありがたい先生です。
No.5003
Re:注意：演習１０ー２の二問目にある問題の解答より
投稿者---かずま(2003/02/05 14:56:33)


> 'a'〜'z'に該当する領域に'A'〜'Z'を格納しておけば、変換対象の文字を
> インデックスにして配列を参照するだけで済みますので、変換のための演算を
> する必要はまったく無くなります。

そのプログラムだと、"AbcDefGHij1234lmNOP" という文字列に対して
小文字以外がすべて '\0' に変換されてしまいます。
また、char が符号付きの場合、buf[128]〜buf[255] が参照される
ことはなく、buf[-128]〜buf[-1] が参照されてしまいます。
#include <stdio.h>

char buf[256] = {
      0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
     16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
     32,'!','"','#','$','%','&', 39,'(',')','*','+',',','-','.','/',
    '0','1','2','3','4','5','6','7','8','9',':',';','<','=','>','?',
    '@','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
    'P','Q','R','S','T','U','V','W','X','Y','Z','[', 92,']','^','_',
    '`','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
    'P','Q','R','S','T','U','V','W','X','Y','Z','{','|','}','~',127,
    128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
    144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
    160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
    176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
    192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
    208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
    224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
    240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
};

int main(void)
{
    char *p = "AbcDefGHijk1234lmNOP";

    while (*p)
        putchar(buf[*p++ & 0xFF]);
    putchar('\n');
    return 0;
}

No.5005
Re:注意：演習１０ー２の二問目にある問題の解答より
投稿者---stosd(2003/02/05 15:29:29)


参考のプログラムはあくまでも説明用です。これを使え、と言っているわけではありません。貴方の改良は実用的ですが説明するには不要な部分が多すぎます。説明に必ず実用的なものを使う必要があるとは限らないんですよ。
最初の質問者が混乱するのをできるだけ避けるように。つっこみを入れるのは自由ですが、しっかりと空気を読んでください。改良点を評価して欲しいならいつでもしてあげますが、その時は別のスレでお願いします。
No.5023
Re:注意：演習１０ー２の二問目にある問題の解答より
投稿者---SSA(2003/02/06 01:29:51)


えーと、終わったスレッドを蒸し返して申し訳ないのですが、別スレッドを立てるほどの
話題でもないので、1つだけ指摘させて下さい。
再び細かい話なので、やはり関心のある方だけどうぞ。なお、最初の質問者である
偽ギルガメッシュさんに対する回答ではありません。

>/*注意*/と書かれた行は速度、見た目の両方の点から標準関数のtoupperが理想的です。

まず大前提として、toupper()が最善であろうという意見には大賛成です。
これを断った上で、以下の（細かい）指摘をします。

>参項までに、配列参照の形にすると速度の点で効率よくなります。
…
>'a'〜'z'に該当する領域に'A'〜'Z'を格納しておけば、変換対象の文字をインデックス
>にして配列を参照するだけで済みますので、変換のための演算をする必要はまったく
>無くなります。

条件分岐を配列などのテーブル参照に変えるという話は確かにありますが、やはり
高速とは限りません。
（もちろん、stosdさんが一般論的に説明しているということも理解していますが）

そもそも、演算をする必要が全くなくなるということはありません。
配列のi番目の要素にアクセスするためには、

(配列の先頭アドレス) + i * (1要素のサイズ)

という乗算＆加算を行い、要素のアドレスを計算しなければなりません。
その上で、メモリ上のそのアドレスから値をロードして来ることになります。
今回の場合に限って言えば、元の減算を行うコードではメモリアクセスなど必要なかった
のに、配列参照ではメモリアクセスが必要になっています。これはレジスタ上で減算を
行うだけに比べて、大きく遅いはずです。

なお、x86系アーキテクチャでは、上記のアドレス計算とメモリアクセスを1命令で行う
ことができることは承知しています。（が、1命令でも高速かどうかは私は知りません）
しかし、他のアーキテクチャ（例えば、unix等で一般的なSparcやPA-RISCなど）では
きっちりアドレスを求める演算が必要になることも多いでしょう。

x86系アセンブラでは、この手の大文字変換などを行うのに、stosdさんの名前である
「stosd」や「loop」といった命令を使うようですが、メモリアクセスを行っても速いので
しょうか。（実測してないので、←は純粋な疑問文です。）
======
結局、私が言いたいのは、C言語上で直感的に高速に見えるコードでも、実際のマシン上で
高速だとは限らないということです。特に、このスレッドで話題になった点などは非常に
デリケートな部分なため、マシンのアーキテクチャと独立には論じられないということです。
差し出がましい発言、申し訳ありませんでした。
No.5030
Re:注意：演習１０ー２の二問目にある問題の解答より
投稿者---stosd(2003/02/06 15:19:29)


>そもそも、演算をする必要が全くなくなるということはありません。
>配列のi番目の要素にアクセスするためには、
>(配列の先頭アドレス) + i * (1要素のサイズ)
>という乗算＆加算を行い、要素のアドレスを計算しなければなりません。
>その上で、メモリ上のそのアドレスから値をロードして来ることになります。
>今回の場合に限って言えば、元の減算を行うコードではメモリアクセスなど必要なか
>ったのに、配列参照ではメモリアクセスが必要になっています。これはレジスタ上で減
>算を行うだけに比べて、大きく遅いはずです。

これはその通りです。実際に計測してもらっているかもしれませんが、これくらい単純な処理では配列参照の方が速度は遅くなります。ただし、toupperよりは速くなります（BC5.5、VC++6.0の場合）。

これは非常に局所的な見方なので、これを理由に"配列参照は遅い"と憶える人が出てしまうことを危惧しています。私としては参考資料としてのプログラムを見てもらい"このような方法も存在する""機会があったら応用してみよう"と考えてくれることを期待しているわけです。No.5003のかずまさんの時も同じ理由ですが、複雑で、詳しすぎる知識を披露されると"最初の質問者に理解してもらおう"という目的から遠のいてしまうので、私としてはご遠慮願いたい次第です。プログラミングの能力に長けている人ならば、質問の内容だけではなく質問者の能力も文面から読み取っていただきたい。

経験されているかもしれませんが、配列参照は今回の場合よりも大規模、複雑なプログラムの場合に効果を発揮します。例えば組み込み等で使われる三角関数のテーブル等がそうです。

>x86系アセンブラでは、この手の大文字変換などを行うのに、stosdさんの名前である
>「stosd」や「loop」といった命令を使うようですが、メモリアクセスを行っても速い
>のでしょうか。（実測してないので、←は純粋な疑問文です。）

この掲示板で答える内容では無いと思いますが一応お答えします。私の経験からはMOVSx、STOSx系のストリング命令とリピートプリフィクスの組み合わせはメインメモリ内でなら最速だと思います（xはB、W、D。Dは32bitから）。ただし、他のデバイスが持つメモリに対しては遅くなります。
No.5004
Re:注意：演習１０ー２の二問目にある問題の解答より
投稿者---kikk(2003/02/05 15:07:21)


ども。


>にした場合とで、できたEXEファイルの処理の終わる速さに差は出るのでしょうか。

clock()あたりを使って実際に測ってみてはどうでしょ?
処理が軽すぎるというのであれば、表示以外の部分をループでくくって
何度も実行するようにすればOKです。


>あと、答えとしては、良いでしょうか。

文字コードが(EBCDIC等の)ASCII以外の環境では、たぶん死にます。
移植性、可読性、速度の面において解答例のtoupper()を使うのが
よろしいかと。


ついで。

ちょっと賢いコンパイラなら*32は<<5に直してくれるかもしれません。

また、&&は左側を評価して偽だったら右側は評価されないという、
一種の条件分岐が潜在的に含まれます(||も同様)。
ただし、今回の場合は条件分岐なしでも該当式を実現できるので、
かなり賢いコンパイラなら式を変形して&&による条件分岐のない
コードを生成するかもしれません。
(('a' <= *s_pointer) && (*s_pointer <= 'z')) /*ASCIIと仮定*/
-> ((unsigned)(*s_pointer-'a') <26u) /*ASCIIと仮定*/

いろんな意味でほどほどに。。


では。