スプレイソートを使用する

スプレイソート (splay sort) は、要素を順にスプレイ木 (splay tree) へ挿入し、その後、中順走査 (in-order traversal) ですべてのキーを読み出して昇順を得る比較ソートである。スプレイ木は、参照したノードを根へ持ち上げる（スプレイ操作）自己調整二分探索木であり、直近にアクセスした要素へ素早く再び到達できる性質を持つ。

  1. 挿入: 入力値を順にスプレイ木へ挿入する。各挿入のあと、挿入したキー（または探索経路上の最終ノード）が根へスプレイされる。
  2. 取出し: 中順走査でキーを昇順に列挙し、配列へ書き込む。
procedure splay_sort(elements)
  T = empty splay tree
  for x in elements
    insert_splay(T, x)
  return inorder_traversal(T)

スプレイ木の単一操作の最悪時間計算量は O(n) だが、任意の m 回の操作に対する償却時間計算量は O(log n) である（スプレイ木の償却解析）。n 個の挿入全体では償却 O(n log n)、中順走査は O(n) なので、合計は償却 O(n log n) となる。

素の二分探索木と異なり、スプレイ木は偏った入力でも木の高さを抑えやすい。一方、各挿入で回転が発生するため定数係数は AVL 木や赤黒木より大きくなりがちである。ノード用に O(n) の追加記憶域が必要で、入力配列だけをインプレースで整える実装ではない。

等しいキー同士の相対順序は木の実装や等値を左子・右子のどちらへ入れるかの規約に依存し、一般には安定ソートではない。次のデモでは、同じ値の棒が画面上で入れ替わらないよう、挿入の比較を値が異なれば値、等しければ元の位置 id の辞書式順にしている。これは可視化のための工夫であり、素のスプレイソートが安定であることを意味しない。

procedure insert_splay(T, x)
  if T is empty then
    T.root = new node(x)
    return
  splay(T, x)
  if x = T.root.key then
    increment count at T.root
  else if x < T.root.key then
    attach old left subtree of T.root to new node(x)
    make T.root the right child of new node(x)
    T.root = new node(x)
  else
    attach old right subtree of T.root to new node(x)
    make T.root the left child of new node(x)
    T.root = new node(x)

二分木ソートと同様、配列上の並びは挿入フェーズでは動かず、整列結果は中順走査で得る。スプレイ木は「直近に触ったキーが根に来る」という局所性を活かした辞書やキャッシュの実装でよく使われるが、一度だけ全要素を整列する用途では回転のオーバーヘッドから、配列を直接いじるクイックソートやマージソートのほうが実用的なことが多い。

計算量のまとめ

区分 時間計算量 空間計算量 備考
最悪（単一操作） O(n) O(n) 1 回の挿入・探索
償却（n 回挿入） O(n log n) O(n) スプレイ木の償却解析
中順走査 O(n) — 整列結果の取出し
安定性 — — 一般に不安定

計算時間量および空間計算量を計測する

Size Average time Maximum time Average memory Maximum memory
256 0.000018 0.001084 1694 1700
512 0.000040 0.000717 1710 1716
1024 0.000082 0.000487 1746 1752
2048 0.000184 0.000626 1817 1824
4096 0.000405 0.001059 1961 1968
8192 0.000925 0.004044 2249 2256
16384 0.002123 0.007383 2702 2708
32768 0.005260 0.018099 3780 3812
65536 0.014622 0.038418 6083 6116
131072 0.033458 0.142269 10692 10724
262144 0.078169 0.180472 19908 20052
計測に使用したコードを表示する 

set -euo pipefail

WORKDIR="$(mktemp -d)"
trap 'rm -rf "$WORKDIR"' EXIT

cat > "$WORKDIR/Dockerfile" <<'EOF'
FROM rust:1.95.0

WORKDIR /app

RUN mkdir -p src

RUN cat > Cargo.toml <<'CARGO'
[package]
name = "rust-benchmark"
version = "0.1.0"
edition = "2021"

[profile.release]
lto = true
codegen-units = 1
panic = "abort"
CARGO

RUN cat > src/main.rs <<'RUST'
use std::{
    env,
    process::Command,
    time::{Duration, Instant},
};
const MIN_POWER: u32 = 8;
const MAX_POWER: u32 = 18;
const RUNS: usize = 8192;


type Link = Option<Box<Node>>;

#[derive(Default)]
struct Node {
    value: usize,
    count: usize,
    left: Link,
    right: Link,
}

fn rotate_right(mut x: Box<Node>) -> Box<Node> {
    let mut y = x.left.take().expect("rotate_right");
    x.left = y.right.take();
    y.right = Some(x);
    y
}

fn rotate_left(mut x: Box<Node>) -> Box<Node> {
    let mut y = x.right.take().expect("rotate_left");
    x.right = y.left.take();
    y.left = Some(x);
    y
}

fn splay(mut root: Box<Node>, key: usize) -> Box<Node> {
    if key < root.value {
        if let Some(mut left) = root.left.take() {
            if key < left.value {
                if let Some(grand_left) = left.left.take() {
                    left.left = Some(splay(grand_left, key));
                    left = rotate_right(left);
                }
                root.left = Some(left);
                return rotate_right(root);
            }
            if key > left.value {
                left.right = left.right.take().map(|r| splay(r, key));
                if left.right.is_some() {
                    root.left = Some(rotate_left(left));
                    return rotate_right(root);
                }
                root.left = Some(left);
            } else {
                root.left = Some(left);
            }
        }
    } else if key > root.value {
        if let Some(mut right) = root.right.take() {
            if key > right.value {
                if let Some(grand_right) = right.right.take() {
                    right.right = Some(splay(grand_right, key));
                    right = rotate_left(right);
                }
                root.right = Some(right);
                return rotate_left(root);
            }
            if key < right.value {
                right.left = right.left.take().map(|l| splay(l, key));
                if right.left.is_some() {
                    root.right = Some(rotate_right(right));
                    return rotate_left(root);
                }
                root.right = Some(right);
            } else {
                root.right = Some(right);
            }
        }
    }
    root
}

fn splay_insert(root: Link, value: usize) -> Link {
    match root {
        None => Some(Box::new(Node {
            value,
            count: 1,
            left: None,
            right: None,
        })),
        Some(node) => {
            let mut node = splay(node, value);
            if node.value == value {
                node.count += 1;
                return Some(node);
            }
            if value < node.value {
                let mut new_node = Box::new(Node {
                    value,
                    count: 1,
                    left: node.left.take(),
                    right: None,
                });
                new_node.right = Some(node);
                Some(new_node)
            } else {
                let right = node.right.take();
                let mut new_node = Box::new(Node {
                    value,
                    count: 1,
                    left: None,
                    right,
                });
                new_node.left = Some(node);
                Some(new_node)
            }
        }
    }
}

fn drain_node(root: &Link, out: &mut Vec<usize>) {
    if let Some(node) = root {
        drain_node(&node.left, out);
        out.extend(std::iter::repeat(node.value).take(node.count));
        drain_node(&node.right, out);
    }
}

fn splay_sort(a: &mut [usize]) {
    let mut root = None;
    for &value in a.iter() {
        root = splay_insert(root, value);
    }
    let mut out = Vec::with_capacity(a.len());
    drain_node(&root, &mut out);
    a.copy_from_slice(&out);
}


fn benchmark_sort(array: &mut [usize]) {

    splay_sort(array);

}

fn shuffled(size: usize, seed: u64) -> Vec<usize> {
    let mut v: Vec<usize> = (1..=size).collect();

    let mut state = seed;

    for i in (1..size).rev() {
        state ^= state << 13;
        state ^= state >> 7;
        state ^= state << 17;

        let j = (state as usize) % (i + 1);

        v.swap(i, j);
    }

    v
}

fn memory_usage_kb() -> usize {
    let contents = std::fs::read_to_string("/proc/self/status")
        .unwrap_or_default();

    for line in contents.lines() {
        if let Some(rest) = line.strip_prefix("VmHWM:") {
            let kb = rest
                .split_whitespace()
                .next()
                .unwrap_or("0")
                .parse::<usize>()
                .unwrap_or(0);

            return kb;
        }
    }

    0
}

fn micros(d: Duration) -> u128 {
    d.as_micros()
}

fn run_once(size: usize, seed: usize) -> (u128, usize) {
    let expected: Vec<usize> = (1..=size).collect();
    let mut array = shuffled(size, seed as u64);

    let start = Instant::now();

    benchmark_sort(&mut array);

    let elapsed = start.elapsed();

    if array != expected {
        panic!(
            "sort failed with seed {} for size {}",
            seed,
            size
        );
    }

    (micros(elapsed), memory_usage_kb())
}

fn run_child(args: &[String]) {
    let size = args[2].parse::<usize>().expect("invalid size");
    let seed = args[3].parse::<usize>().expect("invalid seed");
    let (elapsed_us, mem) = run_once(size, seed);
    println!("{} {}", elapsed_us, mem);
}

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.get(1).is_some_and(|arg| arg == "--run-once") {
        run_child(&args);
        return;
    }

    println!(
        "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
        "Size",
        "Average time",
        "Maximum time",
        "Average memory",
        "Maximum memory"
    );

    println!(
        "|{:-<11}:|{:-<16}:|{:-<16}:|{:-<16}:|{:-<16}:|",
        "",
        "",
        "",
        "",
        ""
    );

    for power in MIN_POWER..=MAX_POWER {
        let size = 1usize << power;

        let mut total_time: u128 = 0;
        let mut max_time: u128 = 0;

        let mut total_mem: usize = 0;
        let mut max_mem: usize = 0;

        for seed in 1..=RUNS {
            let output = Command::new(env::current_exe().expect("failed to find current executable"))
                .arg("--run-once")
                .arg(size.to_string())
                .arg(seed.to_string())
                .output()
                .expect("failed to run benchmark child process");

            if !output.status.success() {
                panic!(
                    "benchmark child process failed: {}",
                    String::from_utf8_lossy(&output.stderr)
                );
            }

            let stdout = String::from_utf8(output.stdout)
                .expect("child process returned non-UTF-8 output");
            let mut fields = stdout.split_whitespace();
            let elapsed_us = fields
                .next()
                .expect("missing elapsed time")
                .parse::<u128>()
                .expect("invalid elapsed time");
            let mem = fields
                .next()
                .expect("missing memory usage")
                .parse::<usize>()
                .expect("invalid memory usage");

            total_time += elapsed_us;

            if elapsed_us > max_time {
                max_time = elapsed_us;
            }

            total_mem += mem;

            if mem > max_mem {
                max_mem = mem;
            }
        }

        let avg_time = total_time / RUNS as u128;
        let avg_mem = total_mem / RUNS;

        println!(
            "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
            size,
            format!("{}.{:06}", avg_time / 1_000_000, avg_time % 1_000_000),
            format!("{}.{:06}", max_time / 1_000_000, max_time % 1_000_000),
            avg_mem,
            max_mem
        );
    }
}
RUST

RUN cargo build --release

CMD ["./target/release/rust-benchmark"]
EOF

docker build -t rust-benchmark "$WORKDIR"
docker run --rm --init rust-benchmark