Closed14
Hands-on Data Structures and Algorithms with Rust の5章
yukiBinary Tree や Red-Black Tree や Trie や B-Tree などが扱われている。
題材がおもしろくて、IoT Device の管理をどうするか？という内容になっている。いつものようにだんだんよりよいデータ構造に改変していって、その過程でさまざまな解説がされている。最後 B-Tree ということはつまり、結局のところデータベースに入れるのがいいという話になってくるのかな。
yukiRed-Black Tree のルールは下記のようになっている。
- The root node is always black.
- Each other node is either or black.
- All leaves (often null/NIL values) are considered black.
- A red node can only have black children.
- Any path from the root to its leaves has the same number of black nodes.
Red-Black Tree を使用したいモチベーションとしては、Binary Search Tree では、挿入時にとくに根と葉の数を調整する操作を行わないので、だんだん偏った構成の気になってしまう。
Red-Black Tree を使用すると、そうした偏りを防ぐよう挿入時や削除時にあらかじめ定められたルールに基づいてローテーション等を行う。そうすると偏りが減ってより効率のいい木ができやすくなる。といったところなのかなあ。
yukiRustのRed-Black Tree の実装超大変でワロタ
use std::{cell::RefCell, rc::Rc};
type BareTree = Rc<RefCell<Node>>;
type Tree = Option<BareTree>;
struct Node {
pub color: Color,
pub dev: IoTDevice,
pub parent: Tree,
left: Tree,
right: Tree,
}
impl Node {
pub fn new(dev: IoTDevice) -> Tree {
Some(Rc::new(RefCell::new(Node {
color: Color::Red,
dev: dev,
parent: None,
left: None,
right: None,
})))
}
}
#[derive(Clone, Debug)]
pub struct IoTDevice {
pub numerical_id: u64,
pub address: String,
}
enum Rotation {
Left,
Right,
}
#[derive(Clone, Debug, PartialEq)]
enum Color {
Red,
Black,
}
#[derive(PartialEq)]
enum RBOperation {
LeftNode,
RightNode,
}
// from binary tree
pub struct BetterDeviceRegistry {
root: Tree,
pub length: u64,
}
impl BetterDeviceRegistry {
pub fn new_empty() -> Self {
BetterDeviceRegistry {
root: None,
length: 0,
}
}
pub fn add(&mut self, device: IoTDevice) {
self.length += 1;
let root = std::mem::replace(&mut self.root, None);
let new_tree = self.add_r(root, device);
self.root = self.fix_tree(new_tree.1);
}
fn add_r(&mut self, mut node: Tree, device: IoTDevice) -> (Tree, BareTree) {
if let Some(n) = node.take() {
let new: BareTree;
let current_device = n.borrow().dev.clone();
match self.check(¤t_device, &device) {
RBOperation::LeftNode => {
let left = n.borrow().left.clone();
let new_tree = self.add_r(left, device);
new = new_tree.1;
let new_tree = new_tree.0.unwrap();
new_tree.borrow_mut().parent = Some(n.clone());
n.borrow_mut().left = Some(new_tree);
}
RBOperation::RightNode => {
let right = n.borrow().right.clone();
let new_tree = self.add_r(right, device);
new = new_tree.1;
let new_tree = new_tree.0.unwrap();
new_tree.borrow_mut().parent = Some(n.clone());
n.borrow_mut().right = Some(new_tree);
}
}
(Some(n), new)
} else {
let new = Node::new(device);
(new.clone(), new.unwrap())
}
}
fn fix_tree(&mut self, inserted: BareTree) -> Tree {
let mut not_root = inserted.borrow().parent.is_some();
let root = if not_root {
let mut parent_is_red = self.parent_color(&inserted) == Color::Red;
let mut n = inserted.clone();
while parent_is_red && not_root {
if let Some(uncle) = self.uncle(n.clone()) {
let which = uncle.1;
let uncle = uncle.0;
match which {
RBOperation::LeftNode => {
// uncle is on the left
let mut parent = n.borrow().parent.as_ref().unwrap().clone();
if uncle.is_some()
&& uncle.as_ref().unwrap().borrow().color == Color::Red
{
let uncle = uncle.unwrap();
parent.borrow_mut().color = Color::Black;
uncle.borrow_mut().color = Color::Black;
parent.borrow().parent.as_ref().unwrap().borrow_mut().color =
Color::Red;
n = parent.borrow().parent.as_ref().unwrap().clone();
} else {
if self.check(&parent.borrow().dev, &n.borrow().dev)
== RBOperation::LeftNode
{
// do only if it's a right child
let tmp = n.borrow().parent.as_ref().unwrap().clone();
n = tmp;
self.rotate(n.clone(), Rotation::Right);
parent = n.borrow().parent.as_ref().unwrap().clone();
}
// until here. then for all black uncles
parent.borrow_mut().color = Color::Black;
parent.borrow().parent.as_ref().unwrap().borrow_mut().color =
Color::Red;
let grandparent = n
.borrow()
.parent
.as_ref()
.unwrap()
.borrow()
.parent
.as_ref()
.unwrap()
.clone();
self.rotate(grandparent, Rotation::Left);
}
}
RBOperation::RightNode => {
// uncle is on the right
let mut parent = n.borrow().parent.as_ref().unwrap().clone();
if uncle.is_some()
&& uncle.as_ref().unwrap().borrow().color == Color::Red
{
let uncle = uncle.unwrap();
parent.borrow_mut().color = Color::Black;
uncle.borrow_mut().color = Color::Black;
parent.borrow().parent.as_ref().unwrap().borrow_mut().color =
Color::Red;
n = parent.borrow().parent.as_ref().unwrap().clone();
} else {
if self.check(&parent.borrow().dev, &n.borrow().dev)
== RBOperation::RightNode
{
// do only if it's a right child
let tmp = n.borrow().parent.as_ref().unwrap().clone();
n = tmp;
self.rotate(n.clone(), Rotation::Left);
parent = n.borrow().parent.as_ref().unwrap().clone();
}
// until here. then for all black uncles
parent.borrow_mut().color = Color::Black;
parent.borrow().parent.as_ref().unwrap().borrow_mut().color =
Color::Red;
let grandparent = n
.borrow()
.parent
.as_ref()
.unwrap()
.borrow()
.parent
.as_ref()
.unwrap()
.clone();
self.rotate(grandparent, Rotation::Right);
}
}
}
} else {
break;
}
not_root = n.borrow().parent.is_some();
if not_root {
parent_is_red = self.parent_color(&n) == Color::Red;
}
}
while n.borrow().parent.is_some() {
let t = n.borrow().parent.as_ref().unwrap().clone();
n = t;
}
Some(n)
} else {
Some(inserted)
};
root.map(|r| {
r.borrow_mut().color = Color::Black;
r
})
}
fn rotate(&self, node: BareTree, direction: Rotation) {
match direction {
Rotation::Right => {
let x = node;
let y = x.borrow().left.clone();
x.borrow_mut().left = match y {
Some(ref y) => y.borrow().right.clone(),
_ => None,
};
if y.is_some() {
y.as_ref().unwrap().borrow_mut().parent = x.borrow().parent.clone();
if y.as_ref().unwrap().borrow().right.is_some() {
let r = y.as_ref().unwrap().borrow().right.clone();
r.unwrap().borrow_mut().parent = Some(x.clone());
}
}
if let Some(ref parent) = x.borrow().parent {
let insert_direction = self.check(&parent.borrow().dev, &x.borrow().dev);
match insert_direction {
RBOperation::RightNode => parent.borrow_mut().right = y.clone(),
RBOperation::LeftNode => parent.borrow_mut().left = y.clone(),
}
} else {
y.as_ref().unwrap().borrow_mut().parent = None;
}
y.as_ref().unwrap().borrow_mut().right = Some(x.clone());
x.borrow_mut().parent = y.clone();
}
Rotation::Left => {
let x = node;
let y = x.borrow().right.clone();
x.borrow_mut().right = match y {
Some(ref y) => y.borrow().left.clone(),
_ => None,
};
if y.is_some() {
y.as_ref().unwrap().borrow_mut().parent = x.borrow().parent.clone();
if y.as_ref().unwrap().borrow().left.is_some() {
let l = y.as_ref().unwrap().borrow().left.clone();
l.unwrap().borrow_mut().parent = Some(x.clone());
}
}
if let Some(ref parent) = x.borrow().parent {
let insert_direction = self.check(&parent.borrow().dev, &x.borrow().dev);
match insert_direction {
RBOperation::LeftNode => parent.borrow_mut().left = y.clone(),
RBOperation::RightNode => parent.borrow_mut().right = y.clone(),
}
} else {
y.as_ref().unwrap().borrow_mut().parent = None;
}
y.as_ref().unwrap().borrow_mut().left = Some(x.clone());
x.borrow_mut().parent = y.clone();
}
}
}
fn parent_color(&self, n: &BareTree) -> Color {
n.borrow().parent.as_ref().unwrap().borrow().color.clone()
}
fn uncle(&self, tree: BareTree) -> Option<(Tree, RBOperation)> {
let current = tree.borrow();
if let Some(ref parent) = current.parent {
let parent = parent.borrow();
if let Some(ref grandparent) = parent.parent {
let grandparent = grandparent.borrow();
match self.check(&grandparent.dev, &parent.dev) {
RBOperation::LeftNode => {
Some((grandparent.right.clone(), RBOperation::RightNode))
}
RBOperation::RightNode => {
Some((grandparent.left.clone(), RBOperation::LeftNode))
}
}
} else {
None
}
} else {
None
}
}
/// compares two devices in order to provide a direction that they should be appended to
fn check(&self, a: &IoTDevice, b: &IoTDevice) -> RBOperation {
if a.numerical_id <= b.numerical_id {
RBOperation::LeftNode
} else {
RBOperation::RightNode
}
}
}
とくにこのあたりがひどいｗ
let grandparent = n
.borrow()
.parent
.as_ref()
.unwrap()
.borrow()
.parent
.as_ref()
.unwrap()
.clone();
本の中ではマクロを使えば楽にできるよと書いてあるが、Rc<RefCell<Node>> を NewType にして、それに対する取得関数をはやしたらいいのではないかと思った。
struct BareTree(Rc<RefCell<Node>>);
impl BareTree {
pub fn grandparent(&self) -> BareTree {
self.0.borrow()
.parent
.as_ref()
.unwrap()
.borrow()
.parent
.as_ref()
.unwrap()
.clone()
}
}
ちなみに、Rust ユーザーはこういうメソッドチェーンきっちり読めてるの？とよく質問されるが、IDE 上では型が横についているので問題はない。下記は VSCode によるもの。
yukiHeap
- 挿入の際に upheap 、削除の際に downheap という処理を行う？
- Red-Black Tree と比べると相対的に実装の複雑さがにあ。
- リストをソートするためにとても効率のいい手段。
- 並行処理時でも正しく動く。
- キューイングあるいはソーティング以外の用途として使用するのはまれ。
- ただもっといいソートの方法はいくらでもある。
yuki本が全然ヒープに対してやる気がないみたいで、説明がなくてちょっと笑った。
本書で紹介されているのは Binary Heap で、これは Primary Queue を使って完全二分木をエミュレートする。
キューの番地がそのままツリーの探索に使用でき、
- その番地 i から着目した際に左にあるノードは primary queue 上は 2*i + 1 のインデックス
- その番地 i から着目した際に右にあるノードは primary queue 上は 2*i + 2 のインデックス
- その番地 i から着目した際に親にあたるノードは primary queue 上は (i - 1) / 2 のインデックス
に存在する。Eytzinger Layout とか検索すると出てくる。
あとで読む。
実装は下記のような感じになる。Red-Black Tree の地獄に比べるとかなり楽だ笑
#[derive(Clone, Debug)]
pub struct IoTDevice {
pub numerical_id: u64,
pub address: String,
}
#[derive(Clone, Debug)]
pub struct MessageNotification {
pub no_message: u64,
pub device: IoTDevice,
}
pub struct MessageChecker {
pub length: usize,
heap: Vec<Box<MessageNotification>>,
}
impl MessageChecker {
pub fn add(&mut self, notification: MessageNotification) {
self.heap.push(Box::new(notification));
self.length = self.heap.len();
if self.length > 1 {
let mut i = self.length;
while i / 2 > 0 && self.has_more_messages(i, i / 2) {
self.swap(i, i / 2);
i /= 2;
}
}
}
fn swap(&mut self, pos1: usize, pos2: usize) {
let m2 = self.heap[pos1 - 1].clone();
self.heap[pos1 - 1] = std::mem::replace(&mut self.heap[pos2 - 1], m2);
}
fn has_more_messages(&self, pos1: usize, pos2: usize) -> bool {
let a = &self.heap[pos1 - 1];
let b = &self.heap[pos2 - 1];
a.no_message >= b.no_message
}
pub fn pop(&mut self) -> Option<MessageNotification> {
if self.length > 0 {
let elem = self.heap.swap_remove(0);
self.length = self.heap.len();
let mut i = 1;
while i * 2 < self.length {
let children = (i * 2, i * 2 + 1);
i = if self.has_more_messages(children.0, children.1) {
if self.has_more_messages(children.0, i) {
self.swap(i, children.0);
children.0
} else {
break;
}
} else {
if self.has_more_messages(children.1, i) {
self.swap(i, children.1);
children.1
} else {
break;
}
}
}
Some(*elem)
} else {
None
}
}
}
Trie tree。名前は聞いたことあった。
このサイトの解説がわかりやすかった。
文字列の保有が典型的なユースケースで、たとえばサイトのように fire-arm, fire-man とある状態で fire-works を追加すると、fire までは共通で fireworks の接頭辞は w だからそれがあるかどうかを見るだけで、すでに保持しているかどうかが判定可能になるっぽい。
yukiTrie の実装はなんかこうなるらしい。
通常ツリーは Node に left, right の Node をもたせて実装すると思うけど、このツリーの場合は HashMap を保存先として使用しながら実装するという点が特徴的かも。
use std::collections::HashMap;
type Link = Box<Node>;
#[derive(Clone, Debug)]
pub struct IoTDevice {
pub numerical_id: u64,
pub path: String,
pub address: String,
}
impl IoTDevice {
pub fn new(id: u64, address: impl Into<String>, path: impl Into<String>) -> IoTDevice {
IoTDevice {
address: address.into(),
numerical_id: id,
path: path.into(),
}
}
}
struct Node {
pub key: char,
next: HashMap<char, Link>,
pub value: Option<IoTDevice>,
}
impl Node {
pub fn new(key: char, device: Option<IoTDevice>) -> Link {
Box::new(Node {
key: key,
next: HashMap::new(),
value: device,
})
}
}
impl PartialEq for Node {
fn eq(&self, other: &Node) -> bool {
self.key == other.key
}
}
pub struct BestDeviceRegistry {
pub length: u64,
root: HashMap<char, Link>,
}
impl BestDeviceRegistry {
pub fn add(&mut self, device: IoTDevice) {
// デバイスのパスを一旦取っておく。
let p = device.path.clone();
// chars に分解する。
let mut path = p.chars();
// イテレータの1つ目を取得する（つまり戦闘の文字を取る）。
if let Some(start) = path.next() {
// 追加するので長さを +1
self.length += 1;
// キーが存在するかを確認してキーがなければノードを追加する。
let mut n = self.root.entry(start).or_insert(Node::new(start, None));
// パスを1文字1文字回す。
for c in path {
// ノードの次の文字を取る。
// 取って、そのキーでまた探してノードに含まれるかどうかを検索→なければノードを追加する。
// 以下、path のイテレーションが終わるまで続く。
let tmp = n.next.entry(c).or_insert(Node::new(c, None));
n = tmp;
}
// 最後にデバイスをノードに登録する。
n.value = Some(device);
}
}
pub fn find(&mut self, path: &str) -> Option<IoTDevice> {
let mut path = path.chars();
// 例のごとく次の文字を取得する
if let Some(start) = path.next() {
// 該当する文字に対するキーが存在していれば、次々文字を探していって見つかるまでやる。
self.root.get(&start).map_or(None, |mut n| {
for c in path {
match n.next.get(&c) {
// 該当する文字が見つかったら代入して返す。
Some(ref tmp) => n = tmp,
None => break,
}
}
n.value.clone()
})
} else {
None
}
}
pub fn walk(&self, callback: impl Fn(&IoTDevice) -> ()) {
for r in self.root.values() {
self.walk_r(&r, &callback);
}
}
fn walk_r(&self, node: &Link, callback: &impl Fn(&IoTDevice) -> ()) {
for n in node.next.values() {
self.walk_r(&n, callback);
}
if let Some(ref dev) = node.value {
callback(dev);
}
}
}
久々になってしまったけど続き（機械学習の勉強をしてた）。
B-Tree
B-Tree のルールは Knuth さんによって次のように定められている。
- Each node can only have order children.
- Each node that is not a leaf node or root has at least the ceiling of order/2 children.
- The root node has at least two children.
- All nodes hold order - 1 keys when they have order children.
- All leaf nodes appear on the same level.
赤黒木よりもバランシングのアルゴリズムはシンプルになる。
図の通りで、キーというのはその要素の持つ範囲になる。7, 16 という要素をもつとき、7以下、7より大きく16以下、16より大きい、みたいな感じでキーが用意される（本には書いてなかったけどつまり、要素同士は比較可能でなければならない気がする。これは赤黒木と同様かな？）。
yukiB-Tree への挿入は赤黒木よりは簡単だけどやはりちょっと複雑。
- データが挿入されるべきリーフノードを探す。
- リーフノードがその追加するアイテムを収容可能なとき（各要素は order - 1 より大きくなってはいけない）、アイテムをノード内の適切な位置に足す。
- リーフノードがいっぱいで収容不可能なときは、ノードを2分割する。1, 2, 3, 4 という要素をもつノードだった場合、1, 2 と 3, 4 にまずは分ける、みたいな感じ。で、中間のアイテムを親のノードに「promote」させる。あとはこれを繰り返す。
yuki本の説明だとやはりちょっとよくわからなかったので、この動画を見た。B-Tree のデモンストレーションが実装されていて挿入がアニメーションになっていてとてもわかりやすかった。
yuki基本的には B-Tree は常に
- search
- insert
- delete
の操作時には O(log(n)) で行える。
yuki- 二分探索木と比べると B-Tree は実装が複雑で、理論上の計算量は二分探索木より小さいケースがあるが、複雑さゆえに実装をミスると実行時間が長くなる可能性がある。
- Index に B-Tree が使用される理由は、ハードディスクとの相性にその答えがある。
- ハードディスクはデータを自身から読み取る際に、あるサイズ単位の塊（ブロック）で読み取りをする。
- 小さなデータをたくさん読み取る必要がある場合、複数のブロックを読み取る必要が出てくる。
- が、ハードディスクのヘッドの移動やディスクの回転などといった物理的な制約をはさむことになるため、コンピュータの CPU やメモリの読み込みと比べると非常に遅くなる可能性がある。
- B-Tree はその特性上、1つのノードに複数値をもつので、このブロック単位の読み書きという概念に非常によく適合する。
yukiB-Tree はワーストケースでもAccess, Search, Insertion, DeletionがO(log(N))で済むんだ。一方でHashTableなんかはワーストケースだとO(N)になる可能性がある。
この比較はそのままRDBMSとKey-Value Storeの比較にも使えて、
この記事の内容がようやく腑に落ちた気がする。B-Treeすごい。
このスクラップは2021/01/18にクローズされました