3

私は基本的なテキスト エディターを作成しています。実際には、メイン プログラムのコード、数値、および式を記述したい編集コントロール ボックスです。

私が現在行っている方法は、文字列をエディット コントロールにフィードすることです。エディット コントロールには、文字列を単語、数字、改行、タブ、フォーマット トークンなどの「グリフ」に分割するクラスがあります。たとえば、単語グリフには、リテラル ワードを表す文字列と、それを表す短い整数が含まれます。末尾の空白の数。グリフには、テキストを描画して行の折り返しを計算するときに必要な情報も含まれています。

たとえば、テキスト行「私の名前はカール」は、次のようなグリフのリンクされたリストと等しくなります。 whitespace ) → WordGlyph (“Karl”, 0 whitespace) → NULL.

そのため、文字列を char (または WCHAR) の連続ブロックとしてメモリに格納する代わりに、多数の小さな割り当てと割り当て解除が行われる可能性のある小さなチャンクに格納されます。

私の質問は; この方法で行う場合、ヒープの断片化に注意する必要がありますか? これをより効率的にするためのヒントはありますか？それとも全く違うやり方？:)

PS。私はWin7でC++で作業しています。

4

2 に答える 2

2

断片化を心配する必要がありますか? 答えは、ドキュメントのサイズ (単語数など)、編集の量、およびそれらの編集の性質によって異なります。あなたが概説したアプローチは、ドキュメントを一度「解析」できる静的（読み取り専用）ドキュメントには妥当かもしれませんが、データ構造を維持するために舞台裏でかなりの量の作業が必要になると思いますユーザーが任意の編集を行っているため、正しい状態にあります。また、「単語」が何であるかを決定する必要があります。これは、すべての場合に必ずしも明白/一貫しているわけではありません。たとえば、「勤勉」は 1 語ですか、それとも 2 語ですか? それが1つの場合、ハイフンでワードラップしないということですか? または、「単語」が 1 行に収まらない場合を考えてみましょう。その場合、

私の推奨事項は、テキストをブロックとして保存し、改行を個別に (テキスト ブロックへのオフセットとして) 保存し、変更があるたびに必要に応じて改行を再計算することです。断片化と割り当て/割り当て解除の数の最小化が懸念される場合は、固定サイズのブロックを割り当ててから、それらのブロック内のメモリを自分で管理できます。これが私が過去にやったことです：

  • テキストは文字のブロックとして格納されますが、ドキュメント全体に対して 1 つの連続したブロックを保持するのではなく、常に 4KB (つまり、4K のシングルバイト文字または 2K の WCHAR) が割り当てられるブロックのリンク リストを維持します。つまり、テキストは配列のリンク リストとして格納され、各配列は一定のサイズに割り当てられます。

  • 各ブロックは、そのブロック内で使用されている/空いているスペース (つまり、文字) の量を追跡します。

  • 1 つまたは複数の文字を挿入するときに、現在のブロックにスペースがあれば、そのブロック内でメモリをシフトするだけです (割り当て/割り当て解除は必要ありません)。現在のブロックに使用可能なスペースがなく、隣接するブロックにスペースがある場合は、既存のブロック間でメモリをシフトするだけです (割り当て/割り当て解除は必要ありません)。両方のブロックがいっぱいになった場合にのみ、新しい 4KB ブロックを割り当て、リンク リストの適切な位置に追加します。

  • 1 つまたは複数の文字を削除する場合、ドキュメント テキスト全体ではなく、メモリ (最大 4KB) をシフトするだけで済みます。また、完全に空になったブロックの割り当てを解除して削除する必要がある場合もあります。

  • また、適切なタイミングで空き領域を結合する「ガベージ コレクション」も行います。これはかなり簡単で、あるブロックから別のブロックにキャラクターを移動して、一部のブロックを空にして削除できるようにする必要があります。

OS および/またはランタイム ライブラリの観点からは、割り当て/解放はすべて同じサイズ (4KB) であるため、断片化はありません。そして、そのメモリの内容を管理しているため、メモリの内容をシフトして無駄なスペースをなくすことで、割り当てられたスペース内での断片化を回避できます。もう 1 つの利点は、alloc/dealloc 呼び出しの数を最小限に抑えることです。これは、使用しているアロケーターによってはパフォーマンスの問題になる可能性があります。つまり、これは速度とサイズの両方の最適化です。それはどのくらいの頻度で行われるのでしょうか? :-)

于 2011-09-02T19:30:59.270 に答える
1

ヒープの断片化については心配しません。現代のヒープマネージャーは、それをうまく処理できます。

ただし、データの局所性が低いことを心配するかもしれません。リンクされたリスト (特に std::list のような非侵襲的なリスト) 内の個別の割り当てとして各グリフを使用すると、ドキュメントを通過するあらゆる種類のパスが、キャッシュに適していない可能性のある方法でメモリ全体にジャンプします。

テキスト エディターは、一見したよりも難しいものです。テキストのブロックや構造化ドキュメントを表すための特殊なデータ構造が数多くあります。それらはそれぞれ、さまざまなタイプの操作に最適化されています。それらの説明を検索してから、最も実行する必要がある操作の種類を検討することをお勧めします.

この論文は古いですが、多くの優れた情報があります: http://www.cs.unm.edu/~crowley/papers/sds.pdf

于 2011-09-02T19:49:59.500 に答える