3

私はこの質問が行われたことを知っていますが、少し違ったひねりを加えています。これは時期尚早の最適化であると指摘する人もいますが、実用性と実用性のみを求めているのであれば、これは完全に真実です。私の問題は実際的な問題に根ざしていますが、それでもまだ興味があります。

データベーススキーマ（簡単に何百ものテーブル、ビューなど）を再作成するためのスクリプトを作成する（ディスクに保存されるように）一連のSQLステートメントを作成しています。これは、私の文字列連結が追加専用であることを意味します。MSDN によると、StringBuilder は、内部バッファー (確実に char[]) を保持し、文字列文字をそこにコピーして、必要に応じて配列を再割り当てすることで機能します。

ただし、私のコードには多くの繰り返し文字列 ("CREATE TABLE ["、"GO\n" など) があります。つまり、それらがインターンされていることを利用できますが、毎回コピーされるため、StringBuilder を使用する場合はそうではありません。唯一の変数は、本質的にテーブル名であり、既にメモリ内にある他のオブジェクトの文字列として既に存在しています。

つまり、データが読み込まれ、スキーマ情報を保持するオブジェクトが作成された後、すべての文字列情報をインターンによって再利用できるということです。

それを仮定すると、インターンされた文字列へのポインターを保持するため、文字列の List または LinkedList の方が高速ではないでしょうか? 次に、正確に正しい長さの文字列全体の単一のメモリ割り当てに対して String.Concat() を 1 回呼び出すだけです。

リストはインターンされたポインターの string[] を再​​割り当てする必要があり、リンクされたリストはノードを作成してポインターを変更する必要があるため、「自由に」行うことはできませんが、何千ものインターンされた文字列を連結している場合、それらは彼らがより効率的であるように。

ここで、各 SQL ステートメントの文字カウントに関するヒューリスティックを考え出し、各タイプをカウントして、大まかなアイデアを得て、char[] の再割り当てを避けるために StringBuilder の容量を事前に設定できると思いますが、かなりのマージンでオーバーシュートする必要があります。再割り当ての可能性を減らします。

したがって、この場合、連結された単一の文字列を取得するのに最も速いのは次のとおりです。

  • StringBuilder
  • インターンされた文字列の List<string>
  • インターンされた文字列の LinkedList<string>
  • 容量ヒューリスティックを使用した StringBuilder
  • 他の何か？

上記に対する別の質問(私は常にディスクにアクセスするとは限りません) として: 出力ファイルへの単一の StreamWriter はさらに高速でしょうか? または、List または LinkedList を使用してから、最初にメモリ内で連結する代わりに、リストからファイルに書き込みます。

編集: 要求に応じて、MSDN への参照(.NET 3.5)。「空きがある場合は新しいデータがバッファの末尾に追加されます。そうでない場合は、新しい大きなバッファが割り当てられ、元のバッファのデータが新しいバッファにコピーされ、新しいデータが新しいバッファに追加されます。バッファ。" 私にとっては、それを大きくするために再割り当てされた char[] を意味し (古いデータをサイズ変更された配列にコピーする必要があります)、追加します。

4

7 に答える 7

3

別の質問については、Win32 にはWriteFileGather関数があり、(インターンされた) 文字列のリストをディスクに効率的に書き込むことができますが、非同期で呼び出された場合にのみ大きな違いが生じます。

あなたの主な質問について: メガバイトのスクリプトまたは数万のスクリプトに達しない限り、心配しないでください。

StringBuilder は、再割り当てごとに割り当てサイズを 2 倍にすることが期待できます。つまり、バッファを 256 バイトから 1MB に増やすと、再割り当ては 12 回にすぎません。最初の見積もりが目標から 3 桁ずれていたことを考えると、かなり良い結果です。

純粋に演習として、いくつかの見積もり: 1MB のバッファを構築すると、およそ 3MB のメモリがスイープされます (1MB のソース、1MB のターゲット、再割り当て中のコピーによる 1MB)。

リンクされたリストの実装は、約 2MB をスイープします (これは、文字列参照ごとに 8 バイト/オブジェクトのオーバーヘッドを無視しています)。したがって、10Gbit/s の一般的なメモリ帯域幅と 1MB L2 キャッシュと比較して、1 MB のメモリ読み取り/書き込みを節約できます。)

はい、リストの実装は潜在的に高速であり、バッファーが桁違いに大きい場合、違いは問題になります。

小さな文字列のより一般的なケースでは、アルゴリズムの利点は無視でき、他の要因によって簡単に相殺されます。StringBuilder コードは既にコード キャッシュにある可能性が高く、マイクロ最適化の実行可能なターゲットです。また、文字列を内部的に使用すると、最終的な文字列が最初のバッファーに収まる場合、コピーがまったく行われないことを意味します。

リンクされたリストを使用すると、再割り当ての問題も O(文字数) から O(セグメント数) に減少します。文字列参照のリストは、文字列と同じ問題に直面します!

したがって、IMO の StringBuilder の実装は正しい選択であり、一般的なケースに最適化されており、予想外に大きなターゲット バッファーの場合はほとんどが低下します。リストの実装は最初に非常に多くの小さなセグメントで劣化すると予想されますが、これは実際には StringBuilder が最適化しようとしている極端な種類のシナリオです。

それでも、2 つのアイデアを比較してみるのは興味深いことです。

于 2009-05-02T23:47:14.103 に答える
3

このようなものを実装していた場合、StringBuilder (またはスクリプトのメモリ バッファー内の他のもの) を構築することはありません。代わりにファイルにストリーミングして、すべての文字列をインラインにします。

疑似コードの例を次に示します (構文的に正しくないなど)。

FileStream f = new FileStream("yourscript.sql");
foreach (Table t in myTables)
{
    f.write("CREATE TABLE [");
    f.write(t.ToString());
    f.write("]");
    ....
}

そうすれば、文字列のすべてのコピーを使用して、スクリプトのメモリ内表現が必要になることはありません。

意見？

于 2009-05-02T20:30:37.570 に答える
2

私の経験では、適切に割り当てられた StringBuilder は、大量の文字列データに対して他のほとんどすべてよりも優れています。再割り当てを防ぐために、見積もりを 20% または 30% オーバーシュートすることによって、いくらかのメモリを浪費する価値があります。現在、私自身のデータを使用してそれをバックアップするための難しい数字はありませんが、詳細についてはこのページをご覧ください。

ただし、Jeff が好んで指摘しているように、時期尚早に最適化しないでください。

編集: @Colin Burnett が指摘したように、Jeff が実施したテストは Brian のテストと一致しませんが、Jeff の投稿をリンクするポイントは、一般的に時期尚早の最適化に関するものでした。Jeff のページの何人かのコメント投稿者は、彼のテストの問題を指摘しました。

于 2009-05-01T18:19:55.100 に答える
1

連結されるすべて（またはほとんど）の文字列がインターンされている場合、使用するメモリが大幅に少なくなり、いくつかの大きな文字列コピーを節約できるため、スキームによってパフォーマンスが向上する可能性があります。

ただし、実際にパフォーマンスが向上するかどうかは、処理するデータの量によって異なります。これは、アルゴリズムの大きさの順序ではなく、一定の要因によるものであるためです。

実際に伝える唯一の方法は、両方の方法を使用してアプリを実行し、結果を測定することです。ただし、メモリに大きな負荷がかかり、バイトを節約する方法が必要でない限り、私は気にせず、文字列ビルダーを使用します。

于 2009-05-01T18:46:33.947 に答える
1

Aはデータの格納にStringBuildera を使用せず、内部の可変文字列を使用します。char[]つまり、文字列のリストを連結するときと同じように、最終的な文字列を作成するための追加の手順はなくStringBuilder、内部文字列バッファーを通常の文字列として返すだけです。

が容量を増やすために行う再割り当てはStringBuilder、データが平均で 1.33 回余分にコピーされることを意味します。を作成するときにサイズを適切に見積もることができれば、StringBuilderそれをさらに減らすことができます。

ただし、全体像をつかむために、最適化しようとしているものを確認する必要があります。プログラムで最も時間がかかるのは、実際にデータをディスクに書き込むことです。そのため、文字列処理を a を使用する場合の 2 倍の速さで最適化できたとしてもStringBuilder(これはほとんどありません)、全体的な違いは依然として数パーセント。

于 2009-05-01T18:52:52.510 に答える
0

これについてC++を検討しましたか？できればC++で記述されたT/SQL式を既に構築しているライブラリクラスはありますか。

文字列で最も遅いのはmallocです。32ビットプラットフォームでは、文字列ごとに4KBかかります。作成される文字列オブジェクトの数を最適化することを検討してください。

C＃を使用する必要がある場合は、次のようなものをお勧めします。

string varString1 = tableName;
string varString2 = tableName;

StringBuilder sb1 = new StringBuilder("const expression");
sb1.Append(varString1);

StringBuilder sb2 = new StringBuilder("const expression");
sb2.Append(varString2);

string resultingString = sb1.ToString() + sb2.ToString();

perfが非常に重要な場合は、依存性注入フレームワークを使用してオブジェクトをインスタンス化するための最適なパスをコンピューターに評価させることもできます。

于 2009-05-02T17:10:47.863 に答える