【AtCoder】【C#】文字列ソートでパフォーマンスが出ない時の対応
AtCoder Beginner Contest 155 のC問題でTLEがどうしても解決できず、終了後に文字列ソートの方法を変えれば通ることがわかったので、メモを残します。
はじめに
本記事のテーマ
下記問題をC#で解こうとするとちょっと工夫をしないとTLEになってしまいます。これを解決する方法について書きます。
本題
問題概要
- N枚目の上には文字列Sが書かれている
- 最も多く書かれた文字列を辞書順で出力する
今回の実装方針
- Dictionaryで文字列と出現回数をまとめる
- 出現回数が最大となる値を求める
- 出現回数が最大となる文字列をListに格納(Add)
- ListをArrayに変えてSortする(Sortする時に、Sort関数の第二引数にStringComparer.OrdinalIgnoreCaseを指定する)
解説
今回ポイントになるのは、4.です。結論からいうと、下記のように実装しなければ通りません。
Array.Sort(array, StringComparer.OrdinalIgnoreCase);
おそらく、通常は下記のように実装すると思います。ただ、これだとTLEしてしまいます。
Array.Sort(array);
これはなぜかというと、Microsoftのベストプラクティスにも記載があるように、StringComparer.OrdinalIgnoreCaseをつけることでカルチャ(ロケール)に依存した処理にならずパフォーマンスが向上しているとのことです。
今回はこの実装が必須でした。
実装全体は下記です。
実装リンク AtCoder/C.cs at master · chittai/AtCoder · GitHub
感想
非常に悔しいし悲しいのですが、この学びを活かして次につなげたいですね
