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
1
2.9k
Python で最強の平衡二分探索木を作る
tatyam
May 18, 2022
Tweet
Share
More Decks by tatyam
See All by tatyam
定数倍高速化の技術
tatyam_prime
9
4.3k
Monge の手引書
tatyam_prime
1
6.6k
高難易度木問題を解くテクニック集
tatyam_prime
5
6.3k
Featured
See All Featured
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
229
22k
Measuring & Analyzing Core Web Vitals
bluesmoon
7
520
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
48
2.9k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
138
34k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
A Tale of Four Properties
chriscoyier
160
23k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
231
53k
The Power of CSS Pseudo Elements
geoffreycrofte
77
5.9k
Practical Orchestrator
shlominoach
189
11k
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
248
1.3M
Writing Fast Ruby
sferik
628
62k
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 ってすごいですね