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
3k
Python で最強の平衡二分探索木を作る
tatyam
May 18, 2022
Tweet
Share
More Decks by tatyam
See All by tatyam
定数倍高速化の技術
tatyam_prime
9
4.5k
Monge の手引書
tatyam_prime
1
6.8k
高難易度木問題を解くテクニック集
tatyam_prime
5
6.4k
Featured
See All Featured
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
126
53k
Why Our Code Smells
bkeepers
PRO
339
57k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
46
7.6k
StorybookのUI Testing Handbookを読んだ
zakiyama
31
6.1k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
4k
Rails Girls Zürich Keynote
gr2m
95
14k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
26
3k
Intergalactic Javascript Robots from Outer Space
tanoku
272
27k
The Straight Up "How To Draw Better" Workshop
denniskardys
236
140k
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.6k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
8
910
Code Review Best Practice
trishagee
70
19k
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 ってすごいですね