| テキストエディタ実装技術
|
|
|
|
|
| [ index | 前のドキュメント | 次のドキュメント | このドキュメントのソース ]
|
|
|
| ■ CStringListEE の高速化
|
|
|
| CStringList aList のデータを最初から順に参照する場合、以下のように POSITION オブジェクトを使い、ノードを順にたどるのが普通である。この方法であればシーケンシャルアクセスにかかる時間は極めて少ない。
|
POSITION pos = aList.GetHeadPosition(); // 最初のノードへのポインタを取得
while( pos != NULL ) { // ポインタが有効な間
CString text = aList.GetNext(pos); // ポイントしてるノードのテキストを取得し、次のノードへ
.....
}
|
| CStringListEE でも同様に POSITION でのノード指定とノード移動を可能にすれば、先のシーケンシャルアクセスが高速化できる。しかし、POSITION は CStringList に強く依存するし、クラスの実装の都合がインタフェースに影響するのはエディットエンジンの設計としは好ましくない。そこで、直前にアクセスされた行番号とノードを覚えておき、getText() で指定された行番号が覚えておいた行の次であれば、覚えているノードの次のノードのテキストを返すようにする。
|
| メンバ変数に直前にアクセスされたの行番号、ノードへのポインタを追加する。これらのデータをキャッシュと呼ぶことにする。
|
class CStringListEE : public CEditEngine
{
CStringList m_editBuf;
int m_lastLine; // 直前にアクセスされた行番号
POSITION m_lastPos; // 直前にアクセスされた行ノードへのポインタ
.....
}
|
| CStringListEE::getText() の実装では、キャッシュが有効で、キャッシュの次の行番号であれば、ノードを移動しテキストを返すようにする。実装は以下のようになる。
|
bool CStringListEE::getText(
int line, // 行番号 [0..N-1]
CString &text) // output:指定行の文字列
{
if( m_lastPos != NULL ) {
if( line == m_lastLine + 1 ) { // 次の行を参照
m_lastLine += 1;
m_editBuf.GetNext(m_lastPos);
text = m_editBuf.GetAt(m_lastPos);
return true;
}
}
POSITION pos = m_editBuf.FindIndex(line); // 行番号
if( pos == NULL ) // 指定行が存在しない場合
return false;
text = m_editBuf.GetAt(pos);
m_lastLine = line;
m_lastPos = pos;
return true;
}
|
| このキャッシュを用いた実装でシーケンシャルアクセスのパフォーマンス計測を行ってみた。以前の結果は、
|
CStringListEE:
シーケンシャルアクセス（1000 行、最初から最後）:0.000 sec
シーケンシャルアクセス（10000 行、最初から最後）:0.321 sec
シーケンシャルアクセス（20000 行、最初から最後）:3.255 sec
シーケンシャルアクセス（30000 行、最初から最後）:16.714 sec
|
| だったのが、
|
CStringListEE:
シーケンシャルアクセス（1000 行、最初から最後）:0.000 sec
シーケンシャルアクセス（10000 行、最初から最後）:0.010 sec
シーケンシャルアクセス（20000 行、最初から最後）:0.010 sec
シーケンシャルアクセス（30000 行、最初から最後）:0.010 sec
|
| となった。
|
| このように直前にアクセスされた行番号とノードを覚えておき、その情報からノードを高速に取得する手法を行番号キャッシュ法と呼ぶ。
|
|
|
| [ index | 前のドキュメント | 次のドキュメント | このドキュメントのソース ]
|