Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
Python で最強の平衡二分探索木を作る
Search
tatyam
May 18, 2022
3.5k
1
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
Python で最強の平衡二分探索木を作る
tatyam
May 18, 2022
Transcript
9 slides
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 ってすごいですね
More Decks by tatyam
See All by tatyam
定数倍高速化の技術
tatyam_prime
9
6.3k
Monge の手引書
tatyam_prime
1
8.5k
高難易度木問題を解くテクニック集
tatyam_prime
6
8.3k
Featured
See All Featured
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
31
3.4k
It's Worth the Effort
3n
188
29k
The Illustrated Children's Guide to Kubernetes
chrisshort
51
53k
Principles of Awesome APIs and How to Build Them.
keavy
128
18k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
3k
Tips & Tricks on How to Get Your First Job In Tech
honzajavorek
1
850
HTML-Aware ERB: The Path to Reactive Rendering @ RubyCon 2026, Rimini, Italy
marcoroth
6
940
Fireside Chat
paigeccino
43
4.1k
Building the Perfect Custom Keyboard
takai
2
960
How to audit for AI Accessibility on your Front & Back End
davetheseo
0
640
Rebuilding a faster, lazier Slack
samanthasiow
85
9.8k
Hiding What from Whom? A Critical Review of the History of Programming languages for Music
tomoyanonymous
3
1.5k