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
Red-Black Tree for Ruby
Search
Kyuden Masahiro
March 22, 2019
Programming
2.2k
1
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
Red-Black Tree for Ruby
https://railsdm.github.io/
Kyuden Masahiro
March 22, 2019
Transcript
50 slides
Red-Black Tree for Ruby Kyuden Masahiro
I’m kyuden • Github: kyuden • Twitter: @kyuden_ • Banken
gem creator • https://github.com/kyuden/banken • Sorcery gem commiter • https://github.com/Sorcery/sorcery • WEB+DB Press Ruby連載(vol96~101)
None
None
Ruby biz Grand prix 2017
Our Team
RubyKaigi 2017
RubyKaigi 2017 RubyKaigi 2018
今回のストーリーの始まり • インメモリで約800万個の数値(integerのみ)の集合から最小 値を取得したい – 数値は頻繁に追加/削除され集合の数は増減する – Rubyを使用する(Redisは使用しないものとする) ※ 実際はもう少し複雑な要件だったがミニマルにして抜粋
どう実装しましょうか?
SortedSet • Rubyの標準ライブラリであるSortedSetを発見 • SortedSetという名前から今回の用途にぴったりだと確信
これで無事何もなければこのスライドは無価値
問題発生 • 想像以上にパフォーマンスがでなかった ※1 – まず自分が書いたプログラムのバグを疑う • 見当たらない • プロファイリングしてみる
– SortedSetに時間がかかりすぎていた ※1 ベンチマークはのちほど
SortedSetの内部実装 • rbtreeというgemがrequireできる場合は内部記憶として rbtreeを利用する • ただrbtreeはthird partyのgemでありデフォルトではイン ストールされていない – その場合requireできないので内部記憶はSet同様Hash
を利用する – なのでデフォルトの挙動はこちら
SortedSetの内部実装 – rbtreeを利用しない場合 - • SourtedSet#first – SourtedSet#firstが呼ばれると全要素をArray#sort!して いた •
一度sortしたものはキャッシュするが新しい要素が 追加/削除された場合はキャッシュが消える • 最悪計算量はO(n^2) • SortedSetという名前からO(log n)を期待していた
各計算量のおけるステップ数比較 log n n n log n n^2 2 5
12 25 3 10 33 100 4 15 59 225 4 20 86 400 5 25 116 625 5 30 147 900 7 100 664 10000 8 300 2468 90000 10 1000 9966 1000000 13 10000 132877 100000000 16 100000 1660964 10000000000 20 1000000 19931568 1000000000000
解決? • とりあえず`gem install rbtree`すればO(log n)が手に入るので今回の問題 は解決する – だがRubyとしてこれで良いのかは少し疑問が残る –
気づかずにO(n^2)のSortedSetを利用してしまう人がいるのではないか – Ruby本体にrbtreeのようなデータ構造の実装が入ると今回の自分のよ うに調査しなくて済むし、気づかなかった人もO(log n)が手に入る – もしくはRuby本体からSortedSetを削除し後方互換性を考えgemとし て提供するのも選択肢としてはあり?
SortedSet#first vs SortedSet#first with rbtree Ruby 2.6.1 gcc version 8.1.0
(Ubuntu 8.1.0-5ubuntu1~16.04)
Rbtreeとは?
Rbtree • Red-Black Tree(赤黒木)の実装を提供するC extension gem Red-Black Tree • 平衡二分探索木の一種であり現在も広く利用されているデータ構造
– std::set, std::map (GNU C++ ) – TreeMap, TreeSet (Java) – SortedSet (C# .NET) – etc
Red-Black Tree -性質- • 2分木 • 各ノードは赤か黒の色を持つ • 根は黒ノード •
赤ノードの子は黒ノード • 全ての葉から根への経路上の 黒ノードは同じ個数 1 2 5 4 6 7 8 3
Red-Black Tree -性能- • 探索、挿入、削除の最悪計算量がO(log n) • 木の高さが2logn以下 – 最短のパスは全てが黒ノードのパス、最長のパスは赤黒交互に並ぶノードのパス
• 最短の最長のパスの長さは2倍以内に収まる ※ AVL木も探索、挿入、削除の最悪計算量はO(log n)だが赤黒木より厳密な平衡性を保つので 赤黒木より木高さも低く検索は早い。一方、その分挿入、削除のリバランスに時間がかかる ため赤黒木より遅くなる場合がある。 よって頻繁に更新しない辞書のような用途だとAVL木が適しているが、様々な汎用的な用 途を考慮すると赤黒木のほうが適しているケースが多いため様々な言語のライブラリの実 装として選択されているのではないかと推測する
Red-Black Tree -ユースケース-優先度付きキュー- • Linuxカーネル 2.6.23 にマージされたCompletely Fair Scheduler (CFS)も内
部でも仮想実行時間でキーとし優先順序付けされた赤黒木を使用しタスク を選択している。 https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c
Red-Black Tree -ユースケース-転置インデックス検索 • Rbtree#lower_bound/upper_bound/boundを使用すれば、キーを正確に指 定する必要はなく、次の大きいキーや次に小さいキー、有る範囲のキーにあ る要素をO(log n)で取得できる – Hashはキー順に並んでいないので同様の操作を行う場合、全てのキーを
参照する必要がある
実装が複雑 Red-Black Treeの優れた性質の代償
Left-leaning Red-Black Tree
Left-leaning Red-Black Tree • 2008年にRobert Sedgewickによって発表された論文※1にて発表された赤黒 木の異種(variant) • もともと赤黒木は1978年にRobert SedgewickとLeonidas
J. Guibasによって 発表された※2ことを考えると、相対的には最近発表されたといえ、かつ Robert Sedgewick自身による赤黒木の再発明ということでわくわくする ※1 Robert Sedgewick. Left-leaning Red–Black Trees(2008) http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf ※2 赤黒木の元になったのは1972年のRudolf Bayerの発明によるもの
実装が複雑 Red-Black Treeの優れた性質の代償
Left-leaning Red-Black Tree - 要約 - • Left-leaning Red-Black Tree(以後
左傾赤黒木と記載する)は赤黒木より非常にシンプル に実装でき、挿入、削除においては1/4以下のコード量で実装できる – よって従来の赤黒木の複雑性を解決し、メンテナンス性が向上する • 赤黒木と左傾赤黒木のパフォーマンス比較に関しては明確にはこの論文で述べられて いない – Robert Sedgewickによるプレゼンテーション資料※1では左傾赤黒木の特徴として 赤黒木と比較して”less code implies faster insert, delete”とパフォーマンスに関し 言及されていた。(だがあくまで”imply”であり計測結果の数値の記載はない) ※1 Robert Sedgewick. Left-leaning Red–Black Trees http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
Left-leaning Red-Black Tree - コンセプト - • 左傾赤黒木は赤黒木に対してさらに制約を追加することで赤黒木の複 雑な条件分岐を減らすことに成功している –
赤黒木を2-3-4木もしくは2-3木に1対1対応させる過程で新しい制 約が生まれ結果それが左傾赤黒木となる 1 2 5 4 6 7 8 3 1 2 3 5 4 6 7 8
2-3-4木 -ノードの種類 - b • 2ノードは、1つの要素と2つの子をもつ • 3ノードは、2つの要素と3つの子をもつ • 4ノードは、3つの要素と4つの子をもつ
※子は空の場合もあり a c b d a c e b d f a c e g
2-3-4木をRed-Black Treeで表現 -3ノード場合- 5 3 3 5 • 子ノードに赤ノードを含む赤黒木で表現する –
3ノードの場合は上記のように2種類の赤黒木に分類できる – 必ず左の子に赤ノードが傾くという制約を加え、もし右の子に赤いノードが傾いている場合は 左回転(Left flip)して左の子に赤ノードがくるよう強制する(Left-leaning Red-Black Treeという命 名はこの制約からきたものである) • その結果、右の子が赤ノードである多くのケースを排除でき赤黒木の分岐条件を減らすこと ができる 3 3 5 5 3 3
2-3-4木をRed-Black Treeで表現 -2ノード場合- 4 • 2ノードの場合は2分木なのでそのまま赤黒木で表現できる 4
2-3-4木をRed-Black Treeで表現 -4ノード場合- 8 7 6 7 8 6 7
3 6 8 6 8 7 8 6 7 6 7 8 6 8 7
Left-leaning Red-Black Treeを2-3-4木で表現 • 左傾赤黒木が2-3-4木にみえてくるはず 1 2 5 4 6
7 8 3
Left-leaning Red-Black Treeを2-3-4木で表現 • 左傾赤黒木が2-3-4木にみえてくるはず.. 1 2 5 4 6
7 8 3
Left-leaning Red-Black Treeを2-3-4木で表現 • 左傾赤黒木が2-3-4木にみえてくるはず.... 1 2 5 4 6
7 8 3
Left-leaning Red-Black Treeを2-3-4木で表現 • 左傾赤黒木が2-3-4木にみえてくるはず...... 1 2 5 4 6
7 8 3 6 7 8 3 5 1 2 4
Left-leaning Red-Black Treeを2-3-4木で表現 • 左傾赤黒木が2-3-4木にみえてくるはず! 1 2 3 5 4
6 7 8
Left-leaning Red-Black Tree – ここまでのまとめ- • 赤黒木は赤黒ノードのノードパターンを全てチェックする必 要があったが、2-3-4木を赤黒木で表現する過程で必要となる 制約を加えることで、いくつかのパターンが自明となり チェックする必要なくなったため左傾赤黒木はシンプルな実
装となる • ただ、4ノードの分割処理など他にもケアする内容があり実 際はもう少し複雑だが、本資料では詳細な左傾赤黒木の解説 は割愛する
https://github.com/kyuden/llrbtree
kyuden/llrbtree • 左傾赤黒木を提供するC extention gem • 左傾赤黒木は`llrbtree/ext/llrbtree/tree.c`に実装 • binding部分は左傾赤黒木に合わせて改変したが基本的には rbtree
gemと同じであるためbinding部分のCopyrightは原 作者のまま • Robert Sedgewickがさきほどの論文で推奨していた再帰に よる追加、削除処理の実装を選択
kyuden/llrbtree -モチベーション- • 論文には明示的に赤黒木と左傾赤黒木のパフォーマンス比較が記載 されていなかった • 論文には左傾赤黒木のデメリットの記載が少なかった • もし、前述した論文やプレゼンテーション資料通りコード量も少な くメンテナブルで、かつ赤黒木より高速にうまく実装できれ
ば、Rubyにfeature request送ってみるのもありだと思った – 少なくとも現在のSortedSet#firstより数千倍は高速化できる • 論文読んで高まった
llrbtreeとrbtreeのパフォーマンス比較 -検索- Ruby 2.6.1 gcc version 8.1.0 (Ubuntu 8.1.0-5ubuntu1~16.04)
llrbtreeとrbtreeのパフォーマンス比較 -挿入- Ruby 2.6.1 gcc version 8.1.0 (Ubuntu 8.1.0-5ubuntu1~16.04) Ruby
2.6.1 gcc version 8.1.0 (Ubuntu 8.1.0-5ubuntu1~16.04)
llrbtreeとrbtreeのパフォーマンス比較 -削除- Ruby 2.6.1 gcc version 8.1.0 (Ubuntu 8.1.0-5ubuntu1~16.04)
パフォーマンス結果 -要約- • 左傾赤黒木は検索、挿入、削除がいずれの操作においても赤黒木より遅い という結果となった – 削除に関しては要素数が100万個の場合約2倍の開きがあった – 左傾赤黒木は赤黒木に比べて挿入と削除、各操作における回転数が挿入 は2.96x、削除は51.99x増えている※1
• 前述したRobert Sedgewickの論文にパフォーマンス比較がなかったのは左 傾赤黒木が遅いため? ※1 http://www.read.seas.harvard.edu/~kohler/notes/llrb.html
Red-Black Tree vs Left-leaning Red-Black Tree • 左傾赤黒木はたしかにコード量はシンプルだがパフォーマンス比較の 結果をふまえると、例えばプログラミング言語の標準ライブラリとし て提供するなら赤黒木の方がメリットがあるのではないか
– 赤黒木の方が歴史が長く安定して実用されてきたという実績から も左傾赤黒木が選ばれるユースケースは限られてくるのではない か – もし要素数が少ない場合のみの使用を前提とするアプリケーショ ンなら実装コストを優先して左傾赤黒木が選択肢になりえる
本日の内容 • SortedSetの内部実装/気をつけるべき点 • Red-Black Tree – 性質/性能 – ユースケース
• Left-leaning Red-Black Tree – コンセプト – Red-Black Treeとのパフォーマンス比較
おわり
More Decks by Kyuden Masahiro
See All by Kyuden Masahiro
365日24時間稼働必須サービスの 完全無停止DB移行
kyuden
23
11k
Why Rails 5.1
kyuden
1
800
Rails Authorization
kyuden
21
15k
One Night Vue.js
kyuden
14
3.8k
Other Decks in Programming
See All in Programming
止まらない比較を止める — 余帰納法で無限ストリームを比べる
tarao
0
190
Materialが消えた日 〜真っ白なFlutterキャンバスにRenderObjectで絵を描く〜
umigishiaoi
0
170
まずはコードより業務と向き合う:テーブル解体のためにPdMを呼んだ話
sakawe_ee
0
250
SFCで実現する病院・医療システムの動的組み立て式UI
koukimiura
1
180
RaspberryPi 5で軽くはじめるk3sとtailscaleを用いたホームサーバー構築 (1)
nasum
0
400
社内AIエージェント「Askワンバン」における コストチューニングの取り組み
t0yohei
0
170
Claude Codeのおかげでやりたいことがやれるようになったんだよォー!
sms_tech
0
150
クラウドゲーミングのパフォーマンス最適化に挑む / Cloud Gaming Performance Tuning
vivion
0
350
protojson における文字化けの扱い
kazuki1023
0
440
LLM 101
dalinaum
0
510
Spec-Driven Development - Why Vaadin Is the Perfect Fit
simas
PRO
0
260
[DroidKnights 2026] Workflow AX 적용기 — 자동 정책 정리부터 E2E까지
dayeon
0
110
Featured
See All Featured
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
46
3.1k
Learning to Love Humans: Emotional Interface Design
aarron
275
41k
KATA
mclloyd
PRO
35
16k
State of Search Keynote: SEO is Dead Long Live SEO
ryanjones
0
350
Pawsitive SEO: Lessons from My Dog (and Many Mistakes) on Thriving as a Consultant in the Age of AI
davidcarrasco
1
300
Reality Check: Gamification 10 Years Later
codingconduct
0
2.4k
[SF Ruby Conf 2025] Rails X
palkan
3
1.5k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
12
1.4k
How to build a perfect <img>
jonoalderson
1
6.2k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
47
8.4k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
254
23k
Agile Leadership in an Agile Organization
kimpetersen
PRO
0
310