【C++】テキストエディタのバッファ データ構造・アルゴリズム【第３回】

目次

• gap_buffer<char>

gap_buffer<char>

前章でも言及したように、テキストエディタにおいてはテキストの参照・編集箇所は局所化されている。
この性質を利用し、vector を高速化したものが gap_buffer （ギャップバッファ、gap vector とも呼ばれる）だ。

vector と gap_buffer のデータ構造の違いは少なく、前者がアロケートしたデータ領域の後ろに未使用部分があるのに対して、
後者はデータ領域の途中に未使用部分があるという点だけだ（下図参照）。
この未使用部分を「ギャップ」と呼び、常に編集位置に設定される。

このようにデータ構造を少し変えただけで、なぜ高速化されるのか不思議に思われる方も少なくないだろうが、
高速になる理由は、挿入・削除時に何が起こるかを見てみると納得していただけるはずだ。

編集位置に ‘a’, ‘b’ が挿入され、その後 BackSpace で2文字が消される場合を下図に示す。

ギャップは編集位置にあるものとする。編集位置にない場合は、そうなるようにデータを移動する。
そうすると、文字を挿入する処理はギャップの先頭にその文字を書き込むだけで済む。
vector<char> の場合は、挿入位置以降の文字を毎回ずらす必要があったが、
gap_buffer ではギャップがそこにない場合のみギャップを移動すればよい。
連続して挿入する場合はその必要すらない。
しかも、文字挿入位置は前回の文字挿入位置からそう離れていない場合がほとんどなので、
データが大量にあったとしても移動する必要のあるデータ量はかなり少ないことになるのだ。

編集位置から文書末尾方向に1文字が削除された場合（Delete)も見ておこう（下図参照）。

削除の場合も挿入時と同じで、ギャップが編集位置にない場合は、そうなるように移動し、
単にギャップサイズをインクリメントするだけで削除処理があっけなく終わってしまう。
vector<char> の場合は、削除位置以降の文字を前にずらす必要があったが、その必要はない。

このような事情により、gap_buffer の局所的編集処理は O(1) と非常に高速となるのだ。
なんと賢いデータ構造じゃないか、と思うでしょ。

参照処理では、ギャップ位置の判定が入るので vector より若干遅くなるが、
そもそも非常に負荷の小さな処理なので問題にはならず、O(1) と高速だ。

このように、gap_buffer のメモリ効率は vector 同等と、そう悪くなく、局所的編集パフォーマンスが非常によい。
ちなみに、最初期の Emacs に採用されたデータ構造でもある（最新版は未調査）。

◎ クラス実装例

gap_buffer のクラス例を下図に示す。

string, vector の場合とほとんど同じだが、異なるのは、ギャップ位置とギャップサイズを保持しているくらいだ。
非常に単純でわかりやすい。

◎ 実装例

下記に文字参照を行うための operator[](pos_t ix) の実装例を下記に示す。

    char& operator[](pos_t ix) { //  operator[] は範囲チェックを行わない
        if( ix >= m_gapix ) ix += m_gapSize;
        return m_data[ix];
    }

参照位置がギャップ以降かどうかを判定し、そうであれば ix をギャップ分増やして、データ領域を参照しているだけだ。

次に、挿入関数 insert(pos_t ix, char v) の実装例を下記に示す。

    void insert(pos_t ix, char v)
    {
        if( ix < 0 || ix > size() ) return;     //  挿入位置不正の場合チェック
        if( !reserve(size() + 1) ) return;      //  必要なら領域再確保
        move_gap(ix);                           //  挿入位置にギャップ移動
        m_data[m_gapIndex++] = v;               //  ギャップ先頭に文字設定
        --m_gapSize;                            //  ギャップサイズをデクリメント
        ++m_size;                               //  サイズをインクリメント
    }

reserve(size_t sz) は現データ領域が sz 未満の場合は、領域メモリを再アロケートする関数。
move_gap(pos_t pos) はギャップ位置を pos に設定する関数だ。
これらの具体的ソースは本稿では省略するので、読みたい場合は github を参照していただきたい。

削除関数 erase(pos_t ix) の実装例も以下に示しておく。

    void erase(pos_t ix)
    {
        if( ix < 0 || ix >= size() ) return;    //  挿入位置不正の場合チェック
        move_gap(ix);                           //  削除位置にギャップ移動
        ++m_gapSize;                            //  ギャップサイズをインクリメントすることで１文字削除
        --m_size;                               //  サイズをインクリメント
    }

削除位置にギャップを移動し、ギャップサイズをインクリメントしているだけだ。

◎ パフォーマンス計測

50～500メガ文字の場合について、先頭から末尾まで文字参照した場合の処理時間計測結果を以下に示す。
比較のために vector<char> も同じ条件で計測している。

1文字参照に要する時間は O(1) で、vector とほとんど差がない結果となった。

次に、5文字ごとに1文字挿入を最後まで繰り返えした場合の処理時間計測結果を以下に示す。
行長は80文字で、20キロ～200キロ行について計測した。
vector では処理時間が O(N*N) となってしまい比較にならないので、list<string> を比較対象とした。

結果は上記の通りで、合計処理時間は両方とも O(N) だが、
gap_buffer<char> の方が list<string> よりも有意に高速という結果になった。

◎ まとめ

・gap_buffer は、参照処理時間 O(1)、編集箇所が局所的であれば、編集処理時間 O(1) という爆速なバッファである。

筆者：津田伸秀 プロフィール：テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員（主席）。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。