.Net / C＃での文字列の展開について

文字列について、または.Net / C＃で文字列を反転することについて話しましょう。 たまたま標準ライブラリでは、対応する関数が観察されていません。 そして、彼らが私に言ったように、行反転関数を書くことは、就職の面接でかなり一般的な質問です。 このプラットフォームを使用して、効果的にラインを反転できる方法を見てみましょう。



カットの下には、ライン反転のさまざまな方法のパフォーマンスの比較分析があります。







Khrr-rr ...-チェーンソーは言った。

Tyuyuyu ...-男性は言った。

©古いジョーク。



さあ、始めましょう。 すべての実装は、サイズが256メガバイト（128×1024×1024文字）の単一行と256バイト（128文字）の1024×1024行で速度がテストされました。 各測定の前に、ガベージコレクションが加速され（このようなサイズのテストデータで重要です）、測定が50回実行され、20の極端なものが破棄され、残りの値が平均化されました。 条件付きオウムは、ストップウォッチクラスのオブジェクトによって発行されたティックの数を選択しました。



このテストは、Athlon64 x2 4200 +、2GBデュアルチャンネルDDR2 RAMおよびPentium4 HT 3GHz、3GB DDR RAMの2台のコンピューターで実行されました。 このテストの構成の主な違いは、メモリキャッシュバンドルのパフォーマンスです。2番目のシステムは、この点で著しく低速です。



技術的な手続きは終わりました。実際の実装に移りましょう。 明確にするために、ここではユニコードのサロゲートコードポイントは考慮されていません。 周囲の「エコシステム」のコンテキストで、ロジックと実装の「可愛さ」の順にアプローチを検討します。



このノートの最後の部分に、比較測定値があります。 一般に、 ReverseUnsafeCopy関数は、安全なコード-ReverseArrayManualが制限されている場合にのみ最適であることが判明しました。 安全なコードと巨大な文字列が必要な場合、 ReverseStringBuilderで苦しむ必要があります。

パート1：「通常の」メソッド。

1. ReverseStringBuilder

推奨事項に従い、「大きな」文字列を作成するために、特別なツールStringBuilderクラスを使用します。 アイデアは恐ろしいほど単純です。適切なサイズのビルダーを作成し、逆の順序で行に沿って移動し、新しい行に文字を追加します。

Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }

1. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
   
   
   
   
2. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
   
   
   
   
3. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
   
   
   
   
4. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
   
   
   
   
5. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
   
   
   
   
6. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
   
   
   
   
7. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
   
   
   
   

私たちは試して、起動します、はい...それはすべて何らかの形で何らかの形でゆっくり動作します。

2. ReverseArrayFramework

ハ！ したがって、このビルダーには、すべての側面からスレッドの安全性を確保するためのチェックが装備されています。いいえ、これは必要ありません。 しかし、文字列は文字の配列です。 裏返して、結果を文字列に変換します。

Copy Source | Copy HTML

1. 静的文字列 ReverseArrayFramework（ 文字列 str）
2. {
3. char [] arr = str.ToCharArray（）;
4. 配列 .Reverse（arr）;
5. 新しい 文字列 （arr）を返します。
6. }

まったく別の問題で、3.5倍高速でした。 うーん、多分もっといい？

3. ReverseArrayManual

だから、私たちは思う。 最初に、データが2回コピーされます。最初は文字列から配列に、次に配列内にコピーされます。 次に、Array.Reverseはライブラリメソッドです。つまり、入力チェックがあります。 さらに、アトミックタイプの場合、ネイティブメソッドとして明示的に実装され、これは実行コンテキストの追加の切り替えです。 文字列を手動で配列に変換してみましょう。

Copy Source | Copy HTML

1. 静的文字列 ReverseArrayManual（ string originalString）
2. {
3. char [] reverseCharArray = new char [originalString.Length];
4. for （ int i = originalString.Length- 1 ; i> -1 ; i--）
5. ReverseCharArray [originalString.Length-i- 1 ] = originalString [i];
6. 新しい文字列を返します （reversedCharArray）;
7. }

4. ReverseManualHalf

どうぞ この場合、アクションは行の中央に対して対称です。つまり、2つのインデックスを反対方向に配置し、反復回数を半分にすることができます。

Copy Source | Copy HTML

1. 静的文字列 ReverseManualHalf（ string originalString）
2. {
3. char [] reverseCharArray = new char [originalString.Length];
4. int i = 0 ;
5. int j = originalString.Length- 1 ;
6. while （i <= j）
7. {
8. reverseCharArray [i] = originalString [j];
9. reverseCharArray [j] = originalString [i];
10. i ++; j--;
11. }
12. 新しい文字列を返します （reversedCharArray）;
13. }

うーん...何かがうまくいかなかった、遅いメモリのシステムで、速度が1.5倍落ちた。 構成と実装の詳細を考えると、メモリ速度とプロセッサキャッシュが原因であると考えることができます。以前は2つのリモートメモリ領域を同時に操作していましたが、現在はそれぞれ4つあり、データキャプチャはより頻繁に実行されます。

LINQと逆の方法

LINQにはまだ比較的美しく短い方法がありますが、パフォーマンスに関する批判に耐えることはできません。StringBuilderに基づく方法よりも3〜3.5倍遅く動作します。 この理由は、IEnumerableを介したデータのポンピングと各反復の仮想呼び出しです。 ご希望の方には、以下が実装です。

Copy Source | Copy HTML

1. 静的文字列 ReverseStringLinq（ string originalString）
2. {
3. 新しい文字列を返します （originalString.Reverse（）。ToArray（））;
4. }

メモリ使用量

ほとんどの場合、問題はそれほど重大ではありませんが、考慮されるメソッドのすべての「高速」は、文字の配列の形式で文字列の中間コピーを作成します。 合成テストでは、これは最初のメソッドのみが512MBの文字列をラップでき、残りはSystem.OutOfMemoryExceptionになったという事実に現れています。 また、不必要な一時オブジェクトがGCの頻度を増やすことを忘れてはなりません。それは恐怖のポイントに最適化されていますが、とにかく時間を浪費します。 次のパートでは、速度の最適化に加えて、この問題の解決策も探します。

パート2：より速く、より効率的に、または安全でないコードが必要な場合。

安全でないコードを使用すると、1つの興味深い利点が得られます。以前は不変であった行を変更できるようになりましたが、非常に注意して行のコピーのみを変更する必要があります-ライブラリは1行のコピーの数を最小限に抑えます。アプリケーション。



したがって、適切なサイズの新しい行を作成したら、それを配列として見て、必要なデータを入力できます。 さて、インデックスの有効性のチェックがないことを忘れないでください。これによりコードの速度も上がります。 ただし、.Netの文字列の仕様により、目的の長さの文字列を作成することはできません。 String（char、int）コンストラクターを使用して、繰り返し文字（スペースなど）からストリングを作成するか、String.Copy（String）を使用して元のストリングをコピーできます。



この知識を武器に、次の2つの実装を作成します。

5. ReverseUnsafeFill

スペースの行を作成し、逆の順序で埋めます。

Copy Source | Copy HTML

1. 静的な安全でない文字列 ReverseUnsafeFill（ 文字列 str）
2. {
3. if （str.Length <= 1 ）strを返す ;
4. String copy = new String （ '' 、str.Length）;
5. 修正 （ char * buf_copy = copy）
6. {
7. 修正 （ char * buf = str）
8. {
9. int i = 0 ;
10. int j = str.Length- 1 ;
11. while （i <= j）
12. {
13. buf_copy [i] = buf [j];
14. buf_copy [j] = buf [i];
15. i ++; j--;
16. }
17. }
18. }
19. コピーを返す ;
20. }

6. ReverseUnsafeCopy

行をコピーして反転します。

Copy Source | Copy HTML

1. 静的な安全でない文字列 ReverseUnsafeCopy（ 文字列 str）
2. {
3. if （str.Length <= 1 ）strを返す ;
4. char tmp;
5. String copy = String .Copy（str）;
6. 修正 （ char * buf = copy）
7. {
8. char * p = buf;
9. char * q = buf + str.Length- 1 ;
10. while （p <q）
11. {
12. tmp = * p;
13. * p = * q;
14. * q = tmp;
15. p ++; q--;
16. }
17. }
18. コピーを返す ;
19. }

測定結果が示すように、2番目のバージョンは、低速メモリでははるかに速く動作し、高速ではわずかに遅くなります:)いくつかの理由があります：4つではなく2つのリモートメモリ領域で動作し、メモリブロックのコピー速度とループの単純な充填速度の違い フルパスでReverseUnsafeFillバージョンを作成して（メモリからキャッシュへのデータキャプチャの数を減らすことができます）、遅いメモリでテストすることができますが、ReverseUnsafeCopyよりも遅いと信じる理由があります（間違っている可能性があります）。

7. ReverseUnsafeXorCopy

次は？ うわさによると、XOR演算子との交換は、 3番目の変数をコピーするよりも高速に動作します（ちなみに、長所では「a ^ = b ^ = a ^ = b;」、C＃では、この行は機能しません） 。 さて、実際に確認しましょう。

Copy Source | Copy HTML

1. 静的な安全でない文字列 ReverseUnsafeXorCopy（ string str）
2. {
3. if （str.Length <= 1 ）strを返す ;
4. String copy = String .Copy（str）;
5. 修正 （ char * buf = copy）
6. {
7. char * p = buf;
8. char * q = buf + str.Length- 1 ;
9. while （p <q）
10. {
11. * p ^ = * q;
12. * q ^ = * p;
13. * p ^ = * q;
14. p ++; q--;
15. }
16. }
17. コピーを返す ;
18. }

その結果、コピーよりも1.2〜1.5倍遅くなります。 レジスタの値をすばやく交換するために機能するトリックは、変数に対しては機能しませんでした（多くのC / C ++コンパイラでは機能しません）。



この事実の説明を求めて、アプリケーションの内部に登り、結果のCILコードを読み取ります。

パート3：CILおよび.Netライブラリコードに進みます。

XORによる交換がより悪いことが判明した理由

この質問への回答については、2つの交換方法用に生成されたCILコードを見る価値があります。 これらの命令を理解しやすくするために、その目的を説明します。ldloc.N-スタックにローカル変数番号Nをロードし、 stloc .N-スタックの先頭をローカル変数番号Nに読み込みますxor-スタックの先頭にある2つの値のXOR演算の値を計算し、結果を読み込みます代わりにスタックに。

コピー共有	XORベースの交換	完全なCIL交換
int a、b; int tmp = a; a = b; b = tmp;	int a、b; a ^ = b; b ^ = a; a ^ = b;
.locals init (<br/> [0] int32 a,<br/> [1] int32 b,<br/> [2] int32 tmp)	.locals init (<br/> [0] int32 a,<br/> [1] int32 b)<br/>	.locals init (<br/> [0] int32 a,<br/> [1] int32 b)<br/>
L_0004: ldloc .0<br/> L_0005: stloc .2<br/> L_0006: ldloc .1<br/> L_0007: stloc .0<br/> L_0008: ldloc .2<br/> L_0009: stloc .1<br/> <br/> <br/> <br/> <br/> <br/>	L_0004: ldloc .0<br/> L_0005: ldloc .1<br/> L_0006: xor <br/> L_0007: stloc .0<br/> L_0008: ldloc .1<br/> L_0009: ldloc .0<br/> L_000a: xor <br/> L_000b: stloc .1<br/> L_000c: ldloc .0<br/> L_000d: ldloc .1<br/> L_000e: xor <br/> L_000f: stloc .0<br/>	L_0004: ldloc .0<br/> L_0005: ldloc .1<br/> L_0006: stloc .0<br/> L_0007: stloc .1<br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/>

ご覧のとおり、XOR演算子を使用したバージョンでは、より多くの仮想マシン操作が必要です。 さらに、その後のネイティブコードへのコンパイル時に、使用されるプロセッサの能力を考慮して、3番目の変数を介した一般的な交換をより効率的な交換操作に置き換える最適化が行われる可能性があります。 分析の副作用として、CILの仮想的な「理想的な」交換が行われます。CILの使用に何らかの効果があるかどうかを確認するのは興味深いでしょうが、このためにilasmまたは反射/放出を台無しにする必要があります。 ただし、結果のコードは安全ではないc＃よりも適用性が低いため、実用的な関心はありません。

Array.Reverseはどのように機能しますか？

さて、リフレクターを使用してアセンブリの内部を見ると、最初の部分で使用されるライブラリメソッドの実装を見るのが理にかなっています。 ここではArray.Reverseが際立っており、ネイティブメソッドとして実装された特定の関数Array.TrySZReverseに依存しています。 したがって、 Shared Source Common Language Infrastructure 2.0 -source .net 2.0をダウンロードして、どんな種類の獣かを確認してください:)短い検索の後、ファイル「sscli20 \ clr \ src \ vm \ comarrayhelpers.h」にリバーステンプレート関数があります（これにはKINDのケースはUINT16）に対応しますが、これは（驚き！）ReverseUnsafeCopy実装と恐ろしく似ています。

Copy Source | Copy HTML

1. static void Reverse（ KIND配列[]、 UNIT32インデックス、 UNIT32カウント）{
2. LEAF_CONTRACT;
4. _ASSERTE（array！= NULL）;
5. if （count == 0）{
6. 帰る
7. }
8. UNIT32 i =インデックス。
9. UNIT32 j =インデックス+カウント-1 ;
10. while （i <j）{
11. KIND temp = array [i];
12. 配列[i] =配列[j];
13. 配列[j] = temp;
14. i ++;
15. j--;
16. }
17. }

パート4：バイナリマラソンの結果。

測定結果の分析は最初の2つの部分で行いますが、ここでは上記の機能の性能比を示す比較図のみを示します。 「ティック」の正確な数値は構成に依存しすぎており、特に関心を引くことはほとんどありません。誰もが提供されたコードを使用して自分のパフォーマンスを測定できます。

最初の2つの部分のベストプラクティスの比較

高速メモリ上



遅いメモリ

高速メモリでのデバッグおよびリリース構成のすべてのメソッドの比較

大きな線



短い線

低速メモリでのデバッグおよびリリース構成のすべてのメソッドの比較

大きな線



短い線