5

ドキュメントの表現をメモリに保持する必要があり、これを行う最も効率的な方法を探しています。

仮定

  • ドキュメントは非常に大きく、最大 100MB になる場合があります。
  • 多くの場合、ドキュメントは変更されません (つまり、不必要な前処理をしたくありません)。
  • 通常、変更はドキュメント内で (つまり、ユーザーが入力するにつれて) 互いに非常に近くなります。
  • 変更をすばやく適用できる必要があります (ドキュメント全体をコピーする必要はありません)。
  • 変更は、オフセットと新規/削除されたテキスト (行/列ではなく) に関して適用されます。
  • C# で作業するには

現在の考慮事項

  • データを文字列として格納します。コーディングが簡単で、設定が速く、更新が非常に遅い。
  • 行の配列、適度にコーディングが簡単で、設定が遅く (文字列を行に解析する必要があるため)、更新が高速です (行を挿入して削除するのは簡単ですが、オフセットを見つけるには行の長さを合計する必要があります)。

この種のものには標準アルゴリズムがたくさんあるに違いありません (何百万マイルものディスクの割り当てと断片化ではありません)。

ご意見ありがとうございます。

4

7 に答える 7

5

ファイルをブロックに分割することをお勧めします。ブロックをロードすると、すべてのブロックの長さが同じになりますが、ユーザーがこのブロックを編集すると、各ブロックの長さが変わる場合があります。これにより、ユーザーが先頭に 1 バイトを挿入した場合に 100 メガバイトのデータを移動することを回避できます。

ブロックを管理するには、ブロックだけを - 各ブロックのオフセットと共に - リストにします。ユーザーがブロックの長さを変更した場合、この後のブロックのオフセットのみを更新する必要があります。オフセットを見つけるには、バイナリ検索を使用できます。

ファイルサイズ: 100 MiB
ブロックサイズ: 16 kiB
ブロック: 6400

二分探索を使用してオフセットを見つける (最悪の場合): 13 ステップ
ブロックを変更する (最悪の場合): 16384 バイトのデータをコピーし、6400 のブロック オフセットを更新する ブロックを
変更する (平均的なケース): 8192 バイトのデータをコピーし、3200 のブロック オフセットを更新する

16 kiB のブロック サイズは単なるランダムな例です。おそらくファイル サイズと操作の可能性に基づいてブロック サイズを選択することで、操作のコストのバランスを取ることができます。簡単な計算を行うと、最適なブロック サイズが得られます。

固定サイズのブロックをロードするため、ロードは非常に高速になります。また、数百万の単一行ではなく、数千のブロックを書き込む必要があるため、保存も適切に実行されるはずです。オンデマンドでのみブロックをロードすることでロードを最適化し、変更されたすべてのブロック (コンテンツまたはオフセット) のみを保存することで保存を最適化できます。

最後に、実装もそれほど難しくありません。StringBuilderクラスを使用してブロックを表すことができます。しかし、このソリューションは、ブロック サイズ以上の長さの非常に長い行ではうまく機能しません。これは、多くのブロックを読み込んで小さな部分だけを表示し、残りはウィンドウの左右に配置する必要があるためです。この場合、2 次元のパーティショニング モデルを使用する必要があると思います。

于 2009-05-08T08:26:29.383 に答える
4

Good Math, Bad Math は、テキスト エディターでテキスト ファイルを表現するための標準的な方法を詳述し、実装とパフォーマンスの単純さを比較する、ロープとギャップ バッファーに関する優れた記事を少し前に書きました。一言で言えば、ギャップ バッファー (現在のカーソル位置の直後に空のセクションがある大きな文字配列) が、最も単純で最善の方法です。

于 2009-05-08T10:10:46.357 に答える
3

この論文は役に立つかもしれません --- Data Structures for Text Sequencesは、いくつかの標準アルゴリズムを説明し、実験的に分析し、[とりわけ] ギャップ バッファとピース テーブルを比較します。

FWIW、それはピーステーブルが全体的にわずかに優れていると結論付けています。ただし、net.wisdom はギャップ バッファーを好むようです。

于 2009-07-21T16:37:27.917 に答える
1

Memory Mapped Files (MMF)を参照することをお勧めします。

いくつかのポインタ:

メモリ マップト ファイル .NET

http://msdn.microsoft.com/en-us/library/ms810613.aspx

于 2009-05-08T08:08:30.550 に答える
1

あまり編集しない場合は、行の b ツリーまたはスキップ リスト、またはより大きなブロックを使用します。

とにかくロード時に各キャラクターにアクセスする必要があるため、ロード時に行末を決定する追加のコストはあまりありません。

ノード内の行を簡単に移動できます。

各ノードのテキストの合計の長さがノードに格納され、変更が親ノードまで伝播されます。

各行は、データ配列、開始インデックス、長さ、および容量で表されます。改行/改行はデータ配列に入れられません。行を分割するなどの一般的な操作では、配列への参照を変更するだけで済みます。行を編集するには、容量を超えた場合にコピーが必要です。行を編集するときに、行ごとに同様の構造が一時的に使用される可能性があるため、キーを押すたびにコピーを実行しません。

于 2009-05-08T09:41:39.873 に答える
0

頭のてっぺんから、非常に長い行がない限り、インデックス付きリンクリストはこの種のことにはかなり効率的だと思っていたでしょう。

リンクされたリストは、データを保存し、ユーザーが編集するときに行を追加または削除する効率的な方法を提供します。索引付けにより、ファイル内の特定のポイントにすばやくジャンプできます。この種のアイデアは、編集を小さなアトミック操作に分類するのがかなり簡単であるため、元に戻す/やり直しタイプの操作にも適しています。

私はcrisbのポイントに同意します.

于 2009-05-08T08:16:37.957 に答える
-1

あなたの説明から、あなたのドキュメントはフォーマットされていないテキストのみのように聞こえます-したがって、stringbuilder はうまくいきます。

書式設定されたドキュメントの場合、MS Word API などを使用して、ドキュメント処理をそれらにオフロードする傾向があります。ドキュメントの解析はしばしば a** の苦痛になる可能性があるため、非常に多くの時間を節約できます:- )

私はまだパフォーマンスについて心配する必要はありません - あなたはまだ実装していないように思えます.実際にプロファイリングに取りかかると、実際には複数のドキュメントをメモリに保持する余裕があります。

于 2009-05-08T08:13:10.367 に答える