最近Atcoderのコンテストによく参加してるのですが、優先度付きキューにお世話になることが異常に多く、内部をちゃんと知っておきたいという気持ちから自前実装することにした。実装は以下です。ほぼ初めてRustでまっとうなものを書いたという感じなので、なんか指摘とかしてほしい。 https://github.com/dekokun/atcoder-rust/blob/master/abc141_d/src/main.rs#L25-L141
Rustの標準ライブラリの優先度付きキュー(BinaryHeap)はfloatが扱えない(BinaryHeapはOrdを要求するが、floatはNaNの存在のためOrdではなくPartialOrdとなるため)というのもあって競プロ的には使いづらいのでそこも使いやすくしたいという思いもあった。 (この目的だけだったらNaNが入らないようなOrdなfloatをつくったほうが筋がいいと思うが今回はBinaryHeapの実装のしたさが先に来ているので。NaNを除くような実装は ordered_float - Rust などが参考になる)
実装の工夫や楽しかったことなど
コード： https://github.com/dekokun/atcoder-rust/blob/master/abc141_d/src/main.rs#L25-L141 優先度付き待ち行列 を参考に作りました
- BinaryHeapの実装を知らずに使っている時は"常にソートされているものから値を取り出している"というマインドセットだったが、実装してみると、ソートされてるわけではなく、常に一番上を取ることに特化してるデータ構造だとわかって感動した
- PartialOrdのpartial_cmpがNoneを返すような比較をしたらpanicするようにすることで、意図せずNaN的なものが混入しても早期に気づけるようにした
- 比較した際にはじめてpanicするため、NaN1つの混入では気づかなくてその後2つ目を入れたタイミングでpanicしてわかりづらさがある。本当は自分自身とpartial_cmpしてNoneが返ったらpanicさせるような実装のほうが好ましいかもしれないが、それはfloatのNaNだけを狙い撃ちにしている感じがしてPartialOrd一般に対する話では無い気がする？など迷いが生じて一旦こうしている
- std::fmt::Formatter - Rust を見つつDebug実装を書いたのだけど、Rust 2018 editioinじゃないRustのバージョン(というかatcoderで使用されている1.15.1)ではコンパイルが通らず調べていたら2018 editioinから'_, the anonymous lifetime - The Edition Guide というのが入ったのを知った
- RustのVecにはswap_removeswap_removeという、任意のindexの値をVecの末尾の値と交換しつつ取り除いてreturnするという、binary heap実装にうってつけのメソッドがあって便利だった
- 標準ライブラリのBinaryHeapと比較して、手抜きでpopでIteratorを表現しているため、Iteratorが回るとすべての要素がなくなるという感じでIteratorが極めて使いづらくなっているという重大ポイントがある。これはそのうち直さないと厳しい気がしている
標準ライブラリとの速度比較と実装比較
- 自前実装は標準ライブラリの実装と比較して遅い
- Atcoderで提出してみると、標準ライブラリ実装は50ms, 私の実装を使うと60msって感じで20%ほど遅い
- BinaryHeapに値をpush/popする際に、親と子の値を入れ替える必要があり、私の実装でははVecのswapを使っている。標準ライブラリでは高速化のため、unsafeな構造体を使ってその中で色々なチェックを省きつつやっていることがわかった
- Holeという構造体を使うことでswapをせずに済ませている。swapの中では配列の境界チェックを行いつつ、tmp変数を使って2回コピーして、みたいなことをしているが、Holeを使うことでコピーを1回だけにしていたりget_uncheckedを使用して配列の境界チェックを防いだりしている
感想
- 自分の実装と標準ライブラリの実装や速度を見比べるのめっちゃ楽しい。今後もお世話になるデータ構造は自前実装していきたい。
