- メモリのオーバーヘッドが少ない。 利用可能なメモリのほとんどは、オーバーヘッド情報ではなく、テキストの保存に使用する必要があります。
- テキストの任意の場所で効率的な挿入と削除を許可します。
これらの要件を満たすことは同時に容易ではありません。 配列、リスト、ツリー、スタック、キュー、リングバッファーなどの既知のデータ構造を考慮すると、両方の要件を効率的に満たすことができるような構造は発生しません。 配列の場合、メモリのオーバーヘッドはわずかですが、挿入操作の複雑さはO（n）です。ここで、nは編集されたテキストのサイズです。 リストの場合、挿入と削除の複雑さはO（1）ですが、メモリオーバーヘッドはテキスト自体のサイズの数倍です。 ツリー、ヒープ、リングバッファ、連想配列、およびその他の構造は、テキストをエディタに保存するのにはまったく適用できません。
テキストが一連の配列に格納され、それが順番にリストに結合される場合、ハイブリッドソリューションがあります。 このアプローチにより、配列とリストの利点を組み合わせることができるように思われます（メモリオーバーヘッドの少ない迅速な挿入/削除）。 ただし、このようなソリューションの実装は困難です。 また、メモリの断片化にもつながります。
編集可能なテキストを保存するための効果的なデータ構造に注目してください。これは実装が容易で、一定のメモリオーバーヘッドと、あらゆる場所での迅速な挿入/削除が可能です。 また、RAMに完全に収まらないファイルを効果的に編集することもできます。
このデータ構造はかなり前に発見され、8ビット時代の古いコンピューターのテキストエディターで使用されていたにもかかわらず、先祖のこの秘密の知識はほとんど失われ、現代のエディターではまれです。 10メガバイトの1行で構成されるファイルをメモ帳またはFarで開いてみてください。 文字の挿入と削除は数秒続きます。
説明
固定サイズのメモリブロックを使用し（古い8ビットコンピューターでは、このブロックにすべての空きメモリが使用されます）、編集可能なテキストをこのブロックの先頭のカーソルの前に配置し、カーソルの後のテキストをブロックの末尾に配置します。 テキストは2つの連続した部分でメモリに保存され、それらの間のすべての空きテキストメモリが使用可能です。 テキストの編集プロセスでは、この不変式をサポートしています。バッファーの先頭はカーソルの前のテキストで、末尾はカーソルの後のテキストです。 それだけです！
このデータ構造は、英語の用語Gap Bufferで呼び出されます。 ロシア語の名前はわかりませんが、ロシア語版ウィキペディアには「バッファウィンドウ」という用語しかありません。 ただし、このような用語の翻訳を信頼するかどうかはわかりません。
分析
- 貼り付けと削除の操作は安価です。O（1）単一の文字とそのグループ（たとえば、クリップボードからの貼り付け）の両方を貼り付けます。
- メモリのオーバーヘッドが低い：O（1）。 カーソル位置と合計バッファサイズのみを保存する必要があります。
- インデックス検索操作は安価です：O（1）。
- コンテンツのセクションをコピーする操作（たとえば、クリップボードにコピーする、またはディスクにテキストを保存する）はO（n）です。ここで、nはコピーされたセクションのサイズです。 複雑さはアレイの場合と同じです。
言い換えれば、上記の操作について、アレイが提供するすべての利点を実現することができました。
ギャップバッファーを使用すると、カーソルを移動するコストがテキストエディターに表示されます。 結局、不変式を保証するためには、バッファの一番下にある部分から一番上にテキストをコピーするか、その逆にコピーする必要があります。 カーソルの移動の難しさはO（n）です。nはカーソルの移動距離です。 テキストの最初から最後に移動すると、顕著なユーザー遅延が発生する場合があります。 ただし、テキストの先頭から末尾への移動は、編集するときに比較的まれな操作です。 多くの場合、文字、行、またはページごとに前後に動きがあり、その後、テキストのごく一部を移動するだけで済みます。 遅延は、8ビットコンピューターでも見えません。
したがって、ギャップバッファは、カーソルがある場所で常に挿入および削除操作が発生するテキスト編集プロセスのプロパティを利用します。 次に、カーソルの動きは通常小さくなります。
バリエーション
1.シャドウレコーディングカーソル
その基本的な実装では、ギャップバッファーは依然として不要な遅延を引き起こす可能性があります。 たとえば、テキストを検索したり、ブックマークを使用したりすると、カーソルが大幅に移動する可能性があります。 また、テキスト内のカーソルのすべての移動に編集が伴うわけではありません。 したがって、解決策：ユーザーには見えない「レコードカーソル」を入力します。これは、ギャップバッファーのギャップに対応します。 このカーソルは、ユーザーがテキストの挿入または削除を開始したときにのみ移動します。 表示カーソルをテキスト上に単に移動または置換する場合（つまり、テキストの合計サイズが変わらない場合）、レコードカーソルを移動しないでください。 これにより、テキストの表示時、ブックマークの使用時、検索時など、表示カーソルのランダムな移動中の遅延がなくなります。
2. RAMに収まらないファイルを編集する
ギガバイトサイズのRAMの時代では、テキストをメモリに完全にロードせずにエディタを実装する人はほとんどいません。 人々によって作成されたドキュメントのほとんどはそれに収まるので、エディターを複雑にすることはまったく意味がありません。 ただし、現在のコンピューターのメモリにも収まらない大きなファイルを編集することが必要になる場合があります。 これは、ログファイルや、センサーやデバイスからのレコードのテキスト表現などのマシン生成データです。
ギャップバッファーを使用すると、コンピューターのRAMよりも大きいファイルを効率的に編集できます。 ギャップバッファーは実際には2つのスタックで構成されており、1つはカーソルの前にデータを格納し、もう1つはカーソルの後にデータを格納します。 最初のスタックは成長し、2番目のスタックは成長します。 したがって、アイデアは、両方のスタックをファイル形式で実装し、RAMに最上部に近いセクションのみを格納することです。
メモリ内のスタックは拡大または縮小でき、ファイルとして実装されたスタックは拡大のみ可能です。 ファイルの最後にのみデータを追加できます。逆の場合は、そこからデータを削除できます。 ここでメモリ操作に戻り、スタックがさまざまな方向に成長することを検討すると、スタックが上向きに成長していること、スタック上の配置の順序に対してデータが直接の順序で配置され、スタックが下向きに成長していることが逆の順序であることがわかります。 したがって、ギャップバッファーを2つのスタックが上向きに成長する形で実装する場合は、カーソルの後のテキストを格納する2番目のスタックの要素の順序を変更する必要があります。 したがって、カーソルの後にデータを含む一時ファイルには、データを逆順で、最初から最後まで含める必要があります。
一時ファイルには、スタックのすべてのコンテンツではなく、その下部のみを保存します。 上部はRAMに配置され、一種の「ローカル」ギャップバッファーを形成し、ユーザーが以前と同様にテキストをすばやく編集し、特定の制限内で移動できるようにします。 カーソルがメモリにロードされた領域の外側のテキスト上に移動すると、カーソルから最も遠い部分が一時ファイルの1つに保存され、不足している部分が他の一時ファイルからロードされます。
テキストの編集が終了したら、カーソルを最後に移動します。 すべてのテキストは、最初のスタック、つまり最初の一時ファイルに成長します。 RAMには、おそらくテキストがまだ残っています。ファイルに追加するだけです。 その後、最初の一時ファイルには保存されたテキストが含まれます。
さらにいくつかの最適化を実装できます。 たとえば、ファイルを開くとき、通常カーソルはその先頭にあります。 したがって、すべてのテキストは2番目のスタックに配置する必要があります。つまり、編集したファイルのほとんどすべての元のコンテンツを2番目の一時ファイルに逆方向にコピーする必要があります。 これは時間のかかる操作です。 これは、必要になるまで2番目の一時ファイルの作成を遅らせることで回避できます。 つまり、ソースファイルの末尾の内容が2番目のスタックの内容と完全に一致する限りです。 この期間中に、2番目の一時ファイルを使用する代わりに、ソースファイルから情報をロードできます。 この方法で2番目の一時ファイルを作成するには、最初にカーソルをテキスト上で空きRAMのサイズを超える距離まで移動し、そこで何かを編集してからテキストの先頭に戻る必要があります。
最初の一時ファイルにも同じ最適化を実装できます。 必要になるまで作成しないでください。 そして、ディスク上にある最初のスタックの一部の内容がソースファイルの最初のセクションと一致しなくなる前に発生します。 また、「シャドウ記録カーソル」を使用して、編集せずにテキスト内でカーソルを移動するときに不要なコピー操作を回避することもできます。 次に、ユーザーが編集せずにテキスト上でカーソルを遠くに移動した場合、メモリに完全にロードせずにテキストを表示するだけのプログラムよりも速度は悪くなりません。
したがって、説明した方法で実装されたテキストをメモリにロードせずに編集すると、ディスク領域に中程度のオーバーヘッドがあります。一時ファイルにはテキストのサイズに等しい領域が必要です。
興味深いのは、大量のテキストが基本的にRAMに入ったとしても、その全体を読み込まないエディターを使用すると、そのようなドキュメントが速く開くことです。 繰り返しますが、ユーザーの利便性が向上します。
おわりに
障害のある古いコンピューター向けに開発された一部のテクノロジーが私たちの時代に忘れられ、非効率なソリューションの普及につながるという事実に出会ったのはこれが初めてではありません。 この記事で説明する「先祖の秘密の知識」が、優れたテキストエディターの出現に役立つことを願っています。
謝辞
zx.pk.ruフォーラムのトピックで、 ESLユーザーから説明されたデータ構造について最初に学びました。 また、ZX Spectrumなどのリソースが限られているコンピューターに関連して、テキストエディターのメモリを整理する問題についても議論しました。