ギャップバッファって？

■掲示板に戻る■ ■過去ログ倉庫めにゅーに戻る■

1 名前： デフォルトの名無しさん 投稿日： 2001/03/23(金) 22:03: リスト構造よりもランダムアクセスに強く
配列よりも挿入、追加に強いとか

どんなアルゴリズム＆データ構造なんでしょう？
2 名前： >1 投稿日： 2001/03/23(金) 22:31: 過去に同様の質問が何回かあったなあ。
昔のスレッド（エディタ関係）漁ってみれば？
3 名前： 1 投稿日： 2001/03/23(金) 22:37: >2
おお、そうすかエディタ関係ですね
レスありがとうございます
4 名前： デフォルトの名無しさん 投稿日： 2001/03/23(金) 23:31: ttp://herb.info.nara-k.ac.jp/~i5639/report/gap.html

$B$3$lJ,$+$j0W$$$h!#(B
5 名前： 1 投稿日： 2001/03/23(金) 23:41: >4
おおおお！感謝します！
親切な方ばかりだ
6 名前： デフォルトの名無しさん 投稿日： 2001/03/24(土) 16:14: 勉強になるぞage
7 名前： デフォルトの名無しさん 投稿日： 2001/03/24(土) 19:56: 大昔にテキストエディタをリンクドリストで作ったら「素人臭えやり方」
と言われました。
玄人はギャップバッファを使うもんなんでしょうか？
たしかemacsがそうだったと思いますが。
8 名前： デフォルトの名無しさん 投稿日： 2001/03/24(土) 20:29: 配列があふれたら結局リアロケートすることになると思うんだけど、
頻度が低いから問題にならないのかな？
だとしたらリンクドリスト使う必要もなくなるはずだね。
9 名前： デフォルトの名無しさん 投稿日： 2001/03/24(土) 20:47: >>1
>リスト構造よりもランダムアクセスに強く
>配列よりも挿入、追加に強いとか

この謳い文句が間違っていると思うが、誰が言っているの？
ギャップ近辺の参照、追加、削除は簡単だけど、「先頭から100行目」
とかの移動は大変だよ。結局リンクリストに似た行頭インデックス情報を
用意しないと速度が稼げない。

エディタなどのように、一時に書き換え/参照する部分が偏っているアプリケーション
に対しては向いているが、そうでないときには...

ということで、エディタの内部実装アーキテクチャ向け。今時エディタ
なんかライブラリや OS 組み込みの機能使うし、ファイル入出力の
時点では、ギャップバッファの利点はなくなるから、行単位のリンクリストで
処理しちゃうけどな。
10 名前： 1 投稿日： 2001/03/25(日) 00:04: >>9
全然関係ない調べものをしてるときに見つけました
ttp://www.jah.ne.jp/~naoyuki/Programs/Programs.html

配列を基礎にした概念だったんですね
たしかにエディタぐらいしか有効じゃなさそう
11 名前： デフォルトの名無しさん 投稿日： 2001/03/25(日) 04:38: ギャップのサイズや数って、どうやって決めるの？

たとえばテキストエディタで100KBのファイルを編集するとして、
どの程度の大きさのギャップを、どれだけの数挿入するかって
経験的にやるしかないの？