.NET Micro Framework で文字置換を高速に行うには
先日「.NET Micro Framework で string.Replace 文字列置換を使うには」で紹介したCommon ExtensionsのReplaceメソッドですが、結構時間がかかります。
あまりに置換の数が多いと、動作に支障がでるので、ここでは一文字（char）に限って高速に置換できるメソッドを実装します。といっても単純ですが。
ちなみに実行環境は Netduino Plus、.NET Micro Framework 4.1 です。
スポンサーリンク
目次
Replaceの概要とStringBuilderの問題
Common ExtensionsのReplaceメソッドは引数にstring型の文字列を2つとります。こんな感じで。
|
1 |
text.Replace("A", "B"); |
これで “A” を “B” という文字列に置き換えてくれます。内部的には同じCommon Extensionsに含まれるStringBuilderクラスを使っているようです。
問題は、textの中に含まれる “A” の数にもよりますが、数十ミリ秒～数百ミリ秒はかかってしまうことです。
原因はこのStringBuilderです。単純な文字列結合より高速なパフォーマンスがでてほしいのですが、特に結合回数が少ない場合はこのNetMf.CommonExtensions.StringBuilderはstringの+演算子より遅いです。
試しに “a” という1バイトの文字列と、”abc” という3バイトの文字列をどんどん結合していく（どんどん後ろに足していく）テストをしたところ、下記のようになりました。
| 回数 | 所要時間 [ms] | |||
|---|---|---|---|---|
| 1文字 “a” | 3文字 “abc” | |||
| string += | StringBuilder | string += | StringBuilder | |
| 100 | 15 | 50 | 19 | 54 |
| 200 | 35 | 100 | 54 | 106 |
| 300 | 60 | 152 | 105 | 158 |
| 400 | 90 | 201 | 172 | 215 |
| 500 | 125 | 251 | 260 | 270 |
| 600 | 164 | 303 | 372 | 327 |
| 700 | 209 | 353 | 491 | 386 |
| 800 | 257 | 403 | 606 | 443 |
| 900 | 305 | 452 | 779 | 498 |
| 1000 | 362 | 504 | 957 | 562 |
ご覧のとおり、1バイトの結合では、stringの結合のほうが速いです。ただ、3バイトになると600回ぐらいからStringBuilderが追い抜きます。しかし、普通は500回も繰り返すことはないと思うので、いずれにしろ単純なstringの結合でよさそうですね。
ということで、内部的にStringBuilderを使っているため、Replaceも遅いのは仕方ないようです。
1バイト置換専用のReplaceを作る
とはいえ、たとえばURLに含まれたスラッシュ “/” をパスのバックスラッシュ “\” に変換したい場合など、1文字を置き換えたいことも多いです。このときにいちいち上記のReplaceメソッドを使っていたのでは、オーバーヘッドが大きくなりすぎてしまいます。
そこで、1バイトのみ置換する用のReplaceメソッドを拡張メソッドで作成しました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public static class StringExt { /// <summary> /// 指定した文字を別の文字で置き換えます。 /// </summary> /// <param name="s"></param> /// <param name="a">検索する文字</param> /// <param name="b">置換する文字</param> /// <returns>置換後の文字列</returns> public static string Replace(this string s, char a, char b) { var arr = s.ToCharArray(); for (int i = 0; i < arr.Length; i++) { if (arr[i] == a) { arr[i] = b; } } return new string(arr); } } |
引数の型はchar型にしてあるので、既存の（CommonExtensionsの）Replaceとは競合しないはず。実装としては非常に単純で一旦char配列に変換して、配列の要素を置換後、再びstringに戻して返す、というだけです。
使うときはこんな感じ。char型なのでシングルクォーテーション ‘ になっていることに注意。
|
1 |
test.Replace('a', 'A'); |
で、せっかくなのでこれらもベンチマークをとりました。
| 置換個数 | 所要時間 [ms] | |||
|---|---|---|---|---|
| CommonExtensionsの Replace |
char専用 Replace |
|||
| 100 | 453 | 30 | ||
| 200 | 1534 | 61 | ||
| 300 | 3237 | 89 | ||
| 400 | 5574 | 121 | ||
| 500 | 8639 | 150 | ||
うーん、劇的に違いますね。これでずいぶん快適になりました。500個置換して150msならさほど問題にならないでしょう。
最後までお読みいただきありがとうございました m(_ _)m
ベンチマーク用のソースコード
最後に今回ベンチマークに使ったソースを載せておきます。参考まで。
Stopwatchは経過時間を計測するだけのクラスなので、適当に作ってください。
StringBuilder と string += 比較用
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
for (int n = 0; n <= 10; n++) { Stopwatch sp1 = new Stopwatch(); Stopwatch sp2 = new Stopwatch(); sp1.Start(); string test = ""; for (int i = 0; i < n*100; i++) { test += "a"; } sp1.Stop(); sp2.Start(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < n*100; i++) { sb.Append("a"); } test = sb.ToString(); sp2.Stop(); Debug.Print(n +"\t"+ sp1.ElapsedMilliseconds.ToString() + "\t" + sp2.ElapsedMilliseconds.ToString()); Debug.GC(true); } |
1000バイト単位の文字列操作を繰り返しているとすぐにOutOfMemoryExceptionが発生するので、1ループごとにDebug.GCで強制的にガベージコレクトさせています。
CommonExtensionsのReplaceと自作Replace比較用
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
for (int n = 0; n <= 5; n++) { string test = ""; for (int i = 0; i < n*100; i++) { test += "abc"; } Stopwatch sp1 = new Stopwatch(); Stopwatch sp2 = new Stopwatch(); sp1.Start(); string t1 = test.Replace("a", "A"); sp1.Stop(); sp2.Start(); string t2 = test.Replace('a', 'A'); sp2.Stop(); Debug.Print(n + "\t" + sp1.ElapsedMilliseconds.ToString() + "\t" + sp2.ElapsedMilliseconds.ToString()); } |
スポンサーリンク
関連記事
