Rustコトハジメ

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

おれの自作スキップリストでABC140-Eを通したぞ!!!

ふらふらです。おれお疲れ様。スキップリストはこれにて一旦終了。

www.rustforbeginners.com

で、ABC140-EはRustの1.17以上じゃないとrange関数がないから不利という話をしました。

www.rustforbeginners.com

これに対して、コンパイラのアップデートが今すぐ行われるという気配はなく、直近のABCで順序つきセットがないことで不利を食らうのが嫌なので、rangeのようなAPIを持ったスキップリストを実装するという話をしました。

Submission #7476535 - AtCoder Beginner Contest 140

それで今、BTreeSetを使ってCEのままだったABC140-EをACしました。うおおおおおおおおおおおおおおおおおおおおおおおお

スキップリストなんか使ってる人はそうそういないでしょうし、わりと嬉しいです。

昨日の段階で、AOJのN=106がMLEするという話をしましたが、記事に書いたとおり、ノード内でBTreeMapを使うのをやめてVecを使ったりと多少最適化したところ、MLEはしなくなり(TLEのまま。2.35secでぎり足りない。BTreeMapだと1.25secでACする)、速度も少しだけ上がりました。

しかし、BTreeSetよりは5-10倍くらいは遅いです。以下は挿入と探索のベンチマーク(N=104)。他にも色々とスキップリストの性能改善のためにベンチマークを書いてみましたが、改善するアイデアがないので、AtCoderの問題が解けるならもういいかなということでやめます。ABC140-Eが200msなので、たぶん、105程度の問題ならば、使えるレベルではあると思います。

test skiplist::skiplist::bench_btree_find_random       ... bench:     626,690 ns/iter (+/- 31,563)
test skiplist::skiplist::bench_btree_insert_random     ... bench:   4,423,480 ns/iter (+/- 1,357,718)

test skiplist::skiplist::bench_skiplist_find_random    ... bench:   4,631,430 ns/iter (+/- 283,324)
test skiplist::skiplist::bench_skiplist_insert_random  ... bench:  26,595,850 ns/iter (+/- 9,479,758)

興味のある競プロRustaceanの方は、BTreeSetでいけるやんけ!という時に使ってみてください。

github.com

APIは、

  • new(): 空のスキップリストを生成します
  • insert(T) -> bool: 実際にインサートしたか(衝突しなかったか)を返します
  • find(&T) -> bool: 値があるかを返します
  • ge_iter(&T): 引数以上の値を昇順に返すイテレータを返します
  • le_iter(&T): 引数以下の値を降順に返すイテレータを返します
  • iter(): 全体を昇順に舐めるイテレータを返します
  • TはOrdの他Cloneも要求しますが、競プロの問題の範疇では問題がないでしょう

非常時用なので競プロで利用可能なだけの最低限な機能しか持ってません。あと、Multisetもないので、これをラップしたMultisetのようなものを実装しています。HashMapを添えて個数をカウントしてるだけです。問題を解くには十分なことが多いはず。これでしのいで、コンパイラのバージョンが上がるのを待ちます。