Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

スキップリストをてきとうに実装したがだめだめだったというお話

AtCoderのRustコンパイラはまだ1.15であり、順序つきセットのrange関数を使うことが出来ない。これがあるなしで差が出る問題が存在するため、自分で順序つきセットを実装しようという発想になった。BTreeSetを再実装しても面白くないのと、そもそもめんどくさいため、積ん読してあった

みんなのデータ構造

みんなのデータ構造

  • 作者: Pat Morin,堀江慧,陣内佑,田中康隆
  • 出版社/メーカー: ラムダノート
  • 発売日: 2018/07/20
  • メディア: 単行本(ソフトカバー)
  • この商品を含むブログを見る

を手にとり、寝る前にパラパラとめくり、「あー勉強がてらスキップリストを実装するか」という考えに至った。概要自体は30分程度で理解出来た。この本はまじでわかりやすい。

翌日から実装を開始し、適当にinsertとfindとremoveが参照実装のBTreeSetと比較して正しく動くまでに、競プロ勉強の合間を使って2日で出来た。(6時間くらいだと思う)

しかし、AOJのADLS1_4_CはMLE+TLEで死亡した。とにかくメモリを食うし遅い。他の人の解答を見ると、標準ライブラリのHashSetで通ってる人がいる。従って、スキップリストでも通らないということはないと思う。

頭の整理にも役立つので、一旦まとめ作業として、実装の概要と、ベンチマークの結果を共有する。

コードはここにありましゅ。

GitHub - akiradeveloper/rust-comp-snippets

実装の概要

f:id:akiradeveloper529:20190911201928j:plain

スキップリストは、ノードの高さをランダムに決めて、その都度左右のノードとつなぐということを繰り返すという乱択データ構造である。挿入も探索も削除もO(logN)。

Rustは標準ライブラリに乱数ライブラリがなくて、外部クレートに分離してしまっているため、線形合同法で乱数を生成している。スキップリストの実装においては問題にならないと信じた。

リンクを繋いだり切ったりする必要があるのと、ノードの高さも簡単に知れると良いため、リンクはBTreeMapで管理している。実際には左右の番兵しか高さを知る必要はないため、ふつうに配列で良い気がするが、オーダ的には大した問題ではないため、楽な実装を採用したというのもあるし、最初の実装では右に番兵がいなかったため、左から誰も繋がっていないという状態を柔軟に管理する必要があったため、こうなったという理由もある。ここはMLEに効きそうなので直すかも知れない。修正方法の候補としては番兵については高さ64固定にして、その他についてはサイコロを振って決めた高さの配列を用意するという実装の方が却ってすっきりするような気もするし、たぶん高速になる。

本では、左の番兵しか書かれていないのと実装は単方向リストだが、range関数が双方向リストを返したいので、このようにすることにした。また、探索範囲のとり方(exclusiveとか)によっては右から下った方が簡潔になる場合もあるため、右にも番兵を置くことにした。

デバグが大変なので、とりあえずわかりやすいように実装したというのは正しかったと思っている。途中でデバグのためにリンクの状態を可視化するコードも書いたりした。

--,--,--,--,04

--,--,--,--,04

--,--,--,--,04

--,--,--,--,04,--,--,--,--,09

00,--,02,--,04,--,--,--,--,09,--,11

00,01,02,--,04,05,--,--,08,09,10,11,--,13

ベンチマーク結果と考察

N回findを繰り返す実験。N回insertを繰り返す実験を書いて、cargo benchで実行した。

括弧内の数字は、N=100を基準にして、logNの比をかけたものを100とした時の値。大きければ、logNの倍率をかけた場合よりも悪化してることを意味する。

N find(us/op) insert(us/op) logN
100 0.29 (100) 4.27 (100) 4.61
1000 0.43 (99) 4.69 (73) 6.91
10000 0.85 (147) 4.84 (56) 9.21
100000 1.53 (211) 7.62 (71) 11.51
  • insertはfindの10倍遅い
  • しかし、Nが上がっていくと、findがlogN以上に遅くなることもあり、insertとの比は小さくなっていく
  • insertとfindはコード的にさほど差がなく、高さ分だけ左右のリンクを切ったりつないだりするくらいなので、ここで差が出てるということは、やはり、リンクの管理に繋がってるBTreeMapの処理が遅いということかも知れない。

結論

コンパイラのバージョンが上がるのを素直に待つのが一番。

おれがこれ以上スキップリストをやるとしたら、BTreeMapを使ってるのがまずそうなので、それをVecに書き換える最適化をしてから、range関数の実装をすると思う。