123. C# でBitSetを自作した話と、C# の定数倍高速化について少し
昨日の ABC258-G問題で BitSet という（C++の）データ構造を利用する想定の問題が出ました*1。
BitSet は、MultiSet と同じく C# には（似たようなものはありますが）存在しないデータ構造です。C++だと通るらしい愚直解は通らなかったので、この問題でテストしつつ BitSet をライブラリ化することにしました。
BitSet とは
ざっくり言えば、BitFlag を bool ではなく long（64bit 整数）で保持し、ビット演算を駆使することで64倍高速な処理を実現するデータ構造です。やや大げさですが、 ループ弱計算量を落とせると考えるとそれなりに効く場面があるかもしれません。
C# における BitSet
C++ の BitSet と完全に一致した API を持つデータ構造はありませんが、C# には BitArray という同じようなデータ構造があります。BitArray ではビット演算はサポートされていますが、フラグの立っている数をカウントする Count の API が存在せず、やや不便です。
そこで、C++ と同じような API を持つ BitSet クラスを自作することにしました。
実装
先ほどの問題の AC コードに貼り付けています。シフト演算は未実装です。
各演算は自分で考えて書いているので、もう少し効率のよい書き方があるかもしれません。すべての演算についてランダム値を用いたテストを通しているので、正確性はあると思います。
定数倍高速化の話
これを書いている中で、今まで少し気になっていた定数倍高速化周りについて知見が得られたので共有しておきます。
class と struct どっちが速い問題
C# の class はヒープ、struct はスタックにインスタンスが生成されます。この関係で速度面ではわずかに struct が有利とされているのですが、struct は値渡しがデフォルトになるなど扱いに注意が必要な面もあります。
インターネットを検索してみてもどちらが良いかは諸説あり、結局どうなんだろうというのをこの問題で試してみました。
こちらが class 版の結果で、こちらが struct 版の結果です。ざっくりまとめると、以下のような結果になりました。
- class 版の実行時間に対する struct 版の実行時間の割合
- 最大値: 110%
- 最小値: 94%
- 100%未満のケース率: 89% (25/28)
- 平均値: 97%
悪化する場合もありましたが、9割弱のケースで実行時間が削減され、削減された実行時間の平均は 3% でした。実行時間の減少だけでいうと、2498ms が 2349ms に削減（-149ms）したものが最も大きかったです。
以上のことから、今回のケースは struct の方が有利でしたが、決定的な差にはならないと結論付けました。とりあえずライブラリは struct にしておこうと思います。
Linq 重い問題
Count の計算に Linq を使った場合、TLE が発生して通せませんでした。これを通常のループでインデックスアクセスに置き換えるだけで通るようになりました。
こちらが Linq を使った版、こちらが通常のループに置き換えた版です（双方114行目から）。ざっくりまとめると、以下のような結果になりました（Linq 版で TLE したケースはまともな比較ができないので除外しています）。
- Linq 版の実行時間に対する通常ループ版の実行時間の割合
- 最大値: 121%
- 最小値: 58%
- 100%未満のケース率: 86% (12/14)
- 平均値: 73%
ケース率だけ見ると微妙な気もしますが、TLE 分を除いて14ケースしか比較できてないのでここはあまり気にしない方が良いかもしれません。注目すべきは平均値で、3割弱ほど実行時間が削れています。
以上のことから、ループ内で Linq を利用するのは避けた方が無難と結論付けました。なんでここまで遅くなっているのか分かりませんが…。
