C# で注意すること

Tuple の == は ReferenceEquals

Tuple.Create(1, 5) == Tuple.Create(1, 5)); // False ！！！
Tuple.Create(1, 5) == Tuple.Create(2, 5)); // False
Tuple.Create(1, 5).Equals(Tuple.Create(1, 5)); // True
Tuple.Create(1, 5).Equals(Tuple.Create(2, 5)); // False

• 値の一致を見たい場合は Equals を使う
• ValueTuple が使える場合は、可能な限りそちらを使ったほうが良い
  • ValueTuple の場合は == 使っても問題ない

BigInteger.Parse(s) の計算量は O(|s|^2)

var s = new string('1', 100000);
var b = BigInteger.Parse(s); // 数秒かかる

String のデフォルトの比較は重い

var a1 = Enumerable.Range(0, 500000).Select(i => i.ToString()).ToArray();
Array.Sort(a1); // 700 ms ぐらいかかる
var a2 = Enumerable.Range(0, 500000).Select(i => i.ToString()).ToArray();
Array.Sort(a2, StringComparer.Ordinal); // 100 ms ぐらいかかる

• デフォルトだと Culture に基づいた文字列になるのでそもそも Ascii 順になる保証はない
• StringComparer.Ordinal を指定すれば、Ascii 順になり、速度も数倍に鳴る
• この問題起因で Atcoder ABC 155 C 問題で大量に TLE が発生した
  • All Submissions - AtCoder Beginner Contest 155

空の Queue.Clear() の計算量は O(|Capacity|) (.Net Framework)

var queue = new Queue<int>(100000);
for (int i = 0; i < 10000; i++) queue.Clear(); // 数秒かかる

• .Net Core だと修正されている
• Clear() 系は他のコレクションクラスでも 基本 O(size) かかるので O(1) ではないという感覚を持つ必要あり。