Crash Course : C の制御の流れ

式と文についての理解が深まったせいか、読むスピードが速まった。今回は3章の「制御の流れ」で理解が足りないところをピックアップしていく。

まずはif-else構文について。elseの部分は省略可能ゆえに、ネストしたie-elseの場合、elseがどのifに対応しているのかがわからなくなるという問題がある。

if (n > 0)
    if (a > b)
        z = a;
    else
        z = b;

インデントを工夫することで人間にわかりやすく書くこともできるが、コンピューターはインデントでは判断しない。コンピューターはelseは直前のifに対応づけるように判断する。それが原則である。だから1個目の ifと対応づけたいならば、

if (n > 0)
{
    if (a > b)
        z = a;
}
else
    z = b;

と{}で対応しなければならない。


次は三分岐の判定を示す二分探索関数について。非常に応用が利きそうだったのでとりあげる。

int binsearch (int x, int v[], int n)
{
    int low, high, mid;

    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid -1;
        else if (x >v[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

low+high が2で割り切れなかったらどうするんだろうと思ったが、確かめてみるとどうやら小数点以下は切り捨てているみたい。 しかし自分はコードを理解するのが遅いなあ。

この二分探索ではループの中で2回のテストを行っているが、本来ループ内テストは1回で十分らしい。(ただしループ外でのテストは増えるとのこと)さて、どう書けばいいだろうか。

#include <stdio.h>

binarysearch(int x, int v[], int n) //where is x in v[]
{
    for (i = 0; i < n; i++){
        if(x == v[i])
            return v[i];
    }
    return -1;
}

単純なforループで探索機能を実装してみた。思考の道筋としては、ループ内でのテストは1回だけという条件なら、不等号テストでは判定しきれない。つまり=か!=かの2択で判定するしかない。これを全要素に順にかけるループを作ればいいのではないか。

つまりこれは、ループの中身の処理を増やすか、ループの回数を増やすかのトレードオフの関係にあると言える。課題には「処理速度を比較せよ」と書かれているが、どうすればいいのか全くわからない。

と思ったら神サイト発見。

www.serendip.ws

ループ外での処理を工夫するというのはこういう意味だったのか。ただただ感動。これは後ほどエントリーを改めて書く。


次はswitch case文について。if else以外の条件分岐の形。これはpythonにはない構文かもしれない。とにかく具体例から。

#include <stdio.h>

main()
{
    int c, i, nwhite, nother, ndigit[10];
    nwhite = nother = 0;

    for (i = 0; i < 10; i++)
        ngitit[i] = 0;

    while ((c = getchar()) != EOF){
        switch (c){
        case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
            ndigit[c-'0']++;
            break;
        case ' ': case '\n': case '\t':
            nwhite++
            break;
        default:
            nother++;
            break;
        }
    }
    printf("digits =");
    for (i=0; i < 10; i++)
        printf(" %d", ndigit[i]);
    printf(", white space = %d, other = %d\n", nwhite, nother);
    return 0;
}

おおむね理解した。まず case のあとは定数式がくる。式ね。それから break文というのは、switch文を抜けるのに使う。breakやreturnはwhileやforのようなループを抜けるための一般的手法であるとのこと。 注意点としては、caseのあとにはbreakを使ったほうがいいとのこと。こういう排他的な条件分岐の場合はbreakがなくても同じように機能するが、書いておいたほうが人間にとってよりわかりやすく、機能を付け加えるときなどに混乱しなくて済むらしい。了解。慣習に従おう。


最後にループやって終わりにしよう。

for ( i = 0; i < n; i++)

これはCでよく使われる慣用句らしいが、i の値や限界値n をループ内で変更できる点は注意。あるいはループが途中で終了したときに、インデックス i は値をそのまま保持しているという点にも注意するべし。これは手続きをひとつずつ追ってみればそうなるのはわかる。

応用としてatoi関数のより精密バージョンを書いてみる。atoiは文字列を数値に変換する関数だが、先頭にスペースがある文字列や、+やーの符号がある文字列もちゃんと処理する。

#include <ctype.h>

int atoi(char s[])
{
    int i, n, sign;

    for (i = 0; isspace(s[i]); i++)
        ;
    sign = (s[i] == '-') ? -1 : 1;
    if (s[i] == '+' || s[i] == '-')
        i++;
    for (n = 0; isdigit(s[i]); i++)
        n = 10 * n + (s[i] - '0');
    return sign * n;
}

; を単独で使うのは、continue; と同じ意味だろうか。それからisspaceやisdigit関数みたいなのが登場しているが、これはctype.hライブラリにある関数だろうか。おそらくbooleanを返すのだろう。

まず最初のfor ループで左から順にスペースかどうかテストしていく。スペースでなかった時点でループを抜ける。それで抜けた時点でi の値は保持されているから、一番左の要素が、'-'ならそれは負の値ということなので、signに-1を、それ以外なら1を代入している。そのあと符号の要素を飛ばして、2個目のループに突入。このときはインデックスはnで始めている。なんという技巧的な流れだろうか。美しい。

次の関数は整数配列を整列させるための関数。これはシェルソートと呼ばれていて、有名なアルゴリズムらしい。

void shellsort(int v[], int n)
{
    int gap, i, j, temp;

    for (gap = n/2; gap > 0; gap /= 2)
        for (i = gap; i < n; i++)
            for (j = i - gap; j >= 0 && v[j] > v[j+gap]; j -= gap){
                temp = v[j];
                v[j] = v[j+gap];
                v[j+gap] = temp;
            }
}

ループ内がどんどん複雑になっていくので、頭が活性化する。楽しい。

まず i や n のような単純な名前の変数以外の変数にはなにかしら人間が解釈できる意味のある名前がついている。そう推測できるだろう。なので、まずは変数の意味を考えるところから始めるのがいいのではないかと最近思うようになった。

それでここでは gap の意味が大事になりそうだが、ソートの比較対象とのインデックスの差という意味でとらえるといい。あと3番目のループの後処理で、

j -= gap

をかける理由がわからなかったが、なんとなく見えてきた感じがする。理解するのに時間がかかった。かなり難しいので、次のエントリーでわかりやすくまとめることにしよう。なんかプログラマーって、人間が苦手な思考を得意とする気がする。