C言語編 目次

　関数設計

　

・関数名の命名規則
・プログラミングに出る！英単語

　ポインタ

　

・データ型とポインタ

　データ型

　

・char *とconst char *は違う
・符号付きと符号なし

　演算子

　

・三項演算子とデータ型の問題

　制御構文

　

・条件式で代入する
・三項演算子を使ったswitch

　構造体

　

・構造体のサイズとアライメント
・構造体メンバのサイズを知る

　配列

　

・配列使用時の注意
・配列の要素数を知る

　メモリ管理

　

・メモリスタック
・動的メモリ確保とメモリリーク

　モジュール設計

　

・モジュール分割
・汎用モジュールとアプリ依存モジュール

　パフォーマンス
　　徹底チューニング

　


・どんな処理に時間がかかるのか
・ファイル入出力の効率化
・アルゴリズムを考える１
・アルゴリズムを考える２

　プリプロセッサの便利機能


・2重インクルード防止

　


トップページへ戻る

アルゴリズムを考える１

　ここでは、Cプログラムのアルゴリズムについて考えます。プログラムはアルゴリズムを見直すことによって、想像以上に高速化することが可能です。いかに高速に動作するアルゴリズムでプログラムを作るかは、プログラマの腕の見せ所です。

　ここでは0.1秒でも速くプログラムが動作するよう、徹底的にアルゴリズムを見直す方法を説明していきます。

　例題として、次のようなプログラムを考えてみます。short型の32768個の配列srcPに0〜32767までの数値を入れ、dstPに反転コピーするというプログラムです。dstPには32767〜0までが、順に入ることになります。今回はWindowsのコンソールアプリで実装しています。

#include <windows.h>
#include <stdio.h>

int _tmain(int argc, _TCHAR* argv[])
{
    const int       datNum = 32768;
    short           *srcP = NULL;
    short           *dstP = NULL;
    int             i, j;
    unsigned int    bt, et;
    int             err = 0;
    
    if (!err) if ((srcP = (short *)malloc(sizeof(short) *datNum)) == NULL) err = 1;
    if (!err) if ((dstP = (short *)malloc(sizeof(short) *datNum)) == NULL) err = 1;
    
    if (!err) for (i = 0; i < datNum; i++) srcP[i] = (short)i;
    // 反転コピー処理 x20000回(1)
    if (!err)
    {
        bt = GetTickCount();
        for (j = 0; j < 20000; j++)
        {
            for (i = 0; i < datNum; i++) 
                dstP[datNum -1 -i] = srcP[i];
        }
        et = GetTickCount() -bt;
        printf("(1)%d\n", et);
    }
    
    if (srcP) {free(srcP), srcP = NULL;}
    if (dstP) {free(dstP), dstP = NULL;}
    return 0;
}

　GetTickCount()は、ミリ秒単位で経過時間を取得する関数です。1回では短かすぎるので、反転コピーを20,000回繰り返した時の処理速度を計測します。純粋な処理速度を測るため、コンパイラによって最適化されないように、デバッグモードで実行します。また、CPUが最大限の力で動作するように、CnQ、EISTが有効になっている場合は、OFFにしておきます。(コントロールパネル→電源オプション→電源設定を「自宅または会社のデスク」に設定する)

　まずは、反転コピーしようと思った場合、どのように実装するでしょうか。最初に誰でも思いつくのは、次のように、配列の添え字を使って、srcPからdstPに一つずつコピーしていく方法です。

// 反転コピー処理 x20000回(1)
if (!err)
{
    bt = GetTickCount();
    for (j = 0; j < 20000; j++)
    {
        for (i = 0; i < datNum; i++) 
            dstP[datNum -1 -i] = srcP[i];
    }
    et = GetTickCount() -bt;
    printf("(1)%d\n", et);
}

　このプログラムを実行すると、管理人の環境(Core Duo 1.5GHz)では、反転コピー処理に8.672[S]かかりました。では、この処理をさらに速くするにはどうすればいいでしょうか。メインになるループ処理はたったの２行ですが、この２行を徹底的に突き詰めていきます。

for (i = 0; i < datNum; i++) 
    dstP[datNum -1 -i] = srcP[i];

　この処理をよく見ると、１つ無駄な演算が入っていることがわかります。それは、datNum -1 -iの部分です。datNumは定数なので、datNum -1も定数になります。毎回1を引く必要はないわけです。この部分は次のように直すことができます。

const int    datNum = 32768, iMax = datNum -1;

...

// 反転コピー処理 x20000回 (2)
if (!err)
{
    bt = GetTickCount();
    for (j = 0; j < 20000; j++)
    {
        for (i = 0; i < datNum; i++) 
            dstP[iMax -i] = srcP[i];
    }
    et = GetTickCount() -bt;
    printf("(2)%d\n", et);
}

　このプログラムを実行すると、管理人の環境では8.688[S]かかりました。処理速度は変わっていません。(WindowsのGetTickCount()は、正確にミリ秒がとれるわけではないので、1/100秒以下は誤差を含むと考えていいでしょう。より高精度に処理速度を計測したい場合は、ループ回数を10倍、100倍に増やします。)

　どうやら、これは処理速度には影響しないようです。このように、プログラムを変えても、コンパイラやCPUのレベルで同じ処理になってしまうことはあります。演算がCPUレベルでどのように処理されるのかまで考慮するのは困難なので、変えてみて速くなっていたら、そのチューニングは効果があると考えるのがよいでしょう。

　さて、ここからさらにチューニングするには、発想を切り替える必要があります。今まではデータを配列として考えてきました。srcP[i]というのは、srcPの先頭アドレスから、short型のサイズがi個分オフセットされたアドレスにあるデータを意味します。ということは、このデータを取り出すためには、*(short *)((char *)srcP +sizeof(short) *i)のような計算が行われていると想像できます。（あくまで想像で、実際にこういう計算がされているとは限りません。）

　これは、かなりの計算量になることが容易に想像できますよね。毎回srcPを基準として、そこからのオフセットを計算しているからです。それであれば、基準位置を毎回ずらしていって、その位置にあるデータを取ったほうが効率的です。こういう考え方をすれば、次のように書き換えることができます。

short    *srcCP = NULL;
short    *dstCP = NULL;

...

// 反転コピー処理 x20000回 (3)
if (!err)
{
    bt = GetTickCount();
    for (j = 0; j < 20000; j++)
    {
        srcCP = &srcP[0];
        dstCP = &dstP[iMax];
        for (i = 0; i < datNum; i++)
        {
            *dstCP = *srcCP;
            srcCP++;
            dstCP--;
        }
    }
    et = GetTickCount() -bt;
    printf("(3)%d\n", et);
}

　srcCP、dstCPには、あらかじめsrcPの先頭アドレス、dstPの最後尾のアドレスを入れておきます。１データコピーしたら、srcCPはインクリメント、dstCPはデクリメントしていけば、順に反転コピーされていくことになります。

　このように変えると、管理人の環境では、7.031[S]で実行できました。実に２割も高速化されたことになります。たった２行の処理でも、一工夫すれば驚くほど高速化されることがわかったと思います。次回は、さらに徹底的にアルゴリズムを見直していきます。