14

メモ帳などのエディタの実装で使用されるデータ構造。このデータ構造は拡張可能である必要があり、編集、削除、スクロール、テキスト範囲の選択などのさまざまな機能をサポートする必要がありますか?

4

6 に答える 6

8

私たちは古いマシン用のエディターを作成しました (これは少し前の 1986 年頃のことなので、これは記憶によるものであり、最新技術はそれ以降多少進歩している可能性があることを覚えておいてください)。セルフマネージド プールの固定メモリ ブロックを使用することで、パフォーマンスを向上させます。

これには 2 つのプールがあり、それぞれが一定数の特定サイズのブロックを含んでいました (1 つのプールはライン構造用で、もう 1 つはライン セグメント構造用でした)。それは基本的に、リンクされたリストのリンクされたリストでした。

メモリは ' ' のような呼び出しから (各領域に対して) 事前に割り当てられmalloc()、65,535 ブロックを使用しました (0 から 65,534 までを含み、ブロック番号 65,535 はヌル ブロック、つまりリストの終わりのインジケーターと見なされました)。

これにより、それぞれ 65, 535 行 (埋め込みバージョンの場合は 384K または 512K) と約 1.6G のファイル サイズ (2G の割り当てられたスペースを使用) が可能になり、当時はかなり大きかったです。これが理論上のファイル サイズの制限でした。線分構造の完全なセットを割り当てなかったので、実際にはこれに近づいたとは思いません。

malloc()メモリの小さなブロックごとに呼び出す必要がないため、速度が大幅に向上しました。特に、固定サイズのブロック用に独自のメモリ割り当てルーチンを最適化できたためです (最終的な最適化バージョンでの呼び出しのインライン化を含む)。

2 つのプールの構造は次のとおりで、各行は 1 バイトです)。 

Line structure (6/8 bytes)     Line-segment structure (32 bytes)
+--------+                     +--------+
|NNNNNNNN|                     |nnnnnnnn|
|NNNNNNNN|                     |nnnnnnnn|
|PPPPPPPP|                     |pppppppp|
|PPPPPPPP|                     |pppppppp|
|bbbbbbbb|                     |LLLLLLLL|
|bbbbbbbb|                     |LLLLLLLL|
|........|                     |xxxxxxxx|
|........|                     :25 more :
+--------+                     : x lines:
                               +--------+

どこ：

  • x線分プールを指す以外の小文字。
  • 大文字はライン プールを指します。
  • N次の行のブロック番号 (null は、これがファイルの最後の行であることを意味します)。
  • P前の行のブロック番号 (null は、これがファイルの最初の行であることを意味します)。
  • bその行の最初の行セグメントのブロック番号です (行が空であることを意味する null)。
  • .予約済みのパディングでした (構造を 8 バイトにするため)。
  • n次のライン セグメントのブロック番号です (null は、これがラインの最後のセグメントであることを意味します)。
  • p前のライン セグメントのブロック番号です (null は、これがラインの最初のセグメントであることを意味します)。
  • Lセグメントのライン ブロックのブロック番号です。
  • xその行セグメントの 26 文字でした。

行構造がパディングされた理由は、ブロック番号から実際のメモリ位置への変換を高速化するためでした (その特定のアーキテクチャでは、6 を乗算するよりも 3 ビット左にシフトする方がはるかに高速で、使用される余分なメモリはわずか 128K で、合計に比べて最小限でした)。ただし、メモリを重視するユーザー向けに低速バージョンを提供しました。

また、100 個の 16 ビット値の配列もありました。これには、ほぼその割合で線分 (および特定の行にすばやく移動できるように行番号) が含まれていました (そのため、array[7] は、おおよそ 7% にある行でした)各プール内のフリー リストを維持するための 2 つのフリー ポインタ (これは非常に単純な一方向リストでN、n構造内で次のフリー ブロックが示され、これらのリストの先頭からフリー ブロックが割り当てられ、そこに戻されます。 ）。

ファイルでは 0 バイトは有効ではないため、各行セグメントの文字数を保持する必要はありませんでした。各行セグメントは、完全に無視される末尾の 0 バイトを持つことが許可されていました。行は、変更されるたびに圧縮されていました (つまり、線分が結合されていました)。これにより、ブロックの使用率が低く保たれ (まれで時間のかかるガベージ コレクションがなくても)、検索と置換操作が大幅に高速化されました。

これらの構造を使用すると、テキストの編集、挿入、削除、検索、およびナビゲーションを非常に高速に行うことができます。これは、単純なテキスト エディターでパフォーマンスの問題のほとんどが発生する可能性が高い場所です。

3d選択の使用 ( 3 行の削除や6x6 文字の削除などの vi のようなコマンドを使用するテキスト モード エディターだったため、これは実装しませんでした){line#/block, char-pos}は、テキスト内の位置をマークするタプルを持つことで実装できます。これらのタプルの 2 つを選択範囲に使用します。

于 2009-03-16T05:58:37.730 に答える
6

ロープをチェックしてください。文字列の挿入/削除/編集を高速に処理します。範囲は通常、Rope の実装でサポートされており、スクロールはロープへの逆インデックスで実行できます。

于 2009-03-16T04:43:03.513 に答える
3

HexEditの作者であるJamesBrownによるPieceChainsに関する優れた記事があります。

一言で言えば：ピースチェーンを使用すると、テキストに加えられた変更を記録できます。ロードすると、テキスト全体にまたがるピースチェーンができます。ここで、中央のどこかに挿入します。

新しいバッファを割り当てたり、テキストをコピーしたりする代わりに、2つの新しいピースを作成し、既存のピースを変更します。既存のピースには、挿入ポイントまでのテキストが含まれます（つまり、ピースの長さを変更するだけです）。次に、新しいテキストを含むピースがあり、その後、挿入後のすべてのテキストを含む新しいピースがあります。元のテキストは変更されません。

元に戻す/やり直しの場合、追加/削除/変更した部分を簡単に覚えておくことができます。

ピースチェーンを使用する場合の最も複雑な領域は、表示されるテキストのオフセットとメモリ構造の間に1：1のマッピングがなくなることです。チェーンを検索するか、ある種のバイナリツリー構造を維持する必要があります。

于 2009-05-13T14:16:49.063 に答える
1

Notepad++ の実装を確認してください。SourceForge でソースを表示できます。

于 2009-03-16T04:38:32.273 に答える
-1

通常は、文字の配列のリストまたは配列のようなものを使用します。何年にもわたって、これに関して多くのことが行われてきました:この google searchを見たことがあるかもしれません。

于 2009-03-16T04:46:07.483 に答える