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
Related Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →atcoder×テストは記憶の手段×人に教える×numba×abc171×質の良い情報源の発見×テストの高速サイクル×気づきの言語化×abc172c×経路に依存しない×順序のない列は多重集合×educational_dp_contest×エンジニアの学び方×学び方→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×Pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
- →座標圧縮×setはメモリ食い×numba×numbaに複雑な型を渡す×numba bisect×numpy.unique×長方形グラフ探索×番兵×numba np.concatenate×csr_matrix×リンクトリスト×mprof×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]