テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum

テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を

[rryu]

仕組み的にはread-onlyのバッファは無くても何とかなるのだが、おそらくmmapすることを意図しているのだと思う。

[u_mid]

↓「〜がち」(漢字だと～勝ち)は「黒目がち」「遠慮がち」等、別にそれ自体が悪い傾向を含ませる言葉ではないと思いますよ、「上回りがち」とか使ってもいいですし（「早い者勝ち」は用法が別でした）

[wait0000]

こちらも良い記事で各データ構造のパフォーマンス比較してる http://vivi.dyndns.org/vivi/docs/buffer/edit_buffer2.php

[ysync]

全体が必要なのは完成後の話なので、ラインエディタの挙動をまんま持ってきても構わなくね？／ジャーナリングfsくらいまで拡張する話？

[minamishinji]

アルゴリズム自体も興味深いけど、アルゴリズムに名前をつけるのって意外に重要かもと思った記事。

[kmaebashi]

この方法のメリットは、rryuさんの言うようにread-onlyバッファをmmapで割り当てれば、「巨大なファイルを開いて、ちょっと直す」みたいな作業が速い、ということでいいのかな。

[fujihiro0]

ファイルを mmap して read-only にする方式だと、文字コードの変換が必要なとき使えない。であってる？ / こっちにその件について書かれてた。http://vivi.dyndns.org/vivi/docs/buffer/edit_buffer2.php

[rezelolike]

テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum

[Ehren]

めちゃ面白い

[turanukimaru]

連続したデータの途中に新しくデータを挿入するのは紙でもメモリでも不得手なところなので、文章を断片にして管理する。Piece Table は紙の本に付箋を貼って注釈をつけていく形で編集すると考えるとわかりやすいかも。

[IGA-OS]

いつか参考にする日が来たら良いな？

[imash]

テキストエディタあるあるですか

[mjy]

「〜がち」という表現は、それが悪い傾向であることを暗に示します。そのような意図が無い場合は避けた方が良いでしょう。

[takamR1]

ある業界専門のテキストエディタ開発したことあるけど、STLのdeaqueで実装したなあ

[t_yano]

こういうアルゴリズム記事好きだな

[razokulover]

面白い

[remonoil]

いつか読む必要がある気がする

[misshiki]

“テキストエディタのデータ構造で採用されることが多い Piece Table について紹介し、その実装例”昔、自作バイナリエディタを作ったことがあるのでこういう話は気になってしまう。Piece Table という構造があるのか。

[pekee-nuee-nuee]

おもしろそうだけどいつ読めるかわからない

[kazkun]

納得感は薄い。けどこういうの好き。

[Derabon]

後で読む

[ryunosinfx]

うほ！うほほ！

[ShionAmasato]

こんな色々分類があったのね　へぇ

[yarumato]

“テキストエディタで採用されているデータ構造を比較検討した論文。Gap method や Piece table method をベースにしたものが多い。VS Code では、Piece table を改良した Piece tree データ構造が使われるように”

[nanakoso]

エディタで利用されるデータ構造

[efcl]

"Piece Table は、元のファイルは読み取り専用とし、書き込みは別のバッファに対して行い、バッファ位置を Piece Table として管理する方法" ReadとWriteの分離