テキストエディタ実装技術

[ index | 前のドキュメント | 次のドキュメント | このドキュメントのソース ]

■ MFC のコレクションクラスを用いたエディットバッファ

MFC には文字列クラス CString のコレクションクラスとして、双方向リンクを用いる CStringList と、動的にサイズを拡張できる配列 CStringArray がある。これらを用いるとエディタのためのバッファクラスを実装することが可能である。本稿ではそれらを利用した実装を示し、それぞれのパフォーマンス計測・比較を行う。

■ クラスの宣言と実装

CStringList を利用するクラスを CStringListEE、CStringArray を利用するクラスを CStringArrayEE という名前にし、パフォーマンス計測のための関数を共通にしたいので、それらを CEditEngine の派生クラスとする。CEditEngine は以下のように宣言できる。


class CEditEngine
{
public:
    CEditEngine();
    virtual ~CEditEngine();

    virtual int     getLineCount() const = NULL;            //  バッファ内の行数を返す
    virtual bool    getText(int, CString&) const = NULL;    //  指定行の文字列を取得
    virtual bool    insertText(int, const CString&) = NULL; //  行挿入
    virtual bool    deleteText(int) = NULL;                 //  行削除
    virtual void    addText(const CString&) = NULL;         //  1行を最後に追加、文字列は最後に改行を含む
    virtual void    removeAll() = NULL;                     //  バッファの内容をクリア
};

実際のエディットエンジンは様々な機能を持たねばならないが、ここではエディットエンジンのパフォーマンス計測に必要なものだけをメソッドとして宣言している。バッファに存在する行数を返す getLineCount()、指定行のテキストを取り出す getText()、指定行の直前に行を挿入する insertText()、指定行を削除する deleteText() の4つのメソッドは、エディットエンジンがエディットエンジンであるために最低限必要な基本機能である。これらを使えば（非効率的かもしれないが）実際に動作するエディタを実装することができる。addText() と removeAll() は、InsertText(), deleteText() を使用すれば、同じ機能を代行することもできるが、パフォーマンス計測プログラムの記述を楽にするために導入した。

2つの派生クラスは以下のように宣言できる。


class CStringListEE : public CEditEngine
{
    CStringList     m_editBuf;
public:
    CStringListEE();
    ~CStringListEE();

    int     getLineCount() const
            { return m_editBuf.GetCount(); };
    bool    getText(int, CString&) const;
    bool    insertText(int, const CString&);
    bool    deleteText(int);
    void    addText(const CString&);
    void    removeAll();
};

class CStringArrayEE : public CEditEngine
{
    CStringArray        m_editBuf;
public:
    CStringArrayEE();
    ~CStringArrayEE();

    int     getLineCount() const
            { return m_editBuf.GetSize(); };
    bool    getText(int, CString&) const;
    bool    insertText(int, const CString&);
    bool    deleteText(int);
    void    addText(const CString&);
    void    removeAll();
};

エディットバッファそのものは、それぞれ CStringList、CStringArray オブジェクトとしている。以下、各メソッドの実装について簡単に説明する。

getLineCount() は、それぞれインライン関数とした。CStringList::GetCount(), CStringArray::GetSize() は要素数を返してくれるので、それをコールするだけである。

getText() は引数で指定される行番号のテキストを取得する。CStringList は POSITION CStringList::FindIndex(int) をコールし、行番号からノードへのポインタを取得し、CString CStringList::GetAt(POSITION) によりテキストを取得する。FindIndex() はリンクの先頭からノードをたどっていくので O(N) の処理時間を要する。GetAt() は O(1) である。CStringArray は配列だから指定された添え字の要素を返す CString CStringArray::GetAt(int) があるので、それを利用するだけである。処理時間は O(1) だ。

■ パフォーマンス計測・比較

パフォーマンスの計測は、エディタとして意味の有る基本機能に対して行わなくてはいけない。ここでは、(1) バッファに大量の行を追加、全体を削除、(2) バッファ内のシーケンシャル・ランダムな行の文字列を取得、(3) バッファ内の特定の位置に行を挿入削除、の3種類の機能を計測対象にすることにした。ファイルを指定してエディタを起動した場合、ファイル内容を読み込みバッファに大量の行を追加しなくてはならない。バッファ内に読み込んだテキストは、カーソル移動、スクロール、行ジャンプによりいろいろな位置のものが参照され画面に表示され、ファイルに保存する場合はバッファの先頭から順に参照されファイルに書き出される。エディタであるからテキストの挿入や削除が行われ、バッファの内容が修正される。これら3種類の機能があれば（最低限機能の）エディタが実現できるわけである。

それぞれのクラスによるパフォーマンス計測結果を以下に示す（環境：Pentium III@800, メモリ384メガ、Win2K）。


CStringListEE:
  10000 行をバッファに追加、削除（10 回）:0.671 sec
  シーケンシャルアクセス（1000 行、最初から最後）:0.000 sec
  シーケンシャルアクセス（10000 行、最初から最後）:0.321 sec
  シーケンシャルアクセス（20000 行、最初から最後）:3.255 sec
  シーケンシャルアクセス（30000 行、最初から最後）:16.714 sec
  ランダムアクセス（1000 行、10000 回）:0.030 sec
  ランダムアクセス（5000 行、10000 回）:0.160 sec
  ランダムアクセス（10000 行、10000 回）:0.361 sec
  ランダムアクセス（20000 行、10000 回）:2.113 sec
  ランダムアクセス（30000 行、10000 回）:5.248 sec
  ランダムアクセス（40000 行、10000 回）:6.690 sec
  ランダムアクセス（50000 行、10000 回）:6.760 sec
  ランダムアクセス（100000 行、10000 回）:6.940 sec
  バッファ先頭に行挿入、削除（10000 行、10000 回）:0.010 sec
  バッファ最後に行挿入、削除（10000 行、10000 回）:1.322 sec
  ランダム位置に行挿入、削除（10000 行、10000 回）:0.631 sec

CStringArrayEE:
  10000 行をバッファに追加、削除（10 回）:0.591 sec
  シーケンシャルアクセス（1000 行、最初から最後）:0.000 sec
  シーケンシャルアクセス（10000 行、最初から最後）:0.000 sec
  シーケンシャルアクセス（20000 行、最初から最後）:0.010 sec
  シーケンシャルアクセス（30000 行、最初から最後）:0.010 sec
  ランダムアクセス（1000 行、10000 回）:0.000 sec
  ランダムアクセス（5000 行、10000 回）:0.000 sec
  ランダムアクセス（10000 行、10000 回）:0.000 sec
  ランダムアクセス（20000 行、10000 回）:0.000 sec
  ランダムアクセス（30000 行、10000 回）:0.010 sec
  ランダムアクセス（40000 行、10000 回）:0.010 sec
  ランダムアクセス（50000 行、10000 回）:0.000 sec
  ランダムアクセス（100000 行、10000 回）:0.000 sec
  バッファ先頭に行挿入、削除（10000 行、10000 回）:0.170 sec
  バッファ最後に行挿入、削除（10000 行、10000 回）:0.000 sec
  ランダム位置に行挿入、削除（10000 行、10000 回）:0.100 sec

バッファの構築時間：List, Array に大きな優劣はない。

ランダムアクセス：CStringArray はサイズに無関係 O(1)、CStringList は、10000 行までは O(N) でここまでは理論どおり。20000 行あたりからは何かのオーバヘッドが効いている。

挿入削除：CStringList の挿入削除は行アクセスの時間を含んでいる。それを差し引けば、処理時間はほとんどゼロ（バッファ最後への挿入削除はランダム位置への約倍の時間を要している。これはノードをたどる処理が常に先頭から行われているためである。CStringList は最後のノードへのポインタも保持しているので、それを利用すれば、ランダムで半分の時間、最後は最初と同じになる。それをしないというのはなんとも間抜けな実装としか言い様が無い。）。CStringArray は、それ以降のデータを移動する必要があるので、先頭への挿入削除がもっとも時間を要する。O(N) だが、CStringList ランダムアクセスの O(N) に比べて、係数はかなり小さい。

結論としては、CStringList は挿入削除処理のパフォーマンスに優れているが、ランダムアクセスに弱い。CStringArray はランダムアクセスのパフォーマンスに優れていて、バッファに大量の行がある場合のデータを大量に移動しなくてはいけないバッファ先頭での挿入削除処理に弱いということである。アルゴリズムの教科書によく記述されていることがちゃんと確認できたわけである。では、CStringList と CStringArray のどちらがエディットエンジンとしてより適切なのであろうか？先の計測結果を見る限りでは CStringArray の方がバランスがいいように見える。しかし本当にそうなのであろうか？

■ ソースコード

本稿のソースコードはここからダウンロードできる。

[ index | 前のドキュメント | 次のドキュメント | このドキュメントのソース ]