タグ

PieceTableとbufferに関するterurouのブックマーク (2)

  • テキストエディタ用バッファの各種データ構造とその評価 (2)

    vector類をvector類で管理する組み合わせについて、考察とパフォーマンス測定を行う。 測定項目は以下の項目とする。 バッファ構築時間 シーケンシャルアクセス+1文字削除時間・使用メモリ量 シーケンシャルアクセス+1文字挿入時間・使用メモリ量 vector<shared_ptr<array<char>>> 最も基的な組み合わせ。 STL には array が無いので、reserve であらかじめ領域を確保しサイズを固定にした vector<char> を代わりに用いる。 array のサイズは 32KB としてみる。array サイズを変えた場合の計測は余裕があれば行う。 文字データが array サイズ以上になった場合、可能なら前後の array に送る。そうでない場合は新たに array を作成する。 編集コストおよびブロック分割時コストは、ブロックサイズを B とすれば O(

    terurou
    terurou 2010/02/15
    オンメモリに全て展開出来る場合はGapBuffer、メモリに格納できない場合はPieceTable
  • w.l.o.g. ギャップバッファ

    04:40 04/06/04 ピーステーブル PieceTable とも言う。文字列の Piece(小片)を繋げて、 一つの巨大な文書を表現する方式。 検索すると引っかかる文書のほとんどが AbiWord 関係なので、 このワープロソフトの主要な内部データ構造ということなのかな。 他に、MS-WordやOpenOffice.org関連の文書にも登場していて、 基的に単なるテキストエディタよりは、文字に付加情報をくっつける系の 編集ソフトに使われる場面が今のところ多いみたいです。 余談ですがAbiWordは、綱渡り的にですがBeOS版の開発が続いている貴重なワープロソフトなのです。感謝感謝。 概要 ファイルを読み込んだとしましょう。ABCDEFG、という7文字のファイル。 とりあえず、7文字分のOrigという名前のバッファを用意して、そこに格納します。 それと別に、Addという名前の空のバ

    terurou
    terurou 2010/02/15
    PieceTableの基本構造解説
  • 1