c# - 文字列の結合と複雑さ?

Question

2 つの文字列を結合する必要がある場合は、String.Format (コード内の複数の場所で発生する場合は StringBuilder) を使用します。

一部の優れたプログラマーは、文字列の結合の複雑さに注意を払わず、'+' 演算子のみを使用しているようです。

「+」演算子を使用すると、アプリケーションがより多くのメモリを使用するようになることはわかっていますが、複雑さはどうでしょうか?

score 8 · Accepted Answer

これは、 Coding Horrorに関するJeff Atwoodによるさまざまな文字列結合方法に関する優れた記事です。

_{（出典：codinghorror.com）}

マイクロ最適化劇場の悲しい悲劇

投稿の要旨はこちら。

[いくつかの文字列結合方法が示されています]

かゆい小さな人差し指をコンパイルキーから離して、このことについて少し考えてみてください。これらの方法のどれがより速くなりますか?

答えはありますか？すごい！

そして.. ドラムロールをお願いします.. 正解:
これ。ただ。しません。案件！

score 5 · Accepted Answer

この回答は、ランタイムの複雑さについて話していることを前提としています。

Using+は新しい文字列オブジェクトを作成します。つまり、古い文字列オブジェクトの両方の内容を新しい文字列オブジェクトにコピーする必要があります。タイトなループなど、大量の連結があると、これは O(n^2) 操作になる可能性があります。

非公式の証明として、次のコードがあるとします。

string foo = "a";
for(int i = 0; i < 1000; i++)
{
    foo += "a";
}

ループの最初の反復では、最初にfoo("a") の内容が新しい文字列オブジェクトにコピーされ、次にリテラル "a" の内容がコピーされます。それが2部です。2 番目の反復には 3 つのコピーがあります。2 つは new からfoo、1 つはリテラル "a" からです。1000 回目の反復では、1001 回のコピー操作が行われます。総部数は2 + 3 + ... + 1001です。一般に、ループ内で反復ごとに 1 文字のみを連結する場合 (そして 1 文字の長さから開始する場合)、反復回数が n の場合、2 + 3 + ... + n + 1コピーが存在します。1 + 2 + 3 + ... + n = n(n+1)/2 = (n^2 + n)/2これは O(n^2) と同じです。

score 1 · Accepted Answer

複雑さの観点から、フォーマット文字列を解析するために新しく作成された文字列の繰り返しを交換すると思います。たとえば"A" + "B" + "C" + "D"、「ABCD」を作成するには、「A」、「AB」、最後に「ABC」をコピーする必要があることを意味します。コピーは繰り返しですよね？したがって、たとえば、1,000 文字の文字列を 1,000 個の文字列と合計すると、(1,000+N) 個の文字列を 1,000 回コピーすることになります。最悪の場合、O(n^2) の複雑さにつながります。

解析を考慮してもStrin.Fomat、およびStringBufferは O(n) 前後である必要があります。

score 1 · Accepted Answer

複数のステップで大きな文字列を作成する場合は、StringBuilder を使用する必要があります。また、最終的にどのくらいの大きさになるかを知っている場合は、必要なサイズで初期化して、再割り当てのコストがかかるのを防ぐことができます。小さな操作の場合、 + 演算子を使用してもパフォーマンスが大幅に低下することはなく、コードがより明確になります (そして、より速く記述できます...)。

score 1 · Accepted Answer

文字列は Java や C# などの言語では不変であるため、2 つの文字列が連結されるたびに新しい文字列を作成する必要があり、その中に 2 つの古い文字列の内容がコピーされます。

平均して c 文字の長さの文字列を想定します。

最初の連結では 2*c 文字だけをコピーする必要がありますが、最後の連結では最初の n-1 文字列 (長さは (n-1)*c 文字) の連結と、最後の連結そのものをコピーする必要があります。長さ c 文字、合計 n*c 文字。n 連結の場合、これは n^2*c/2 文字のコピーを作成します。これは、O(n^2) のアルゴリズムの複雑さを意味します。

ただし、実際にはほとんどの場合、この二次的な複雑さは目立ちません (Robert C. Cartaino がリンクしているブログエントリで Jeff Atwood が示しているように)。できるだけ読みやすいコードを書くことをお勧めします。

ただし、問題になる場合があり、そのような場合に O(n^2) を使用すると致命的な場合があります。

実際には、base64 でエンコードされた画像を含む大きな Word XML ファイルをメモリ内に生成する場合などに、これを見てきました。この生成には、O(n^2) 文字列連結を使用していたため、10 分以上かかっていました。+ を使用した連結を StringBuilder に置き換えた後、同じドキュメントの実行時間が 10 秒未満に短縮されました。

同様に、連結に + を使用して、非常に大きな SQL コードを文字列として生成するソフトウェアを見たことがあります。これが完了するまで待っていませんでした（すでに1時間以上待っていました）が、StringBuilderを使用して書き直しました。この高速バージョンは 1 分以内に完了しました。

要するに、最も読みやすく/最も書きやすいことは何でも行い、これについては、非常に巨大な文字列を作成するときにのみ考えてください:-)

score 1 · Accepted Answer

アプリケーションが非常に文字列を多用するものでない限り (プロファイル、プロファイル、プロファイル!)、これは実際には問題になりません。優れたプログラマーは、平凡な操作のパフォーマンスよりも読みやすさを優先します。

score 1 · Accepted Answer

状況によります。+ を使用すると、コードの複雑さが軽減される場合があります。次のコードを検討してください。

output = "<p>" + intro + "</p>";

それは良い、明確な線です。String.Format は必要ありません。

score 1 · Accepted Answer

+ を 1 回だけ使用すると、それによる不利益はなく、可読性が向上します (Colin Pickard が既に述べたように)。

私が知る限り + の意味: 左オペランドと右オペランドを取り、それらを新しいバッファにコピーします (文字列は不変であるため)。

したがって、+ を 2 回使用します (Colin Pickards の例のように、既に 2 つの一時的な文字列を作成しています。最初に"<p>"イントロに追加するとき、次に"</p>"新しく作成された文字列に追加するときに.

いつどの方法を使用するかを自分で検討する必要があります。上記のような小さな例であっても、intro が十分な長さの文字列である場合、パフォーマンスの低下が深刻になる可能性があります。

score 0 · Accepted Answer

私はこれをずっと前にベンチマークしましたが、.NET1.0または1.1以降は実際には違いはありません。

当時、文字列を数百万回連結するコード行にヒットするプロセスがある場合は、String.Concat、String.Format、またはStringBuilderを使用することで速度を大幅に向上させることができました。

今ではまったく問題ではありません。とにかく.Net2.0が出て以来、少なくともそれは問題ではありませんでした。あなたが読みやすいようにそれをあなたの心とコードから外してください。

score 0 · Accepted Answer

コンパイラは最適化します: "a" + "b" + "c" は String.Concat メソッドに置き換えられます (修正されたコメントとして String.Format ではありません)

score 0 · Accepted Answer

すでに多くの意見がありますが、パフォーマンスの問題に取り組む最善の方法は、すべての実行可能なソリューションのパフォーマンスの違いを理解し、パフォーマンス要件を満たすソリューションについて、最も信頼性が高く、最も優れたソリューションを選択することであると常に感じてきました。サポート可能。

複雑さを理解するために Big O 表記を使用する人はたくさんいますが、ほとんどの場合 (どの文字列連結方法が最も効果的かを理解することを含めて)、単純なタイムトライアルで十分であることがわかりました。100,000 回の反復のループで strA+strB と strA.Append(strB) を比較して、どちらがより速く動作するかを確認してください。

c# - 文字列の結合と複雑さ?

12 に答える 12

これ。ただ。しません。案件！

Related

Reference