RBST
Randomized Binary Search Tree
ABC170 Eの解説で
順序付き多重集合は C++ の multiset などを用いることで高速に処理することができます。
と書かれていたため、C++のmultisetに相当するものはPythonだと何？と話題になった
Pythonでmultiset heapqを使ってなんとかするケースが多い
Pythonの標準ライブラリには平衡二分木がない
自前ライブラリとして持っておくといいのでは…という気持ちになった
ノードをオブジェクトとして作ってるような実装は全般的に筋悪
オブジェクトの生成コストが高いので。
配列で実装してnumbaでコンパイルする方針で作る
ABC170Eで AC した
--- 開発
C++実装をPythonに移植した
k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiitaで紹介されてるのを素朴に移植
https://github.com/nishio/atcoder/blob/master/memo/rbst_normal.py
ABC170 Eのフェニック木での実装をRBSTに置き換えて全テストコードでACすることを確認
フェニック木での実装　4.83sec
RBSTでの実装　105.47sec
20倍遅い
クラスを取り除く
67.01sec
6割ほど速くなった
再起呼び出しを取り除きnumbaでコンパイル
10.13sec
リストでの逐次追加をnp.arrayでの一括アロケーションに変えた
4.60sec