[Python]平衡二分木が必要な時に代わりに何とかする変なテク[競プロ]
はじめに
読んで
変なテクが足りない
と思ったので勝手に付け足す
解決法5: 変なデータ構造を作る
平衡二分木みたいな複雑なデータ構造は動作が重いが、Python の標準ライブラリの関数でほとんど処理が終わるようなデータ構造なら十分実用できる速さになる
実装が簡単なので機能を足すのも簡単
例
新ジャッジでの実行時間なので比較するときは注意
CPSCO2019 Session1 E - Exclusive OR Queries (1344 ms)
自分的ベンチマーク問題
ARC033 C - データ構造 (500 ms)
k 番目の値を取り出す
すぬけのお誕生日コンテスト F - Lake (685 ms)
tuple を乗せる
解決法6: C++ の set に Python のオブジェクトを乗せる
コンパイル時間にコンパイルする 何もおかしいことはしていない
爆速だけど機能を足すのは面倒、あと PyPy では使えない
例
CPSCO2019 Session1 E - Exclusive OR Queries (916 ms)
int と float を同時に入れるとバグるので注意
ARC033 C - データ構造 (317 ms)
k 番目の要素は g++ 拡張で
すぬけのお誕生日コンテスト F - Lake (630 ms)
tuple も乗る
20/08/20 追記: これ前に誰かがやってた気がしていて記事書いたときは見つけられなかったんですが、今先駆者を見つけました（ごめんなさい）
自分のやり方と結構違ってるっぽい？
PythonからC++のstd::setを召喚するやつが完成しました。
— fine (@refine_P) 2019年6月6日
一応、最低限のメモは残したので未来の僕でも解読できるはず...https://t.co/tvKjer8gqV
(20/07/14追記) 解決法7: SQLite を使う
そういえばデータベースは B 木だか B+ 木だかで実装されているので利用できる
例
CPSCO2019 Session1 E - Exclusive OR Queries (1785 ms)
上手く書けばもっと早くなるかも
k 番目の要素は取り出せなさそう
おわりに
おわりです
