3.10 最適化 (1999.09.04 初版)
 ここからは、より実用的なものにするために、クラスをブラッシュアップします。ま 
ずは、効率について検討します。カプセル化はソフトウェアを安全で強力なものにしま 
す。しかし、メンバ関数を介して内部表現にアクセスするために、関数呼び出しのオー 
バーヘッドを伴います。メンバ関数呼び出しのコストはどれぐらいか、またこの様なコ 
ストをできるだけ軽減し効率を上げるにはどうするか、について考察します。 

3.10.1 効率

 効率を考えるときは、最もコストを要する部分を洗い出し、そのボトルネックとなる 
部分を検討することです。行列クラスで頻繁に呼び出されるのは添え字演算子[]でしょ 
う。また演算についてのボトルネックは、掛け算です。行列の掛け算は3重ループ計算 
となるので、100×100の行列では100万回の計算となります。 

 行列クラス・オブジェクトの積計算に使われる実行時間を、2次元配列に対するもの 
と比較してみましょう。次のプログラムは、100×100の行列の積計算を、3つの 
場合について比較します。2次元配列で行う場合、クラス・オブジェクトについて添え 
字演算子による計算と、積演算子*による場合です。
// lst03_24.cpp
// 実行効率のテスト
#include <iostream.h>
#include <time.h>
#include "matrix17.h"

int main()
{
    const int dim = 100; // 行列の次元数

    // 初期設定
    Matrix a(dim,dim), b(dim,dim), c(dim,dim);
    int i,j,k;
    for(i = 0; i < a.getRow(); i++){
        for(j = 0; j < a.getCol(); j++){
            a[i][j] = 0.1*(i+1) + 0.01*(j+1);
            b[i][j] = 0.2*(i+1) + 0.02*(j+1);
        }
    }

    // 配列版
    double (*d)[dim] = new double[dim][dim];
    double (*e)[dim] = new double[dim][dim];
    double (*f)[dim] = new double[dim][dim];

    for(i = 0; i < dim; i++){
        for(j = 0; j < dim; j++){
            d[i][j] = 0.1*(i+1) + 0.01*(j+1);
            e[i][j] = 0.2*(i+1) + 0.02*(j+1);
        }
    }

    clock_t t0 = clock();

    // 配列による行列の積
    for(i = 0; i < dim; i++){
        for(j = 0; j < dim; j++){
            f[i][j] = 0.0;
            for(k = 0; k < dim; k++)
                f[i][j] += d[i][k] * e[k][j];
        }
    }

    clock_t t1 = clock();

    // 添字演算子を使って行列の積を計算
    for(i = 0; i < a.getRow(); i++){
        for(j = 0; j < b.getCol(); j++){
            c[i][j] = 0.0;
            for(k = 0; k < a.getCol(); k++)
                c[i][j] += a[i][k] * b[k][j];
        }
    }

    clock_t t2 = clock();

    // *演算子を使って行列の積を計算
    c = a * b;

    clock_t t3 = clock();

    cout << "次元数:" << dim << "×" << dim << endl;
    cout << "計算時間(2次元配列での積): "
         << (t1-t0)/ (float) CLOCKS_PER_SEC << "(秒)" << endl; 
    cout << "計算時間(添字演算子での積): "
         << (t2-t1)/ (float) CLOCKS_PER_SEC << "(秒)" << endl; 
    cout << "計算時間 (*演算子での積): "
         << (t3-t2)/ (float) CLOCKS_PER_SEC << "(秒)" << endl; 

    delete [] f;
    delete [] e;
    delete [] d;

    return 0;
}
ソースファイル ( lst03_24.cpp )
計測のために、C標準ライブラリ <time.h> 内の clock 関数を使います。これは使用 
したプロセッサ時間(CPU時間)を求める関数で、次のようにプロトタイプ宣言され 
ています。 

clock_t clock(void); 

関数が返すのは、プログラムが実行を開始してからそれまでに使用したプロセッサ時間 
で、型 clock_t は <time.h> で定義されたプロセッサ時間を表す算術型です。 
 この関数を使って、2つのイベント間の時間を計測できます。時間を秒単位で表現す 
るには,clock が返す値をマクロ CLOCKS_PER_SEC (または CLK_TCK) の値で 
割ります。つまり、 

clock_t t0 = clock(); 

// 処理 

clock_t t1 = clock(); 

cout << ( t1 - t0 ) /  (float) CLOCKS_PER_SEC << endl; 

で処理に要した時間を秒単位で求めることができます。 

[注] ANSI C 規格ではマクロ名 CLOCKS_PER_SEC の方が定められています。 一方、マクロ名 CLK_TCK は規格案の段階で使われていたため、現在も互換性 のために残されています。  CLK_TCK という名前は、「時計(clock)がカチカチ動く(tick)ことから、 1秒を意味する」というのが由来ですが、しかしあまりにも暗号的なので変更 された(平林雅英著「ANSI C言語辞典」、技術評論社)そうです。
 プログラム lst03_24.cpp の実行結果を示します。これは Pentium 133MHzマシン (いまでは非力になってしまった)によるものです。
次元数:100×100 
計算時間(2次元配列での積): 0.559(秒)
計算時間(添字演算子での積): 1.471(秒)
計算時間 (*演算子での積): 0.649(秒)
 結果は、添え字演算子を頻繁に使う場合、そのコストが大きいことを示しています。
添え字演算子を使った内部表現へのアクセスは、 

a[i][j] 

の第1の添え字iに対して、行列・オブジェクトのメンバ関数(添え字演算子関数)

a.operator[]( i ) 

が呼び出され、この関数は行ベクトル要素(ベクトル・オブジェクト) a.ptr[i]を参
照型で返します。更に、第2の添え字jに対してベクトル・オブジェクト a.ptr[i]の
添え字演算子 

a.ptr[i].operator[]( j ) 

が呼び出されて、この関数は 

a.ptr[i].ptr[j] 

を返します。この様に、2段階でメンバ関数呼び出しが行われます。 
 また関数呼び出しのコストの他に、添え字演算子関数は範囲の逸脱についてのチェッ
クを行います。 

3.10.2 メンバ関数のインライン化

 C++では、関数呼び出しのオーバーヘッドを無くすために、インライン関数が導入さ 
れています。クラス定義の中で宣言、定義されたメンバ関数はインライン関数として扱 
われます。 
 またメンバ関数をクラス定義の外でインライン化指定することもできます。それには、 
メンバ関数の定義の先頭にキーワード inlineを付加します。ただし、インライン化す 
る関数はヘッダファイル内で定義します。インライン関数とは、プログラム内でその関 
数を呼び出した箇所に関数コード本体のコピーを埋め込むことです。従って、インライ 
ン関数の定義自体が利用するプログラムに公開されている必要があります。また、実行 
プログラムのサイズはその分大きくなります。 

 添え字演算子関数をインライン化したバージョン( matrix18.h )を示します。
// matrix18.h 
// Matrixクラス Vectorクラス インターフェイス部 
#ifndef MATRIX18_H 
#define MATRIX18_H 

#include <assert.h> // assertマクロを使う 

class Vector{ 
      ・・・・ 
public: 
      ・・・・ 
    double &operator[](int);           // 非constオブジェクト 
    const double &operator[](int) const;// constオブジェクト 

private: 
    double *ptr; //ベクトルの先頭要素へのポインタ 
    int Dim;     //ベクトルの次元 
   ・・・・ 
}; 

class Matrix{ 
      ・・・・ 
public: 
      ・・・・ 
    Vector &operator[](int);          // 非constオブジェクト 
    const Vector &operator[](int) const;// constオブジェクト 

private: 
    Vector *ptr;// 行ベクトルへのポインタ 
    int Row;    // 行の数 
    int Col;    // 列の数 
   ・・・・ 
}; 

//非const Vectorオブジェクトの添え字演算子 
inline double &Vector::operator[](int index) 
{ 
    assert( index >= 0  && index < Dim ); 
    return ptr[index]; 
} 

//onst Vectorオブジェクトの添え字演算子 
inline const double &Vector::operator[](int index) const 
{ 
    assert( index >= 0  && index < Dim ); 
    return ptr[index]; 
} 

//非const Matrixオブジェクトの添え字演算子 
inline Vector &Matrix::operator[](int index) 
{ 
    assert( index >= 0  && index < Row ); 
    return ptr[index]; 
} 

//const Matrixオブジェクトの添え字演算子 
inline const Vector &Matrix::operator[](int index) const 
{ 
    assert( index >= 0  && index < Row ); 
    return ptr[index]; 
} 
#endif
 添え字範囲のチェックにif文の代わりに assertマクロを使っています。この用法は
#2[補足2]new演算子の例外実験でみたように、これはプログラムの診断マクロで、
ヘッダファイル <assert.h> で定義されています。if文を使うよりコードが簡潔にな
ります。ただし、条件式がif文とは反対になります。つまり、assertマクロは

void assert(int test); 

という構文で、引数 test が 0(偽)の場合に診断メッセージを出力して、プログラ
ムを終了させます(abortを呼び出す)。従って、例えば非const Matrixオブジェク
トに対する添え字演算子の定義は、 

inline Vector &Matrix::operator[](int index) 
{ 
    assert( index >= 0  && index < Row ); 
    return ptr[index]; 
} 

というように、添え字indexが満たすべき条件(範囲内にある)を記述します。このと 
き、assert()の引数が偽になると、次のような診断メッセージを表示して実行を終了 
します。 

assertion failed: index >= 0 && index < Row, file matrix18.h, line 121 

Abnormal program termination
表示される診断情報は、引数のテキスト、ソースファイル名と行番号です。つまり、行 
番号121とは、エラーを起こした文 

assert( index >= 0 && index < Row ); 

の位置を意味します。 

 またこの診断マクロは、その機能を無効にすることもできます。次のように、ヘッダ 
ファイル <assert.h>をインクルードする前にプリプロセッサ命令#define NDEBUG を 
宣言しておくと、そのファイル内の assert文は全て無視されます。 

#define NDEBUG 
#include <assert.h>

この用法についてはすぐ後で扱います。 
3.10.3 2つのクラスに対してフレンドな関数

 行列とベクトルの演算でボトルネックとなるのは乗算*です。2つの行列の積は、次 
の様に実装しました( インターフェース matrix17.h を参照)。 

// 行列×行列 
const Matrix operator*(const Matrix &left, const Matrix &right)
{
    if(left.Col != right.Row){//サイズのチェック
        cout << "エラー:行列の型が一致しません\n";
        abort();
    }
    Matrix mat(left.Row, right.Col); //一時的なオブジェクトを作る
    for (int i = 0; i < left.Row; i++)
        mat.ptr[i] = left.ptr[i] * right; // 行ベクトル*行列

    return mat;
}

この演算子関数は、行列クラスに対してフレンドな非メンバ関数です。従って、行列オ 
ブジェクトの内部表現に直接アクセスできます。しかし、ベクトル・クラスの表現には 
アクセスできないために、行列オブジェクトの内部データである行ベクトル要素につい 
ては添え字演算子を使ってアクセスします。コード上は、次の「ベクトル×行列」演算 
子関数を呼び出しています。 

// 行ベクトル×行列
const Vector operator*(const Vector &x, const Matrix &a)
{
    if(a.Row != x.getSize()){//サイズのチェック
        cout << "エラー:ベクトルと行列の型が一致しません\n";
        abort();
    }
    Vector y( a.Col );
    for(int i = 0; i < a.Col; i++){
        double sum = 0.0;
        for(int j = 0; j < a.Row; j++)
            sum +=  x[j] * a.ptr[j][i]; // 添え字演算子
        y[i] = sum;
    }

    return y;
}

 この行ベクトル要素への添え字演算は、範囲チェックを重複して行います。乗算可能 
な行列の型チェックは最初のif文1回で十分であるのに、行ベクトルと行列の積演算子 
の呼び出し 


    for (int i = 0; i < left.Row; i++)
        mat.ptr[i] = left.ptr[i] * right; // 行ベクトル*行列

で、列の要素数についてのチェックが何度も(left.Row 回)行われます。 

 この添え字演算子の使用と過剰な範囲逸脱のチェックを避けるにはベクトルの内部表 
現に直接アクセスすることで解決できます。そのために、積演算子を行列クラスとベク 
トル・クラスの2つのクラスに対してフレンド関数にします。 
class Vector{ 
    friend const Vector operator*(const Matrix &, const Vector &); //積 
    friend const Vector operator*(const Vector &, const Matrix &); 
    friend const Matrix operator*(const Matrix &, const Matrix &); 
    ...... 

}; 

class Matrix{ 
    friend const Vector operator*(const Matrix &, const Vector &); //積 
    friend const Vector operator*(const Vector &, const Matrix &); 
    friend const Matrix operator*(const Matrix &, const Matrix &); 
    ........ 
};
この様に、1つの関数を複数のクラスに対してフレンドにすることができます。これら 
の実装は次のようになります。 
// 多重定義された*演算子
// 行列とベクトルの積を求め、値渡しで返す
const Vector operator*(const Matrix &a, const Vector &x)
{
    if(a.Col != x.Dim){//サイズのチェック
        cout << "エラー:行列とベクトルの型が一致しません\n";
        abort();
    }
    Vector y( a.Row );
    for(int i = 0; i < a.Row; i++){
        double sum = 0.0;
        for(int j = 0; j < a.Col; j++)
            sum += a.ptr[i].ptr[j] * x.ptr[j];
        y[i] = sum;
    }

    return y;
}
// 多重定義された*演算子
// ベクトルと行列の積を求め、値渡しで返す
const Vector operator*(const Vector &x, const Matrix &a)
{
    if(x.Dim != a.Row){//サイズのチェック
        cout << "エラー:ベクトルと行列の型が一致しません\n";
        abort();
    }
    Vector y( a.Col );
    for(int i = 0; i < a.Col; i++){
        double sum = 0.0;
        for(int j = 0; j < a.Row; j++)
            sum +=  x.ptr[j] * a.ptr[j].ptr[i];
        y.ptr[i] = sum;
    }

    return y;
}


// 多重定義された*演算子
// 2つの行列の積を求め、値渡しで返す
const Matrix operator*(const Matrix &left, const Matrix &right)
{
    if(left.Col != right.Row){//サイズのチェック
        cout << "エラー:行列の型が一致しません\n";
        abort();
    }
    Matrix mat(left.Row, right.Col); //一時的なオブジェクトを作る
    for (int i = 0; i < left.Row; i++)
        for(int j = 0; j < right.Col; j++){
            double sum = 0.0;
            for(int k = 0; k < left.Col; k++)
                sum += left.ptr[i].ptr[k] * right.ptr[k].ptr[j];
            mat.ptr[i].ptr[j] = sum;
        }

    return mat;
}
 行列要素 a[i][j] へのアクセスは次のような形式で実現されます。 

a.ptr[i].ptr[j] 

これは、行列オブジェクトaの内部データである行ベクトル(ベクトル・オブジェク 
ト)は次のように表されます。 

a.ptr[i] 

さらにこの行ベクトルの要素はドット演算子(.)を介して a.ptr[i].ptr[j]となり 
ます。行列の内部表現に直接アクセスしているために、余分なオーバーヘッドは除か 
れます。 
3.10 4 最適化の実験

 
  以上の変更をヘッダファイル( matrix18.h )、関数定義プログラム( matrix18.cpp ) 
にまとめます。 

   ソースファイルはこちら
効率の改善をみるために、前のプログラム lst03_24.cpp で新しいヘッダファイルをイ
ンクルードして、

//#include "matrix17.h" 
#include "matrix18.h" 

コンパイル仕直した結果は、次のようになりました。

次元数:100×100 
計算時間(2次元配列での積): 0.53(秒) 
計算時間(添字演算子での積): 1.032(秒)
計算時間 (*演算子での積): 0.343(秒)
 明らかに、積演算子*は高速になっています。この結果は行列の次元にも依ります 
が、2倍速くなる場合もあります。 

 一方、添え字演算子を使った計算は幾分改善されています。これは、関数呼び出し 
のコストの方は0なので、残りは添え字範囲のチェックのコストが効いていると考え 
られます。この推測が正しいことは、assertマクロを無効にすることで確認できます。 
ヘッダファイル matrix18.h にプリプロセッサ命令 

#define NDEBUG 

を追加してassertマクロを無効にしてみましょう。 
---------------------------------------------------- 
// matrix18.h 
// Matrixクラス Vectorクラス インターフェイス部 
#ifndef MATRIX18_H 
#define MATRIX18_H 

#include <iostream.h> 
#include <iomanip.h> 
#include <stdlib.h>
#include <math.h> 

#define NDEBUG 
#include <assert.h> 

----------------------------------------------------- 
結果は次の通りです。 

次元数:100×100
計算時間(2次元配列での積): 0.53(秒)
計算時間(添字演算子での積): 0.319(秒)
計算時間 (*演算子での積): 0.327(秒)
 最後に、クラスオブジェクトを使った計算の方が配列計算よりも、見かけ上高速に 
なった点に触れます。 
 単純なデータ構造である配列計算については、コンパイラの最適化機能が威力を発 
揮します。次の例は、Borland C++ Builder のコマンドライン・コンパイラで最適化
オブション( -O2 :できるだけ高速のコードを生成する)を使ってコンパイルと実行
した結果です。添え字演算子のassertマクロは有効にしています。 

C:\Source>bcc32 -w -O2 lst03_24.cpp matrix18.cpp
Borland C++ 5.4 for Win32 Copyright (c) 1993,1999 Inprise Corporation
lst03_24.cpp:
matrix18.cpp:
Turbo Incremental Link 4.00 Copyright (c) 1997, 1999 Inprise Corporation

C:\Source>lst03_24
次元数:100×100
計算時間(2次元配列での積): 0.218(秒)
計算時間(添字演算子での積): 0.91(秒)
計算時間 (*演算子での積): 0.29(秒)
 結論としてクラスによる設計は、効率を犠牲にすることなく十分に実用的なソフト 
ウェアシステムを構築可能であるといえます。ここでの例で注目すべきことは、クラ 
スを利用するプログラムでは添え字演算子を使うよりも、クラスが提供する演算子* 
を使う方が高速である(理由は上述のごとく)ことです。メンバ関数を提供する甲斐 
がありますね! 

| 目次 | 前のページ| 次のページ | ページの先頭 |

Copyright(c) 1999 Yamada,K