Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Python で最強の平衡二分探索木を作る
Search
tatyam
May 18, 2022
0
2.6k
Python で最強の平衡二分探索木を作る
tatyam
May 18, 2022
Tweet
Share
More Decks by tatyam
See All by tatyam
定数倍高速化の技術
tatyam_prime
7
3k
Monge の手引書
tatyam_prime
1
5.7k
高難易度木問題を解くテクニック集
tatyam_prime
4
5.5k
Featured
See All Featured
Testing 201, or: Great Expectations
jmmastey
41
7.2k
Embracing the Ebb and Flow
colly
84
4.5k
How GitHub (no longer) Works
holman
312
140k
Visualization
eitanlees
146
15k
Rebuilding a faster, lazier Slack
samanthasiow
79
8.8k
Practical Orchestrator
shlominoach
186
10k
Fantastic passwords and where to find them - at NoRuKo
philnash
50
2.9k
GitHub's CSS Performance
jonrohan
1030
460k
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
Intergalactic Javascript Robots from Outer Space
tanoku
270
27k
Automating Front-end Workflow
addyosmani
1366
200k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
49
2.2k
Transcript
Python で最強の平衡二分探索木を作る @tatyam_prime
Python には平衡二分探索木がない 平衡二分探索木 (値の集合を管理して、要素 を追加、要素 を削除、 以上で最小の要素 を見つける、がそれぞれ 時間でできるデータ構造) ↓競プロでよく使われる言語
C++ には std::set が Java には java.util.TreeSet が C# には System.Collections.Generic.SortedSet が Rust には std::collections::BTreeSet が Python には平衡二分探索木が用意されていない! (もしかして : スクリプト言語だから) x x x O(log N)
Python で最強の平衡二分探索木がほしい 実現方法 バイナリを埋め込む とても速い、とても長い、hack のあるコンテストではルール違反 一般に使われている sortedcontainers などのコードを貼り付ける 長すぎて提出できない
Binary Indexed Tree や Binary Trie 整数しか入れられない、値域に制限がある 平方分割 各操作 時間になって、遅い (?) どこでも使えて、整数以外も入れられて、コードが短くて、速い、平衡二分探索木を 作ろう! Θ( ) N
平方分割 個くらいのバケットに分けて要素を管理する (平衡 分探索木) N N
回のランダムアクセス 回のシーケンシャルアクセス 実は平方分割はそこまで遅くない VS Θ(log N) Θ( ) N
さらに速くする 上 : 各バケットの 個目の要素にアクセ スすると、シーケンシャルアクセスにな らない (キャッシュは効くかも) 下 :
シーケンシャルアクセスになる。挿 入・削除に伴うずらす操作はとても速 く、検索も二分探索できる → バケットの数を小さく、各バケットの要素 数は大きく (1 : 50 くらいに) 1
Python の特性 いろいろな型を入れられる柔軟性のために、すべてが参照でできている 参照 → ランダムアクセス → 遅い クラス内の変数 /
関数を得るのに何手間もかかる (C++ ならメモリアクセス 1 回) 平衡二分探索木はこれを 回やるので、遅い 平方分割は組み込み型の list を使える list の任意位置の挿入 / 削除 ( 時間) は異様に速い 「各要素への参照を持った配列」をずらす操作になり、シーケンシャルアクセスで あり、SIMD で高速化できる Θ(log N) Θ(N)
完成した tatyam-prime/SortedSet – GitHub 普通の平衡二分探索木より速く、値域を制限するタイプと同等くらいの速さ Python で std::set の代替物を作った –
Qiita という記事を書いた 平衡二分探索木を使う問題が出題されるたび言及されるように ABC245 E - Wrapping Chocolate では、約 29 / 99 (Python3, コンテスト中の全 AC) が SortedSet を使っていた
おわり 平方分割を使って Python で最強の平衡 二分 探索木を作りました Qiita の SEO ってすごいですね