テキストエディタ実装技術 ■ MFC のコレクションクラスを用いたエディットバッファ MFC には文字列クラス CString のコレクションクラスとして、双方向リンクを用いる CStringList と、動的にサイズを拡張できる配列 CStringArray がある。これらを用いるとエディタのためのバッファクラスを実装することが可能である。本稿ではそれらを利用した実装を示し、それぞれのパフォーマンス計測・比較を行う。 ■ クラスの宣言と実装 CStringList を利用するクラスを CStringListEE、CStringArray を利用するクラスを CStringArrayEE という名前にし、パフォーマンス計測のための関数を共通にしたいので、それらを CEditEngine の派生クラスとする。CEditEngine は以下のように宣言できる。 ## column 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; // バッファの内容をクリア }; ## endcolumn 実際のエディットエンジンは様々な機能を持たねばならないが、ここではエディットエンジンのパフォーマンス計測に必要なものだけをメソッドとして宣言している。バッファに存在する行数を返す getLineCount()、指定行のテキストを取り出す getText()、指定行の直前に行を挿入する insertText()、指定行を削除する deleteText() の4つのメソッドは、エディットエンジンがエディットエンジンであるために最低限必要な基本機能である。これらを使えば（非効率的かもしれないが）実際に動作するエディタを実装することができる。addText() と removeAll() は、InsertText(), deleteText() を使用すれば、同じ機能を代行することもできるが、パフォーマンス計測プログラムの記述を楽にするために導入した。 2つの派生クラスは以下のように宣言できる。 ## column 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(); }; ## endcolumn エディットバッファそのものは、それぞれ 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）。 ## column 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 ## endcolumn 　 バッファの構築時間：List, Array に大きな優劣はない。 ランダムアクセス：CStringArray はサイズに無関係 O(1)、CStringList は、10000 行までは O(N) でここまでは理論どおり。20000 行あたりからは何かのオーバヘッドが効いている。 挿入削除：CStringList の挿入削除は行アクセスの時間を含んでいる。それを差し引けば、処理時間はほとんどゼロ（バッファ最後への挿入削除はランダム位置への約倍の時間を要している。これはノードをたどる処理が常に先頭から行われているためである。CStringList は最後のノードへのポインタも保持しているので、それを利用すれば、ランダムで半分の時間、最後は最初と同じになる。それをしないというのはなんとも間抜けな実装としか言い様が無い。）。CStringArray は、それ以降のデータを移動する必要があるので、先頭への挿入削除がもっとも時間を要する。O(N) だが、CStringList ランダムアクセスの O(N) に比べて、係数はかなり小さい。 結論としては、CStringList は挿入削除処理のパフォーマンスに優れているが、ランダムアクセスに弱い。CStringArray はランダムアクセスのパフォーマンスに優れていて、バッファに大量の行がある場合のデータを大量に移動しなくてはいけないバッファ先頭での挿入削除処理に弱いということである。アルゴリズムの教科書によく記述されていることがちゃんと確認できたわけである。では、CStringList と CStringArray のどちらがエディットエンジンとしてより適切なのであろうか？先の計測結果を見る限りでは CStringArray の方がバランスがいいように見える。しかし本当にそうなのであろうか？ ■ ソースコード 本稿のソースコードは ここ からダウンロードできる。