えびちゃんの日記

えびちゃん（競プロ）の日記です。

ポインタ系データ構造を書きたいな

おつまみ記事

ポインタ系データ構造（未定義お気持ち用語）を書きましょう。

まえがき

ここでポインタ系データ構造と呼んでいるのは、配列や二分ヒープ（のよくある実装）やセグ木（のよくある実装）とは違い、各要素が別の要素のアドレスを持つ必要があるようなものです。線形リストや平衡二分木などがわかりやすい例です。

競プロ界隈でポインタ系データ構造が話題になるときは、概ね次のようなデータ構造の話でしょう。

  • 高機能な平衡木*1
    • 添字でアクセスできるもの
    • merge/split が可能なもの
  • 高機能なヒープ
    • binomial heap, skew heap など併合可能 (meldable) なもの
    • Fibonacci heap など優先度の変更が可能なもの
  • 動的木
    • link/cut tree, top tree など
  • その他
    • trie, Aho–Corasick automaton など

高機能な平衡木は、言語の標準ライブラリで提供されるもの (std::map in C++, std::collections::BTreeMap in Rust) では足りないときに自前で実装する必要が出てくるようなものです。 これらは競技文脈では比較的避けられがちで、「（そういう）平衡木を使わずに解きたい」とか、なるべくなら実装しない・したくない人が多いように見えます。

「実装が大変」とか「実測だと重そう」とかそういう言い訳ばかりが目について嫌だな〜という気持ちがありつつ、「では自分は実装したいか？」というと「まぁ実装したくないですね」というのが正直なところです。 とはいえ、「そうした言い訳をしたまま一生を終えて満足か？」と問われると、それも違うかなという気もしてきます。最近はそういう感情ばかりで嫌になります。

そもそも、競プロ界隈にこういう風潮がある（気がする）のでポインタ系データ構造の導入用の教材はあまりなく、そうした状態で高度なポインタ系データ構造を見せられても「大変そう」という感情になってしまうのは、まぁ無理もないかなとも思います。 何年か前に FPS が流行り始めてた頃（当時は「母関数」という言い方で指されることが多かったですが）、FPS の体系的な教材がないまま高度な問題での適用例の記事だけがちらほらあり、魔法のようなものに感じていたのと似ているような気がします。

というわけで、簡単なものから書いていくことで、そうした「よくわからないけど難しそう」という忌避感を拭えたらいいなという気持ちがあります。

また、別の背景として、えびちゃんが Unsafe Rust の勉強をちゃんとしたいというところがあります。 ポインタ系のデータ構造を書くにあたっては Safe Rust だとどうにも限界があるためです。 Safe Rust で完結するようなものであればそれでよいですが、Unsafe Rust を使うべき状況で Safe Rust に固執するのはやはりよいとは思えません。 似た例として「浮動小数点数を使いたくないので整数に固執する」「浮動小数点数の取り扱いはよくわからない」がある気がします。

やりたいね

目標（この記事の範囲外）としては、添字でのアクセスと merge/split が可能な平衡木（そういう B-tree）を実装することです。 下記は簡単な例から始めるので Safe Rust でも実装できる部分もあるでしょうが、あくまで Unsafe Rust の練習ということで、生ポインタなどを遠慮せずに使いましょう。

下記では Rust の実装例しかないですが、C++ でも学習方針自体は参考になると思います。 ポインタまわりの未定義動作検出に関して、下記では Rust 前提で Miri を紹介していますが、C++（の UBSan など？）でどの程度そうしたことができるかはあまり知らないです。 C++ における strict aliasing rule まわりの事情に関しても忘れてしまいました。 C++ にこだわりがある人は調べてみるとよいのではないでしょうか。

基礎パート

基本的な操作として、下記のようなことができるようになりましょう。

  • 何らかの値を（実行時に）確保して、その値へのポインタを取得する
  • ポインタを介して値の読み書きをする
  • ポインタが指している値を解放する

たとえば次のような感じです。

fn main() {
    // 値を確保して生ポインタを取得
    let p: *mut _ = Box::leak(Box::new("a".to_owned()));

    // ポインタを介した値の読み書き
    unsafe {
        assert_eq!(*p, "a");
        *p += "b";
        assert_eq!(*p, "ab");
    }

    // 値の解放
    unsafe { drop(Box::from_raw(p)) };
}

借用のルールに関して、Safe Rust ではコンパイラがチェックしてくれていた部分を Unsafe Rust ではプログラマがチェックする必要があるので、それに関しても学んでおく必要があります。 最近は Tree Borrows というモデルを勉強するのがよいのでしょうか。

unsafe { ... } は「不正で危険なコードを書くのが許される*2」という意味ではなく、「コンパイラによって（静的に）安全性を保証できない部分を、プログラマが責任を持って書く」という意味なので、そうした自覚を持つ必要があります。

一旦 as *mut _ とすることで lifetime を消去することができ、コンパイラのお目こぼしをいただくことができます（有効なプログラムになるという意味ではないので注意です）。

fn main() {
    let mut a = 0;
    let p1 = unsafe { &mut *(&mut a as *mut i32) };
    let p2 = unsafe { &mut *(&mut a as *mut i32) };

    // 借用ルールを無視した値の読み書き（未定義動作）
    *p1 += 1;
    *p2 += 2;
    assert_eq!(a, 3);
}

注

Stacked Borrows というモデルにおいては、p2 を作った時点で p1 が失効してしまうので p1 += 1 が不正です。 Tree Borrows においては、p2 を作った時点では p1 はまだ待機中という扱いで p1 += 1 は有効ですが、その書き込みによって p2 が失効して p2 += 2 が不正になります。$\eod$

また、*mut _ ではなく std::ptr::NonNull を使うのがよいかもしれません。null でないことを保証する以外に variance の違いもあるので注意が必要です。variance についての説明は一旦先延ばしにします。

ツールの紹介

Rust では Miri というツールがあり、その機能の一つとして Stacked Borrows や Tree Borrows での違反アクセスのチェックがあります*3。 下記のように実行すればよいです。

% MIRIFLAGS=-Zmiri-tree-borrows cargo miri run

現状デフォルトでは Stacked Borrows を使うようなので、Stacked Borrows で試したい場合は cargo miri run のみで大丈夫そうです。

Miri では、違反アクセスチェックに加えてメモリリーク検出もしてくれるため、そうした部分のテストもできてうれしいです。

練習パート

こうしたことがわかってくれば、もう手を動かしたくなる頃だと思うので、簡単なデータ構造から実装していきましょう。

まずは、“平衡一分木” としての線形リスト (linked list) を実装してみます*4。 ちゃんとしたクラスの形でまとめなくても、イメージを掴むところまでできればよいかもしれません。 イメージがつきにくそうであれば、クラスの形にしてみる練習をした方がいいかもしれません。

実装例

use std::ptr::NonNull;

struct ListNode {
    val: i32,
    next: Option<NonNull<ListNode>>,
}

pub struct List {
    first_last: Option<(NonNull<ListNode>, NonNull<ListNode>)>,
}

impl ListNode {
    fn new(val: i32) -> NonNull<Self> {
        NonNull::from(Box::leak(Box::new(Self { val, next: None })))
    }
}

impl List {
    pub fn new() -> Self { Self { first_last: None } }
    pub fn push(&mut self, elt: i32) {
        let node = ListNode::new(elt);
        if let Some((_, last)) = &mut self.first_last {
            unsafe { (*last.as_ptr()).next = Some(node) };
            *last = node;
        } else {
            self.first_last = Some((node, node));
        }
    }
    pub fn iter(&self) -> impl Iterator<Item = i32> + '_ {
        std::iter::successors(
            self.first_last.map(|(first, _)| first),
            |node| unsafe { (*node.as_ptr()).next },
        )
        .map(|node| unsafe { (*node.as_ptr()).val })
    }
}

impl Drop for List {
    fn drop(&mut self) {
        if let Some((first, _)) = self.first_last {
            let mut next = Some(first);
            while let Some(node) = next {
                next = unsafe { (*node.as_ptr()).next };
                unsafe { drop(Box::from_raw(node.as_ptr())) };
            }
        }
    }
}

#[test]
fn sanity_check() {
    let mut list = List::new();
    assert!(list.iter().eq([]));

    list.push(1);
    list.push(2);
    assert!(list.iter().eq([1, 2]));
}

これくらいのことができれば、（該当のデータ構造自体の理解はしている前提で）実装できるようになっているのではないでしょうか。 少なくとも、言語側の問題で「ポインタに関する書き方がわからない・知らないので実装できない」という状態は脱せている気がします。

必要なら、簡単のために平衡しているとは限らない二分木を書いてみるとよいかもしれません。

他の練習

$n$ 個のノードを作り、$(i, p_i)$ を受け取って「$i$ 番目のノードの向き先を $p_i$ 番目のノードにする」という更新をする functional graph 状のおもちゃデータ構造を書いたりしました。もちろんこんなのは本来 Unsafe Rust を使わずに配列で実装できます。

実践パート

練習しているうちに、「そういえばポインタ系データ構造として Fibonacci heap ってあったね」と思い出したので、書きました。 Fibonacci heap は、通常の優先度つきキューの操作 (new, push, pop) の他に、別の Fibonacci heap を併合する操作 (meld) と優先度を上げる操作 (urge)*5 ができます。 計算量は下記です。償却計算量のものは * でマークしています。

操作 時間計算量
new, push, meld $O(1)$
pop $O(\log(n))$ *
urge $O(1)$ *

さて、urge を適切に用いることで、Dijkstra 法の時間計算量を $\Theta(m\log(n))$ から $\Theta(m+n\log(n))$ に落とすことができます。 たとえば ARC 064 E のグラフでは $m = \Theta(n^2)$ なので、前者は $\Theta(n^2\log(n))$、後者は $\Theta(n^2)$ となります。 もちろん、urge を用いないで $\Theta(m\log(n))$ 時間の Dijkstra 法を Fibonacci heap で実装することもできます。

アルゴリズム 実測
BinaryHeap, $\Theta(n^2\log(n))$ 107 ms
FibonacciHeap, $\Theta(n^2\log(n))$ 1772 ms
FibonacciHeap, $\Theta(n^2)$ 25 ms (!)

ポインタ系データ構造だけあって定数倍は重いようですが、オーダーを落としたものでは標準の BinaryHeap のものよりも高速だったのでうれしかったです。

一応、AtCoder のテストケース一つずつに対して Miri (Tree Borrows) で検証したので、未定義動作やメモリリークに関しては大丈夫だと思っています。 全テストケースでのテストは、通常の cargo run --release では 1 秒弱、cargo run では 5 秒弱で終わるのに対して Miri では 2.6 日 程度かかり、まぁちょっと時間がかかるねえといった感じでした。

データ構造に関して補足

Fibonacci heap は以前も書いたことがあり、なつかしい気持ちになりました。 urge の計算量保証（expected ではなく worst で、$O(1)$ 時間）のために、木構造をやや特殊な形で持つところが好きです。

前提として、次のことがあります。

  • 指定したノードを親から切り離す操作を worst $O(1)$ 時間でできる必要がある。
  • 指定したノードに子を追加する操作も worst $O(1)$ 時間でできる必要がある。
  • $k$ 番目の子を取得するという操作は必要ない。

（親から見て）各子へのポインタを配列や tree map で持つと削除が $O(1)$ 時間でできず、hash map で持つと worst が保証できなくなります。 そこで、各子は親へのポインタを持ちつつ親は「代表の子」へのポインタ一つだけを保持し、子を切り離す際は「自分が代表の子であれば、（同じ親を持つ）他の子を代表にする」という操作をするようにします。 子から他の子に worst $O(1)$ 時間でアクセスできるようにするため、子同士は円環状にポインタで結んでおきます (circularly-linked list)。

[                       parent                       ]
    ^             ^ |             ^              ^
    |             | v             |              |
[child 1] <--> [child 2] <--> [child 3] <--> [child 4]
    ^                                            ^
     \------------------------------------------/

アスキーアートで表現するのがやや難しいですが、こういう感じです（2 番の子が代表）。

また、urge は「この値（ノードがどこにあるかは知らない）の優先度を上げたい」ではなく「このノードの優先度を上げたい」という操作です。 前者（検索から行う必要がある）ではおそらく worst $O(1)$ 時間 を達成できないため、ノードを指定できるようなインタフェースを提供する必要があります。

meld に関しても、（pop を行うまで実際の処理を遅延させて）worst $O(1)$ 時間で行います。このため、木構造たち（の根）を linked list で管理します*6。

「Rust Fibonacci heap」で Google 検索して出てくる実装・記事を上から 5 つくらい読みましたが、このあたりをちゃんとしているものがほぼなかったのでかなしかったです。

勉強パート

今は B-tree のお勉強をしています。 Fibonacci heap の項でも少し触れましたが、実装を行う前に計算量解析を含めて理解しておくことで、誤った実装をしてしまうのを防げると思います。

また、allocate の操作が worst $O(1)$ 時間なのかは知らない（そう仮定するのが妥当なのかも知らない）ので、調べるのがよさそうな気がしています。

あとがき

でもそれなりの教材があっても競プロ界隈でポインタ系データ構造が流行る気がしないねえ。 流行らないの自体はいいけど、そうしたデータ構造を食わず嫌いしたまま「アルゴリズムに詳しい集団」みたいな顔をしているのが気に食わない。 と思ったんですが、もしかして最近はそういう顔をしている人はいないですか？ 昔も少数だったかも。

Fibonacci heap のような木構造の持ち方とか、計算量に $\alpha(n)$ が出てくるような設計とかは、あまり一般的なテクという感じの広まり方をしていない気がしていて、もっと日の目を浴びないかなあと思ったりしています。 既存のマイナーテクが非有名というだけでなく、（セグ木とかの慣れ親しんだデータ構造以外の）データ構造を新しく考える機会があまりないような気がします。 こうしたことに興味のある層はあまりいないのでしょうか。 あるいはもう比較的枯れてしまっている部分なのかしら。

そういえば fat-node red-black tree や sardine tree / fusion tree などのお勉強をしなきゃと思っていたのを忘れていました。

あと簡潔データ構造に関しても記事を書こうとして寝かせたままになっているのを忘れています。

おわり

一旦おわりです。B-tree が書けたらまた自慢しに来ます。

*1:必ずしも二分木とは限らないため、こうした呼び方をしています。現行の Rust の標準ライブラリでは $2b$-分木 ($b=6$) になっていそうです。B-tree なので、$b$ 以上 $2b$ 以下分木でしょうか。

*2:コンパイラ「私は許そう。だがこいつが許すかな！」

*3:静的解析ではなく、実際に実行して違反が起きているかを確認するものなので、単体テストとして使う場合は入力ケースを適切に考える必要があります。

*4:競プロ頭の人は「worst $\Theta(n)$ 時間なのに平衡とは？」と思いそうですが、根から全ての葉へのパス（一意）の長さが一定であることを指して平衡ということですね。

*5:最小値を取り出したい文脈では decrease-key と呼ぶ場合もあり、Introduction to Algorithms ではそれを採用していたと思います。ここでは一般の優先度っぽい名称を採用しました。以前は prioritize と呼んでいました。

*6:ところで、一般の meldable heap で push を「要素一つだけの heap を作成して meld する」と言い換えるやつが好きです。