2025-03-10

std::syncの使い方

この記事は主にstd::syncのドキュメントをまとめたものです。

`std::sync`

std::syncはArc, Barrier, Condvar, mpsc, mpmc, Mutex, Once, OnceLock, LazyLock, RwLockなどのモジュール, 構造体, トレイトを提供している。

このモジュールは並行処理とかにおいても命令が予期した順番で行われたりすることを目的にロックとかそういう概念のものを実装している。

コンパイラによる命令の並び替えとかプロセッサが複数の命令を同時に行ったりとかマルチプロセッサの複数スレッドとかを防ぐためにsync::atomicモジュールが役に立つかもしれない。

sync::atomicは低レイヤーだから, 高レベルな同期のために抽象化されたオブジェクトもある。この記事ではsync::atomicについては取り扱わない。

`Arc`

ArcはAtomic Reference-Counted pointerで, Rcのマルチスレッドバージョン。だいたいはRcと同じだけど, 可変性がほしいときはCellとかRefCellのマルチスレッド版であるMutex, RwLockとかアトミックな型を使うこと。後内部の参照カウントにアトミック型をつかってるからちょっと重いからスレッド安全性が欲しいわけでもないならRcを使うべき。中身の型がSyncでSendじゃなきゃArcもSync, Sendにできない。ArcにもRcと同じようにWeakバージョンがあったりDerefを実装してたりする。

`Barrier`

Barrierはマルチスレッドで片方のスレッドがある地点に到達するまで待つのを保証する。公式ドキュメントの例を下に示す。

    use std::sync::Barrier;
    use std::thread;
    
    let n = 10;
    let barrier = Barrier::new(n);
    thread::scope(|s| {
        for _ in 0..n {
            // The same messages will be printed together.
            // You will NOT see any interleaving.
            s.spawn(|| {
                println!("before wait");
                barrier.wait();
                println!("after wait");
            });
        }
    });

すべてのbefore waitがプリントされてからafter waitがプリントされる。

`Condvar`

CondvarはCondition Variableで, 特定のイベントが起きるまでスレッドをブロックして待機させる。公式ドキュメントの例を改変したものを下に示す。

    use std::sync::{Arc, Mutex, Condvar};
    use std::thread;
    
    let pair = Arc::new((Mutex::new(false), Condvar::new()));
    let pair2 = Arc::clone(&pair);
    
    thread::spawn(move || {
        let (lock, cvar) = &*pair2;
        let mut started = lock.lock().unwrap();
        *started = true;
        // cvarを通じてこのスレッドの開始を知らせる。
        cvar.notify_one();
    });
    
    let (lock, cvar) = &*pair;
    let mut started = lock.lock().unwrap();
    while !*started {
        started = cvar.wait(started).unwrap();
    }

基本的にはこんな感じでMutexとペアにする。

主なメソッドを以下に示す。(型などを省略してわかりやすく表記している)

`new`

`wait(&self, guard) -> Result<MutexGuard>`

通知を受けるまでスレッドをブロックする。guardはMutexのロックをとったときに取得できるやつで, これをアンロックして, 関数が返ってきたら再度ロックを取得する。

最適化とかOSのスケジューリングでwaitが勝手に解除されることがあるから条件変数の値を確認することが必要

`notify_one`

ブロックされているスレッドを一つ呼び起こす。

すべて呼び起こすnotify_all, タイムアウト付きのブロックを行うwait系メソッドや関数で条件判定するwait系メソッドもある。

`mpsc`

mpscはマルチプロデューサー, シングルコンスーマのFIFO(先入れ先出し)キューを提供するSender, SyncSender, Receiverを提供する。

SenderもSyncSenderもReceiverにデータを送るのにつかわれる。マルチプロデューサだから複数スレッドから同時に送れるようにクローン出来る。

channelを使えば非同期(受信が開始されたかにかかわらず送信できる), 無限バッファチャンネルである(Sender, Receiver)タプルを取得できる。

sync_channelを使えば同期(受信が開始されるまで送信のスレッドをブロック)固定サイズバッファチャンネルである(SyncSender, Receiver)を取得できる。バッファサイズは0にもできてチャンネルを直接送る"ランデブー"チャンネルにできる

送受信はResultを返して, もしドロップしてたらエラーが返される。

`mpmc`

experimentalだけどマルチコンスーマを実現する。

`Mutex`

ミューテックス, 可変排他機構, ロックを利用して一つ以上のスレッドであるデータにアクセスできるのを保証する。

あるスレッドがMutexを保持しててパニックしたらMutexの中身が不正な状態になってるかもしれないから、そういう時は同じデータを共有してるMutexのロックを取得しようとしてもエラーが返ってくる。だからMutexのlockやunlockはResultを返すようになっている。でもエラーが返ってきたからと言ってもう使えないかというとそうでもなくてエラーのinto_innerメソッドを使えばもう一回中のデータにアクセスできる。でも壊れていないか保証はできない。

`Once`

一度だけ行われるスレッドセーフな大域初期化ルーチンのためにある。他の型の実装に使われることが多い。基本はOnceLockを使おう。

`OnceLock`

スレッドセーフな, 一度きりの, 呼び出し元によって異なる初期化関数が呼ばれるかもしれない変数の初期化を行う。 OnceCellのスレッドセーフバージョン

`LazyLock`

LazyCellのスレッドセーフバージョン

`RwLock`

reader-writer lock, reader-writerモデルに基づく排他制御機構で, 複数のreaderか一つだけのwriterを許容する。Mutexが単純なロックを利用していたのに対して, readerが複数存在するのを許容する。

同じくパニックしてたら不正な状態になるかもしれないし回復することもできる。

2025-03-10

std::rcの使い方

この記事は主にstd::rcのドキュメントをまとめたものです。

`std::rc`

std::rcはRc, WeakRcという2つの構造体を定義しているモジュールです。

RcとはReference Countedのことで, シングルスレッドの参照カウントポインタである。

型Rc<T>はTに対する所有権の共有を提供し, ヒープに置かれる。Rcにcloneを呼ぶと同じヒープの位置に対する新しいポインタを返す。最後のRcポインタが破壊されるとそのヒープにある中身の値もドロップされる。

Rcは共有参照だから可変ではない。Rcの中の値に対する可変参照を獲得することはできない。もし必要ならCellやRefCellを使うこと。

Rcはnon-atomicなリファレンスカウントを使ってるからオーバーヘッドは軽いけどスレッド間で送られることはできないしSendTraitをも実装していない。スレッド間で送られていないかはコンパイル時にチェックされる。もしマルチスレッド環境が欲しいならstd::sync::Arcを使う。

downgradeメソッドで所有権を持たないWeakポインタを作ることができて, 逆にWeakにはupgradeもあるけど, もうドロップされてたらNoneになる。Weakはその位置にある値の生存は維持しないけどその位置はする。(位置取りを行う。)

Rcの循環参照があったら値をドロップできないからWeakが存在する。(C++とかのスマートポインタとかと同じ)

Rc<T>はDeref traitを実装してるからRc<T>からTのメソッドを呼べる。名前衝突を避けるためにRc<T>のメソッドを呼ぶときはRc::downgrade(..)みたいに構造体から呼ぶこと。

Weakは中の値がドロップしてるかもだからそっから中の値のメソッドを呼ぶことはできない。

cloneは構造体から呼んでも(::を使う), インスタンスから呼んでも(.を使う)いいけど慣習的には構造体から呼ぶ。

RcもWeakも内部的にはRcInnerという構造体を使ってて, RcInner<T>の疑似コードは下のようになる。

    struct RcInner<T> {
        value: T,
        strong: usize,
        weak: usize,
    }

Rcがドロップされて内部のstrongが0になったら, Rc::drop_slowというメソッドが呼ばれて, これはこんなコード

    unsafe fn drop_slow(&mut self) {
        // strong weakポインタを再構築して, この変数がこの関数のスコープの外に行ったときにドロップすることで
        // `T`のデストラクタがパニックしてもメモリが解放されることを保証する。
        let _weak = Weak { ptr: self.ptr, alloc: &self.alloc };

        // 中身のオブジェクトを破壊する。
        unsafe {
            ptr::drop_in_place(&mut (*self.ptr.as_ptr()).value);
        }
    }

drop_in_placeはポインタのドロップを呼び出す関数。

Weakのdropはこんなコード

    impl<T> Drop for Weak<T> {
        fn drop(&mut self) {
            let inner = if let Some(inner) = self.inner() { inner } else { return };

            inner.dec_weak();
            // weakが0ならstrongも0だからメモリを解放する。
            if inner.weak() == 0 {
                unsafe {
                    self.alloc.deallocate(self.ptr.cast(), Layout::for_value_raw(self.ptr.as_ptr()));
                }
            }
        }
    }

つまりメモリの解放はWeakで行われ, RcはWeakのdropを利用してドロップとメモリの解放をしているっぽい。

2025-03-05

Rustのstd::cellモジュール/Cell, RefCell, OnceCell, LazyCellの使い方

この記事は主にstd::cellのドキュメントをまとめたものです。

`std::cell`

std::cellは主にCell, RefCell, OnceCell, LazyCellという四つの構造体を定義しているモジュールです。

Rustのメモリ安全性は, 通常任意の型Tに対して, 取得できる参照が可変参照&mut T一つか, & Tいくつかという二種類のどちらかしかできないという借用ルールに基づいていて, このルールが厳しすぎる状況もある。
std::cellに含まれる構造体はこの借用ルールを超え, あるルール下で複数の可変参照を持つためにある。
普通オブジェクトの内部の値を変更するにはそのオブジェクト自身の可変参照を持っていないとできないのをinherited mutation(継承可変性)という一方で, これらの構造体を利用して参照から値を変更できるのを内部可変性という。
これらの構造体はSyncじゃないからそういうのが欲しいならstd::syncにある構造体を使う。

`Cell`

Cellは実際に指している値に対する可変参照を渡したり, 中の値を置き換えることなく中の値を取り出したりできない。だから中の値に対して複数の可変参照が同時には存在しないことが保証できる。 CellはCopyTraitを実装している型に対して, 中の値を複製して渡すgetメソッドを, DefaultTraitを実装している型に対して, 中の値を取得しつつデフォルト値をセットするtakeメソッドを, どんな型に対しても新しい値に置き換えて元の値を取得するreplaceメソッド, 自分を消費して中の値を取得するinto_innerメソッド, 中の値をドロップしつつ新しい値をセットするsetメソッドを提供している。
これらはどれも&Cellから呼び出しながらCellの中の値を変更することができる。
Cellは他の三つより優先的に使われるべきで, 数字みたいにコピーにリソースがかからない型に推奨される。もっと大きかったりコピーがない型にはRefCellがいい。

コード例

use std::{cell::Cell, fmt::Display};

    struct Something {
        i: Cell,
    }
    
    impl Something {
        fn change_inner_with_immutable_borrow(&self) {
            self.i.set(42);
        }
    }
    
    impl Display for Something {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.i.get())
        }
    }
    
    fn main() {
        let s = Something { i: Cell::new(0) };
        s.change_inner_with_immutable_borrow();
        println!("{}", s); // 42
    }

といった感じに, mutで宣言してない変数に対して中の値を変更できます。

`RefCell`

RefCellは中の値に対して一時的で排他的な可変アクセスを取得する動的借用を実装する。普通の借用はコンパイル時に静的にチェックされるけどこれを使ったら借用は実行時にチェックされることになる。メソッドborrowを使えば中の値の参照が, borrow_mutを使えば可変参照が取得できる。これらのメソッドが呼び出されると可変参照が複数存在してないかとか可変参照と参照が同時に存在してないかとかがチェックされる。失敗したらpanic!する。

コード例

use std::{cell::RefCell, fmt::Display, rc::Rc};

    struct Something {
        i: Rc<RefCell>,
    }
    
    impl Something {
        fn change_inner_without_mutable_borrow(&self) {
            *self.i.borrow_mut() = 42;
        }
    
        fn cause_panic(&self) {
            let _borrow_mut = self.i.borrow_mut();
            self.i.borrow_mut(); // panic
        }
    }
    
    impl Display for Something {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.i.borrow())
        }
    }
    
    fn main() {
        let i = Rc::new(RefCell::new(0));
        let s = Something { i: i.clone() };
        s.change_inner_without_mutable_borrow();
        println!("{}", s); // 42
        println!("{}", i.borrow()); // 42
        s.cause_panic(); // already borrowed: BorrowMutError
    }

`OnceCell`

OnceCellはCellとRefCellを組み合わせたような感じで, 基本一回だけ値をセットする。これによってCellと違って値をムーブしたりコピーしたりすることなく参照を取得できるし, RefCellとも違ってランタイムのチェックを必要としない。でも値は一回セットされたらOnceCellへの可変参照がないなら変えることもできない。
メソッドは中の値への参照を取得するgetと中の値がセットされていないならセットするset, 初期化が必要なら初期化して中の値への参照を返すget_or_init, OnceCellへの可変参照を必要とするget_mutがある。

コード例

use std::cell::OnceCell;

    fn main() {
        let cell = OnceCell::new();
        println!("{:?}", cell.get()); // 何も入っていないからNone
        cell.get_or_init(|| 42);
        println!("{:?}", cell.get()); // Some(42)
        println!("{:?}", cell.set(1).unwrap_err()); // 初期化済みの状態でsetされたら中に入っていた1を返す
        let mut cell = OnceCell::new();
        cell.set(1).unwrap();
        *cell.get_mut().unwrap() = 2;
        println!("{:?}", cell.get()); // Some(2)
    }

`LazyCell`

LazyCellはOnceCellに似てるけど, 最初にクロージャをセットしておいて, 中の値が必要となったらクロージャーを評価する。つまりはOnceCellのget_or_initに毎回同じ関数を渡してるならそれを省略する感じ。デリファレンスすると中の値が取得できるし, OnceCellと比べたら冗長性がなくて目的がわかりやすい。

コード例

use std::cell::LazyCell;

    fn main() {
        let cell = LazyCell::new(|| {println!("初期化関数が呼び出された"); 42});
        println!("LazyCell は初期化されていない");
        println!("LazyCell の値: {}", *cell);
        println!("一回呼び出されたら何回も呼び出さない, {}", *cell);
    }

出力

LazyCell は初期化されていない
初期化関数が呼び出された
LazyCell の値: 42
一回呼び出されたら何回も呼び出さない, 42

どんな時に内部可変性を使うか

だいたいは使わないほうが楽だから内部可変性以外選択肢がないときに使うべき。具体的にいうと下の三つ

不可変なものの中に可変性を導入したいとき

Rcみたいな参照を分け合う型を使ってるとき, 借用ルールを守るために&mutできないんだけど, 中の値を変えるために RefCellを使うことができる。
上のコード例でもそうだったようにRefCellをRcで包むのはとても一般的。

論理的にイミュータブルなメソッドで可変性が欲しいとき

意味論的にはイミュータブルだけど, キャッシュみたいなのを使っているときにそれを変更することが必要な時に使う。後はTraitの定義的に &selfだけど中で値を変更したいときとか。

`clone`だけど値を変えたいとき

上の特別だけどたまにある場合。例えばRcは内部で参照カウントをしてるからcloneの時に内部データを変えたい。でもCloneTrait は&selfで宣言しちゃってるからCellを使って管理する。

2025-03-05

Rustのstd::backtraceモジュール

`std::backtrace`

std::backtraceはBacktraceという構造体を定義しているモジュールで, Backtraceはcapture という関数を定義しています。この関数を呼び出すとpanicが発生したときに出てくるようなバックトレースを取得できます。バックトレースを取得できない環境もあったりします。

コード例

use std::backtrace::Backtrace;

    fn main() {
        let bt = Backtrace::capture();
        println!("{:?}", bt.status());
        println!("{:#?}", bt);
    }

RustのPlayground で実行した実行結果載せます。Advanced OptionからBacktraceをオンにする。

実行結果

    Captured
    Backtrace [
        { fn: "playground::main", file: "./src/main.rs", line: 4 },
        { fn: "core::ops::function::FnOnce::call_once", file: "./.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs", line: 250 },
        { fn: "std::sys::backtrace::__rust_begin_short_backtrace", file: "./.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/backtrace.rs", line: 152 },
        { fn: "std::rt::lang_start::{{closure}}", file: "./.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs", line: 195 },
        { fn: "core::ops::function::impls:: for &F>::call_once", file: "/rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/core/src/ops/function.rs", line: 284 },
        { fn: "std::panicking::try::do_call", file: "/rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/std/src/panicking.rs", line: 584 },
        { fn: "std::panicking::try", file: "/rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/std/src/panicking.rs", line: 547 },
        { fn: "std::panic::catch_unwind", file: "/rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/std/src/panic.rs", line: 358 },
        { fn: "std::rt::lang_start_internal::{{closure}}", file: "/rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/std/src/rt.rs", line: 174 },
        { fn: "std::panicking::try::do_call", file: "/rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/std/src/panicking.rs", line: 584 },
        { fn: "std::panicking::try", file: "/rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/std/src/panicking.rs", line: 547 },
        { fn: "std::panic::catch_unwind", file: "/rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/std/src/panic.rs", line: 358 },
        { fn: "std::rt::lang_start_internal", file: "/rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/std/src/rt.rs", line: 174 },
        { fn: "std::rt::lang_start", file: "./.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs", line: 194 },
        { fn: "main" },
        { fn: "__libc_start_main" },
        { fn: "_start" },
    ]

LazyLockを使ってるっぽいから遅延評価されることでバックトレースを取得するコストは環境にもよるけど一回きりならそこまで高くなさそう。

自分で定義したエラーに持たせたりするやり方もありそう。

2025-03-04

ナンプレを自動で解くプログラム

春休み暇すぎてナンプレやってました。
数独にはいくつかテクニックと呼ばれるものがあるのですが, たまに見落としてしまうので, 機械でやってもらおうと思って数独を解くプログラムを作りました。
せっかく作ったから紹介したいと思ったので紹介します。
バックトラックとか使ってないので解けない場合もあります。

全体像

数独を解くプログラムはRustによる解答部分とhtml/css/jsによる表示部分に分かれています。本記事ではRustによる解答部分について説明します。コードはcell/_cell.rs, cell/cell.rs, puzzle/puzzle_index.rs, puzzle/puzzle_slice.rs, puzzle.rs, main.rsにファイル分割されています。
Githubに公開しているので, 興味があれば見てみてください。
内部では主に_Cell, Cell, PuzzleIndex, PuzzleSlice, Puzzleという構造体を使っています。

`_Cell`

_Cellはセルの値を表すenumで, そのセルの値が確定していた場合, Filled(u8)の形でその値を, まだ確定していない場合, Unfilled(u16)の形で候補をフラグで保持します。
楽なのでBitAndAssign<T: Into<u16>>, SubAssign<T: Into<u16>>, Into<u16> を実装しています.

`Cell`

Cellはセルの値を表すstructで, _Cellを内部に保持した上で。また, そのセルが所属する行, 列のインデックスであるPuzzleIndexを持ちます。
基本_CellとPuzzleIndexを継承したようなメソッドを実装しています。

`PuzzleIndex`

PuzzleIndexは行, 列のインデックスを持つstructです。行と列の意味が頭の中でごちゃごちゃになっていたせいでめちゃくちゃバグりました。
自分自身が指し示す位置のブロックのインデックスを返すblock_idxというメソッドを実装しています。

`PuzzleSlice`

PuzzleSliceはパズルの行/列/ブロックのいずれかを表すstructです。Rustに標準であるスライスを使いたかったけど当然行はともかく, 列やブロックだとデータがメモリ上でとびとびになっちゃってスライスは利用できないので, それを補うために作りました。
内部的にはPuzzleへの参照を保持し, Indexによる参照が来た時にPuzzleIndexを計算し, Cellへの参照を返します。これをmutにしたPuzzleSliceMutもあってこっちにはIndexMutも実装しています。これらはIteratorでも回せるようにしており, PuzzleIterという独自のイテレータを返します。ほんとはPuzzleIterMutも欲しかったけどライフタイムとかがややこしくてやめました。

`Puzzle`

Puzzleはパズルそのものです。PuzzleIndexによるIndexやIndexMutを実装しています。また, PuzzleSliceを返すrow, col, blockというメソッドを実装しています。実装しているメソッドはnaked-single/pair/triple, hidden-single, block-line reductionです。また, メソッドを実行して, 何か変化があったかを検知するために, hashを実装しており, これはパズルの状態に応じて一意な文字列を返し, これの値の変化に応じてメソッドを何回適用するか決めています。

最後に

最初はほんとはRc<RefCell<T>>の形でいろいろ管理することで, CellからPuzzleにアクセスしたりできるようにするつもりでしたが, Borrow Mut Errorみたいなのが多発したので断念しました。

2024-09-25

ABC372

当日参加ではないし今更ですが、自力で結構解けたので自分が解けた問題の解法を乗せておきます。解説というよりかはアウトプット位のイメージです。
解けた問題はABCDEの五問、使用言語はRustです。

各セクションはタイトルのAとかEとか押したら問題のページに、提出を押すと私のAC提出に飛んでいくようにリンクを張っているつもりです。掲載されているコードはロジックに関係ある部分を抜粋したものです。

A

提出

fn main() {
    input! {
        s: Chars,
    }
    for c in s {
        if c != '.' {
            print!("{}", c);
        }
    }
    println!();
}

解き方

'.'以外の時だけprintする

B

提出

fn main() {
    input! {
        mut m: usize,
    }
    let mut ans = vec![];
    let mut i = 10;
    while m != 0 {
        if 3usize.pow(i) <= m {
            ans.push(i);
            m -= 3usize.pow(i);
        } else {
            i -= 1;
        }
    }
    println!("{}", ans.len());
    println!("{}", ans.iter().join(" "));
}

解き方

3^10は引けるか, 3^9は引けるかというように, 貪欲法的にできるだけ大きい3のべき乗数を引いていきます。

C

提出

fn main() {
    input! {
        n: usize,
        q: usize,
        mut s: Chars,
        qs: [(usize, char); q],
    }
    let mut ans = 0;
    for i in 2..n {
        if s[i - 2] == 'A' && s[i - 1] == 'B' && s[i] == 'C' {
            ans += 1;
        } 
    }
    for (p, c) in qs {
        let p = p - 1;
        if 2 <= p && is_ABC(&s, p - 2) {
            ans -= 1;
        } else if 1 <= p && is_ABC(&s, p - 1) {
            ans -= 1;
        } else if is_ABC(&s, p) {
            ans -= 1;
        }
        s[p] = c;
        if 2 <= p && is_ABC(&s, p - 2) {
            ans += 1;
        } else if 1 <= p && is_ABC(&s, p - 1) {
            ans += 1;
        } else if is_ABC(&s, p) {
            ans += 1;
        }
        println!("{}", ans);
    }
}

解き方

is_ABC(&s, index)というのはs[p..p+2]が"ABC"になっているかをbool型で返す関数です. まずABCの連続部分文字列が元の文字列にいくつあるか数え, クエリを処理する際はもともとABCがある位置の文字を変えていたらansからその一つを引き, そのあとABCが形成されていたらansにその一つを加えます。

D

提出

fn main() {
        input! {
            n: usize,
            hs: [usize; n],
        }
        let mut highers = vec![n; n];
        // highers[i]: iより左にありかつiより大きいもののうち最も右のindex, nならばhs[..i] < hs[i]
        for i in 1..n {
            let mut j = i - 1;
            while j > 0 && hs[j] < hs[i] && highers[j] != n {
                j = highers[j];
            }
            if hs[j] > hs[i] {
                highers[i] = j;
            }
        }
        lprintln!("{:?}", highers);
        let mut ans = vec![0; n + 1];
        for i in 0..n {
            ans[highers[i]] += 1;
        }
        lprintln!("{:?}", ans);
        let mut sum = ans[n];
        for i in 0..n {
            ans[highers[i]] -= 1;
            sum += ans[i];
            if highers[i] == n || highers[i] < i {
                sum -= 1;
            }
            lprint!("{:?} ", ans);
            println!("{}", sum);
        }
}

解き方

計算量はO(n)くらいですかね. ビル i とビル j の間にビル j より高いビルが存在しないという条件は, iとjが近い値であればあるほど満たしやすくなることはわかるかと思います. 各jについて, この条件が満たされる最小のiを求めます(コード内の配列highers). 前からビルiを走査していったときに, このiについて, 何個のビルjが条件を満たしているのかここから求めることができます.

E

提出

#[derive(Debug, Clone)]
        struct OriginalGraph {
            see_theres: Vec,
            largest_10: Vec<[usize; 10]>,
        }
        
        impl OriginalGraph {
            fn new(n: usize) -> Self {
                let see_theres = (0..=n).collect::<Vec>();
                let mut largest_10 = vec![[0; 10]; n + 1];
                for i in 0..=n {
                    largest_10[i][0] = i;
                }
                Self {
                    see_theres,
                    largest_10
                }
            }
        
            fn kth_largest(&mut self, i: usize, k: usize) -> usize {
                let i = self.see_where(i);
                self.largest_10[i][k - 1]
            }
        
            fn see_where(&mut self, i: usize) -> usize {
                if self.see_theres[i] == i {
                    i
                } else {
                    self.see_theres[i] = self.see_where(self.see_theres[i]);
                    self.see_theres[i]
                }
            }
        
            fn add_edge(&mut self, n: usize, m: usize) {
                let n = self.see_where(n);
                let m = self.see_where(m);
                let (n, m) = if n < m { (n, m) } else { (m, n) };
                self.see_theres[n] = m;
                if n == m {
                    return;
                }
                let mut it = self.largest_10[n].iter().chain(self.largest_10[m].iter()).map(|i| *i).sorted().rev().take(10);
                for i in 0..10 {
                    self.largest_10[m][i] = it.next().unwrap();
                }
            }
        }
        
        
        #[fastout]
        fn main() {
            input! {
                n: usize,
                q: usize,
                qs: [(usize, usize, usize); q],
            }
            let mut graph = OriginalGraph::new(n);
            for (t, a, b) in qs {
                match t {
                    1 => {
                        graph.add_edge(a, b);
                        lprintln!("{a} {b}");
                        lprintln!("{:?}", graph);
                    }
                    2 => {
                        lprintln!("{a} {b} {}", graph.see_where(a));
                        let ans = graph.kth_largest(a, b);
                        if ans == 0 {
                            println!("-1");
                        } else {
                            println!("{}", ans);
                        }
                    }
                    _ => unreachable!(),
                }
            }
        }

解き方

解説に書いてあるUnionFindに10個の最大値を持たせるっていうのと変わらないです. 最大値をマージするときのself.largest_10[n].iter().chain(self.largest_10[m].iter()).map(|i| *i).sorted().rev().take(10) のメソッドチェーンが結構お気に入り. これのためにRust使ってると言っても過言ではない. self.largest_10[n].iter().chain(self.largest_10[m].iter()).map(|i| *i).sorted().rev().take(10).enumerate().for_each(...)にすればforループでindexを回すのを避けられましたかね

感想

最初はC問題の部分文字列を非連続なものだと思ったり, E問題の連結を直接つながっているものと考えたりしていました. 自分の中の言葉の定義と違うものが多い回でした.

2024-09-03

2-3-4木のRustによる実装

Rust アルゴリズム

赤黒木を実装しようと思いましたが, 操作の意味などが分からなくて困っていたので, その元となると言われている2-3-4木の実装をRustで行ってみました。

複雑なデータ構造で, 一応テストはしたつもりですが何かバグがあるかもしれません。ある程度雰囲気をつかむくらいの感覚でお読みいただければ幸いです。

実装したファイルをgithubにアップロードしておきましたので興味があれば見ていただけましたら

2-3-4木とは何か

この記事では, 2-3-4木は以下の定義を満たすデータ構造だと解釈しています

2-3-4木は木である
各ノードは1個以上3個以下のデータを持つ
各ノードは子を持たないか, 子を持つ場合はその個数はノードの持つデータの個数に1加えたものとなる
2-3-4木の根から任意の葉までの距離はすべて等しい

2-3-4木は平衡探索木の一種で, 各ノードについて, その保持するデータと子の間には順序関係が存在します.

具体的には, ノードの保持するデータはソートされており, どのデータも左右に二つの部分木が存在しかつ, データは左の部分木の最大値よりも大きく, 右の部分木よりも小さい状態になっています.

例えば, 3つのデータを保持するノードの保持するデータと部分木は下図の様な大小関係で表されます.

これによって, 2-3-4木ではある程度効率よく, データが木の中に存在するかなどを探索することができるようになります.

ヘルパー関数

具体的なロジックとは関係ないですが, unsafeを使った実装しか思いつかなかった部分がいくつかあったので, それらをヘルパー関数として定義しました.

配列への挿入

fn insert_to_array<S>(array: &mut [S], index: usize, value: S) {
    #[cold]
    #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
    #[track_caller]
    fn assert_failed(index: usize, len: usize) -> ! {
        panic!("insertion index (is {index}) should be <= len (is {len})");
    }
    let len = 3;

    if index > len {
        assert_failed(index, len);
    }

    unsafe {
        // infallible
        // The spot to put the new value
        let p = array.as_mut_ptr().add(index);
        // Shift everything over to make space. (Duplicating the
        // `index`th element into two consecutive places.)
        ptr::copy(p, p.add(1), len - index);
        // Write it in, overwriting the first copy of the `index`th
        // element.
        ptr::write(p, value);
    }
}

配列の指定した位置に値を挿入し, そこにあった値と以降の値を一つ右にずらします. lenは3で固定されており, 今回の実装のみにしか使えません.

配列からの削除

fn delete_from_array<S>(array: &mut [S], index: usize) -> S {
    #[cold]
    #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
    #[track_caller]
    fn assert_failed(index: usize, len: usize) -> ! {
        panic!("insertion index (is {index}) should be <= len (is {len})");
    }
    let len = 3;

    if index > len {
        assert_failed(index, len);
    }

    unsafe {
        // infallible
        // The spot to put the new value
        let p = array.as_mut_ptr().add(index);
        let ret = ptr::read(p);
        // Shift everything over to make space. (Duplicating the
        // `index`th element into two consecutive places.)
        ptr::copy(p.add(1), p, len - index);
        return ret;
    }
}

配列の指定した位置の値を削除し, それ以降の値を一つ左にずらします. 同じく今回の実装にしか使えません.

どちらもstd::Vecの同様の関数の実装を参考にしています.

メンバ変数の設計など

2-3-4木のノードは以下のような構造体で表されます.

pub struct Tree234<T> {
    data: [Option<T>; 4],
    children: [Option<Box<Tree234<T>>>; 4],
    size: usize,
}

dataはノードの保持するデータをOption型で保持しており, これがNoneの場合はデータが存在しないことを指します. 4つもデータ領域必要ないはずですが, 書き直すのがめんどくさいので4になっています.
childrenはノードの子をOption型で保持しており, これがNoneの場合は子が存在しないことを指します.
sizeはノードの保持するデータの個数を指します. この値は0, または1以上3以下の値を取ります. 0の場合は木が空であることを示しており, これは根ノードのみに許されるべきです.
data, childrenはどちらもソートされた状態を保持します.

また, 可読性のためにいくつか関数を用意しておきました.

impl<T: Ord> Tree234<T> {
    /**
     * valueを含んでいるかもしれない子のインデックスを返す. もしself.dataにvalueが含まれている場合はそこにおけるインデックスを返す.
     */
    fn find_index(&self, value: &T) -> usize {
        for i in 0..self.size {
            if value <= self.data[i].as_ref().unwrap() {
                return i;
            }
        }
        self.size
    }
    /**
     * selfが葉であるかどうかを返す.
     */
    fn is_leaf(&self) -> bool {
        self.children[0].is_none()
    }
}

挿入

挿入の実装は以下のようになります. 解説のため, 本来のコードからは少し変えてあります.

pub fn insert(&mut self, value: T) {
    let mut pos = self.find_index(&value);
    if self.size != 3 && self.is_leaf() {
        insert_to_array(&mut self.data, pos, Some(value));
        self.size += 1;
        return;
    }

    if self.size == 3 {
        // 自分がrootかつsizeが3の場合のみ if以下はすべてinsertが再帰的に呼び出される前に分割されるのでここには入らない.
        let mid = self.data[1].take();
        let left = Box::new(Self {
            data: [self.data[0].take(), None, None, None],
            children: [self.children[0].take(), self.children[1].take(), None, None],
            size: 1,
        });
        let right = Box::new(Self {
            data: [self.data[2].take(), None, None, None],
            children: [self.children[2].take(), self.children[3].take(), None, None],
            size: 1,
        });
        self.data = [mid, None, None, None];
        self.children = [Some(left), Some(right), None, None];
        self.size = 1;
    }

    let mut pos = self.find_index(&value);
    if self.children[pos].as_ref().unwrap().size == 3 {
        let mut child = delete_from_array(&mut self.children, pos).unwrap();
        let mid = child.data[1].take();
        let left = Box::new(Self {
            data: [child.data[0].take(), None, None, None],
            children: [
                child.children[0].take(),
                child.children[1].take(),
                None,
                None,
            ],
            size: 1,
        });
        let right = Box::new(Self {
            data: [child.data[2].take(), None, None, None],
            children: [
                child.children[2].take(),
                child.children[3].take(),
                None,
                None,
            ],
            size: 1,
        });
        let pos_ = self.find_index(mid.as_ref().unwrap());
        insert_to_array(&mut self.data, pos_, mid);
        insert_to_array(&mut self.children, pos_, Some(right));
        insert_to_array(&mut self.children, pos_, Some(left));
        self.size += 1;
        pos = self.find_index(&value);
    }
    self.children[pos].as_mut().unwrap().insert(value);
}

コードは再帰的な処理になっており, 大まかには再帰の終端処理->自分のノードが3つのデータをすでに保持している場合の処理->挿入されるべき子が3つのデータを保持している場合の処理->挿入されるべき子がすでに3つのデータを保持している場合の処理になります.

まずは終端処理から

let mut pos = self.find_index(&value);
if self.size != 3 && self.is_leaf() {
    insert_to_array(&mut self.data, pos, Some(value));
    self.size += 1;
    return;
}

selfが葉ノードかつ新しいデータを入れる余地がある場合, 適切な位置にvalueを挿入して処理が終了となります.

次に, selfに新しいデータを入れる余地がない場合, どうなるか見ていきます.

上の図の木に6を挿入する場合を考えます
2よりも6のほうが大きいので, 右のノードに6が挿入されることになりますが, 右のノードはすでに3つのデータを保持しているため, このノードを分割する必要があります.
分割の手順は, まず中央値を親ノードに渡し, 左の値, 右の値をそれぞれ親ノードの子ノードとして追加します. これによって, 親ノードは保持するデータと子ノードが一つずつ増え, 2-3-4木の条件を満たします.
また, 親ノードもまた3つのデータを保持している可能性もあり, その場合繰り上げのような処理が必要となるでしょう. 再帰を簡単にするために, 今回は道中にある3つのデータを保持するノードをすべて分割してから挿入することになっています.

これに対応するコードは以下になります.

if self.children[pos].as_ref().unwrap().size == 3 {
    let mut child = delete_from_array(&mut self.children, pos).unwrap();
    let mid = child.data[1].take(); // 中央値
    let left = Box::new(Self { // 左の値を保持するノード
        data: [child.data[0].take(), None, None, None],
        children: [
            child.children[0].take(), // もともと保持していた子ノードの左側にある二つはこれに持たせておく.
            child.children[1].take(),
            None,
            None,
        ],
        size: 1,
    });
    let right = Box::new(Self {
        data: [child.data[2].take(), None, None, None], // 右の値を保持するノード
        children: [
            child.children[2].take(),
            child.children[3].take(),
            None,
            None,
        ],
        size: 1,
    });
    let pos_ = self.find_index(mid.as_ref().unwrap());
    insert_to_array(&mut self.data, pos_, mid);
    insert_to_array(&mut self.children, pos_, Some(right)); // 同じインデックスに挿入する場合, 先に挿入したもののほうが後になる.
    insert_to_array(&mut self.children, pos_, Some(left));
    self.size += 1;
    pos = self.find_index(&value); // posを再計算
}
self.children[pos].as_mut().unwrap().insert(value); // 次の子ノードに再帰処理を託す

ここで, 次の再帰ではself.children[pos]が親ノードとなりますが, これは高々2つのデータしか保持されないことがわかるかと思います.

しかし, この方法では根ノードが3つの要素を持つ場合には対応できません. そのため, この場合は根ノードを分割する必要があります.

根ノードの分割では, 親ノードが存在しないので, 新しい中間値をデータとする根ノードをつくり, もともと左, 右にあった値をその子とします.

        if self.size == 3 {
            // 自分がrootかつsizeが3の場合のみ if以下はすべてinsertが呼び出される前に分割されるのでここには入らない.
            let mid = self.data[1].take();
            let left = Box::new(Self {
                data: [self.data[0].take(), None, None, None],
                children: [self.children[0].take(), self.children[1].take(), None, None],
                size: 1,
            });
            let right = Box::new(Self {
                data: [self.data[2].take(), None, None, None],
                children: [self.children[2].take(), self.children[3].take(), None, None],
                size: 1,
            });
            self.data = [mid, None, None, None];
            self.children = [Some(left), Some(right), None, None];
            self.size = 1;
        }

先にも述べたように, selfが何かの子ノードであった場合, そのsizeは高々2になるはずなので, この処理は根ノードにしか適用されないことになります.

これによって, 挿入処理が行えるようになりました.

削除

削除の実装は以下のようになります.

        pub fn delete(&mut self, value: &T) -> bool {
            if self.is_leaf() {
                let pos = self.find_index(value);
                if pos < self.size && self.data[pos].as_ref().unwrap() == value {
                    delete_from_array(&mut self.data, pos);
                    self.size -= 1;
                    return true;
                }
                return false;
            }
            let pos = self.find_index(value);
            let is_internal = pos < self.size && self.data[pos].as_ref().unwrap() == value;
            if !is_internal && self.children[pos].as_ref().unwrap().size > 1 {
                // いつかはここに引っかかるはず
                // 子ノードの大きさが2以上の場合, それを起点に再帰的に削除を行う.
                return self.children[pos].as_mut().unwrap().delete(value);
            }
            if !is_internal {
                self.delete_balance(pos);
                return self.delete(value);
            }
    
            self.delete_balance(pos);
            // 内部ノードである場合, 通り道全体にrotateとかしてから左側最大と交換して削除する
            let mut current = self.children[pos].as_mut().unwrap();
            while !current.is_leaf() {
                current.delete_balance(current.size);
                current = current.children[current.size].as_mut().unwrap();
            }
            let pos = self.find_index(value);
            let is_internal = pos < self.size && self.data[pos].as_ref().unwrap() == value;
            if is_internal {
                let mut current = self.children[pos].as_mut().unwrap();
                while !current.is_leaf() {
                    current.delete_balance(current.size);
                    current = current.children[current.size].as_mut().unwrap();
                }
                std::mem::swap(&mut self.data[pos], &mut current.data[current.size - 1]);
                return current.delete(value);
            }
            self.delete(value)
        }

        fn delete_balance(&mut self, pos: usize) {
            // 隣接兄弟ノードの大きさが2以上の場合, 回転を行う
            if (pos > 0 && self.children[pos - 1].as_ref().unwrap().size > 1)
                || (pos < self.size && self.children[pos + 1].as_ref().unwrap().size > 1)
            {
                self.rotate(pos);
            } else if self.size > 1 {
                // 隣接兄弟ノードの大きさが1で親要素の大きさが2以上の場合, マージを行う
                self.merge(pos);
            } else {
                // 高さを1下げる.
                self.shrink();
            }
        }

削除処理もまた再帰的な処理になっています. はじめに終端処理について説明します.

if self.is_leaf() {
    let pos = self.find_index(value);
    if pos < self.size && self.data[pos].as_ref().unwrap() == value {
        delete_from_array(&mut self.data, pos);
        self.size -= 1;
        return true;
    }
    return false;
}

selfが葉ノードの場合, 値がデータとして保持されているか探し, 保持されている場合はそれを削除します.

次に, selfのデータにvalueが存在せず, valueが存在する可能性のある部分木の保持するデータの個数が1より大きい場合です. これは単純に部分木に削除の再帰を渡すだけで済みます.

let pos = self.find_index(value);
let is_internal = pos < self.size && self.data[pos].as_ref().unwrap() == value;
if !is_internal && self.children[pos].as_ref().unwrap().size > 1 {
    // いつかはここに引っかかるはず
    // 子ノードの大きさが2以上の場合, それを起点に再帰的に削除を行う.
    return self.children[pos].as_mut().unwrap().delete(value);
}

特別視して考える必要がある場合に, 削除する値が存在する部分木が1つのデータしか保持していない場合があります.

上図から1や6, 8を削除する場合がそれにあたるでしょう. もし削除するデータがちょうどそこにあったら, データ数が0のノードが出来上がってしまいます. これを防ぐために, 削除の道中にある1つのデータしか保持していないノードはすべて2つ以上のデータを保持するように調整します. これには3つの方法があります.

回転

隣接する兄弟ノードのどちらかに2つ以上のデータを保持しているものがあれば, 回転と呼ばれる操作を行います. さきほど示した図でいう2や9がこれにあたります.

回転は, 自分と兄弟ノードに挟まれたデータの値を自分の値に加え, それがもとにあった位置に兄弟ノードから適切な値を持ってきます. このとき, 2-3-4木のデータとノードの順序関係が満たされるように注意します. また, 兄弟ノードのデータが一つ減るので, 兄弟ノードが保持する子ノードのうち(甥ノード?)もっとも自分に近いものを自分の子に加えます.

例として, 2を回転させる場合, 下図のようになります.

2-3-4木の定義を満たしつつ, 2を含むノードのデータ数が2になっていることがわかるかと思います.

回転のコードは以下のようになります.

fn rotate(&mut self, pos: usize) { // self.children[pos].sizeを1から2にする
    if pos > 0 && self.children[pos - 1].as_ref().unwrap().size > 1 {
        // 左の兄弟から値を持ってくる
        let brother_pos = pos - 1;
        let parent_pos = pos - 1;
        // data = [parent_data, self.data, None];
        // children = [*brother.children, *self.children];
        let parent_data = delete_from_array(&mut self.data, parent_pos); // 自分より一つ左にあるデータをとってくる.
        insert_to_array(
            &mut self.children[pos].as_mut().unwrap().data,
            0, // 既存のデータより小さいことが保証されるので0に挿入
            parent_data, 
        );
        let brother_size = self.children[brother_pos].as_mut().unwrap().size;
        let brother_data = delete_from_array(
            &mut self.children[brother_pos].as_mut().unwrap().data,
            brother_size - 1, // brotherのデータの最大のものを持ってくる.
        );
        insert_to_array(&mut self.data, parent_pos, brother_data);
        let brother_child = delete_from_array(
            &mut self.children[brother_pos].as_mut().unwrap().children,
            brother_size,
        ); // brotherの子の最も右にあるものを自分の最も左の子とする.
        let children = &mut self.children[pos].as_mut().unwrap().children;
        insert_to_array(children, 0, brother_child);
        self.children[brother_pos].as_mut().unwrap().size -= 1;
        self.children[pos].as_mut().unwrap().size = 2;
    } else {
        // 右の兄弟から値を持ってくる
        let brother_pos = pos + 1;
        let parent_pos = pos;
        // data = [self.data, parent_data, None];
        // children = [*brother.children, *self.children];
        let parent_data = delete_from_array(&mut self.data, parent_pos);
        insert_to_array(
            &mut self.children[pos].as_mut().unwrap().data,
            1,
            parent_data,
        );
        let brother_data =
            delete_from_array(&mut self.children[brother_pos].as_mut().unwrap().data, 0);
        insert_to_array(&mut self.data, parent_pos, brother_data);
        let brother_child = delete_from_array(
            &mut self.children[brother_pos].as_mut().unwrap().children,
            0,
        );
        let size = self.children[pos].as_mut().unwrap().size;
        let children = &mut self.children[pos].as_mut().unwrap().children;
        insert_to_array(children, size, brother_child);
        self.children[brother_pos].as_mut().unwrap().size -= 1;
        self.children[pos].as_mut().unwrap().size = 2;
    };
}

マージ

親のデータ数が2以上かつ兄弟ノードのどちらもデータ数が1の場合に使います. 先ほどの図では11を削除する場合がこれにあたるでしょう.

この場合, 適当な兄弟ノードを選んで, 二つのデータとその間にあったデータを自分の新たなデータとし, データ数が3のノードとします.
兄弟ノードの子ノードは自分のノードに加えます. これによって自分の子ノードの数は4になり, 親ノードのデータ数は1へり, 2-3-4木の定義を満たします.

例として, 11を削除する場合, 下図のようになります.

マージのコードは以下のようになります.

fn merge(&mut self, pos: usize) {
    // 兄弟要素の値と親要素のいい感じの値を自分のdataとし, 兄弟要素の子要素を自分の子要素とする.
    self.size -= 1;
    self.children[pos].as_mut().unwrap().size = 3;
    if pos == 3 { // 基本的には右の兄弟を選ぶが, posが3の場合は左の兄弟を選ぶ.
        let brother_pos = pos - 1;
        let parent_pos = pos - 1;
        let parent_data = delete_from_array(&mut self.data, parent_pos);
        let brother_data =
            delete_from_array(&mut self.children[brother_pos].as_mut().unwrap().data, 0);
        let data = &mut self.children[pos].as_mut().unwrap().data;
        insert_to_array(data, 0, parent_data);
        insert_to_array(data, 0, brother_data); // dataは[兄弟のデータ, 親のデータ, 自分のデータ]の順になり, これはソートされている.
        // 兄弟の子ノードを自分の子ノードとする.
        let brother_child0 = delete_from_array(
            &mut self.children[brother_pos].as_mut().unwrap().children,
            0,
        );
        let brother_child1 = delete_from_array(
            &mut self.children[brother_pos].as_mut().unwrap().children,
            0,
        );
        let children = &mut self.children[pos].as_mut().unwrap().children;
        insert_to_array(children, 0, brother_child1);
        insert_to_array(children, 0, brother_child0);
    } else {
        let brother_pos = pos + 1;
        let parent_pos = pos;
        let parent_data = delete_from_array(&mut self.data, parent_pos);
        let brother_data =
            delete_from_array(&mut self.children[brother_pos].as_mut().unwrap().data, 0);
        let data = &mut self.children[pos].as_mut().unwrap().data;
        data[2] = parent_data;
        data[3] = brother_data;
        let brother_child0 = delete_from_array(
            &mut self.children[brother_pos].as_mut().unwrap().children,
            0,
        );
        let brother_child1 = delete_from_array(
            &mut self.children[brother_pos].as_mut().unwrap().children,
            0,
        );
        let children = &mut self.children[pos].as_mut().unwrap().children;
        children[2] = brother_child0;
        children[3] = brother_child1;
    }
}

最後に, 親も兄弟もひとつずつしかデータを持っていない場合を考えます. 先ほどの図でいう1がこれにあたります.

この場合は, 縮小と呼ばれる処理を行います.

縮小では, 自分のデータと兄弟のデータを親ノードにまとめて, 親ノードをデータ数3のノードにします. 自分と兄弟の子ノードも親ノードの子とし, 整合性を保たせます.

1を削除した場合, 下図のようになります.

高さが左の部分木と右の部分木で異なってしまっていますが, 実際の処理では, 親ノードが何かの子ノードであれば, そのデータ数が1となることはないので(回転やマージによって修正される), この処理は根ノードの場合にのみ行われ, 高さについての条件も守られます.

縮小のコードは以下のようになります.

fn shrink(&mut self) {
    // self.data = [left.data, self.data, right.data, None];
    // self.children = [*left.children, *right.children];
    self.size = 3;
    insert_to_array(&mut self.data, 0, self.children[0].as_mut().unwrap().data[0].take());
    self.data[2] = self.children[1].as_mut().unwrap().data[0].take();
    assert!(self.children[1].as_mut().unwrap().children[0].is_some());
    // 上書きされた後に取得することを防ぐため, 3, 2, 1, 0の順で保存する.
    self.children[3] = self.children[1].as_mut().unwrap().children[1].take();
    self.children[2] = self.children[1].as_mut().unwrap().children[0].take();
    self.children[1] = self.children[0].as_mut().unwrap().children[1].take();
    self.children[0] = self.children[0].as_mut().unwrap().children[0].take();
}

また, 今回のコードでは, delete_balanceという関数を用意し, これらのどれを行うかを判断するようにしています.

fn delete_balance(&mut self, pos: usize) {
    // 隣接兄弟ノードの大きさが2以上の場合, 回転を行う
    if (pos > 0 && self.children[pos - 1].as_ref().unwrap().size > 1)
        || (pos < self.size && self.children[pos + 1].as_ref().unwrap().size > 1)
    {
        self.rotate(pos);
    } else if self.size > 1 {
        // 隣接兄弟ノードの大きさが1で親要素の大きさが2以上の場合, マージを行う
        self.merge(pos);
    } else {
        // 高さを1下げる.
        self.shrink();
    }
}

削除するデータが葉ノードにない場合

削除するデータが葉ノードにない場合も一つの悩みになるでしょう.

先ほど載せた図と同じものを再度載せておきます. この図で10をなにか特別な処理せずに削除した場合を考えましょう. データ数が1, 子ノード数が3あるノードができてしまいます.

この事態を避けるために, 葉ノードではないノードにあるデータを削除する場合, これを葉ノードにある適切なデータと交換します.

具体的には, このコードでは対象となるノードの左の部分木で最も大きい要素と交換することになっています.

交換が終わった後の図は次のようになります.

この操作は上で述べたマージや回転がすべて済んだ後に行う必要があります.

以上のことを踏まえて, 再度先ほどのコードを見ていきます.

if !is_internal { // internalでないかつ子ノードの大きさが1の場合
    self.delete_balance(pos);
    return self.delete(value);
}

自分の保持するデータにvalueが存在しない場合, delete_balanceを行ってから, もう一度is_internalの確認をすることになります.

これは回転などによって自分のデータにvalueが来るのを対策しています.

self.delete_balance(pos); // 根についてはここで回転やマージが行われる.
// 内部ノードである場合, 通り道全体にrotateとかしてから左側最大と交換して削除する
let mut current = self.children[pos].as_mut().unwrap();
while !current.is_leaf() {
    current.delete_balance(current.size);
    current = current.children[current.size].as_mut().unwrap();
}

自分のデータにvalueが存在する場合, まずは根について, そしてそこから通り道全体に回転やマージが行われます.

let pos = self.find_index(value);
let is_internal = pos &l self.size && self.data[pos].as_ref().unwrap() == value;
if is_internal {
    let mut current = self.children[pos].as_mut().unwrap();
    while !current.is_leaf() {
        current.delete_balance(current.size);
        current = current.children[current.size].as_mut().unwrap();
    }
    std::mem::swap(&mut self.data[pos], &mut current.data[current.size - 1]);
    return current.delete(value);
}
self.delete(value)

その後, 自分のデータにvalueがある場合はそれを左側最小と交換してから削除し, そうでない場合はself.deleteを行い, 上で述べた自分のデータにvalueがないかつ対象の子ノードのデータ数が1より大きい場合に引っかかる

終わりに

2-3-4木のRustによる実装を説明しました. バグとか無限にありそうな気がしますが, 実際二分探索を行おうとするときにこれを使うことはないと思うので雰囲気だけ味わっていただければと思います.

この記事を書く上で参考にしたウェブサイトなどを紹介します.

暇があったら赤黒木の実装もしようと思います. 2-3-4木は特別な処理が多くてかなり時間を要してしまいましたが, 赤黒木はもう少し簡単だったらうれしいです.

std::sync

Arc

Barrier

Condvar

new

wait(&self, guard) -> Result<MutexGuard>

notify_one

mpsc

mpmc

Mutex

Once

OnceLock

LazyLock

RwLock

std::rc

std::cell

Cell

コード例

RefCell

コード例

OnceCell

コード例

LazyCell

コード例

出力

どんな時に内部可変性を使うか

不可変なものの中に可変性を導入したいとき

論理的にイミュータブルなメソッドで可変性が欲しいとき

cloneだけど値を変えたいとき

std::backtrace

コード例

実行結果

全体像

_Cell

Cell

PuzzleIndex

PuzzleSlice

Puzzle

最後に

目次

A

解き方

B

解き方

C

解き方

D

解き方

E

解き方

感想

目次

2-3-4木とは何か

ヘルパー関数

配列への挿入

配列からの削除

メンバ変数の設計など

挿入

削除

回転

マージ

削除するデータが葉ノードにない場合

終わりに

`std::sync`

`Arc`

`Barrier`

`Condvar`

`new`

`wait(&self, guard) -> Result<MutexGuard>`

`notify_one`

`mpsc`

`mpmc`

`Mutex`

`Once`

`OnceLock`

`LazyLock`

`RwLock`

`std::rc`

`std::cell`

`Cell`

`RefCell`

`OnceCell`

`LazyCell`

`clone`だけど値を変えたいとき

`std::backtrace`

`_Cell`

`Cell`

`PuzzleIndex`

`PuzzleSlice`

`Puzzle`