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