パンケーキソートで配列を並び替える

パンケーキソートを使用する

パンケーキソート (pancake sort) は、配列の 先頭から任意の位置まで を一度に反転（フリップ）できる操作だけを使って整列する比較ソートである。スパチュラで積み重ねたパンケーキの上面から何枚かをひっくり返すイメージから名付けられた。

未整列の範囲: 長さ size の接頭辞 A[0 .. size-1] に注目する（最初は size = n）。
最大の探索: その範囲で最大要素の位置 maxIdx を見つける。
先頭へ: maxIdx ≠ 0 なら A[0 .. maxIdx] を反転し、最大を先頭へ運ぶ。
確定位置へ: A[0 .. size-1] を反転し、最大を範囲の末尾（整列後の正しい位置）へ運ぶ。
繰り返し: size を1つ減らし、size = 2 まで繰り返す。

procedure flip(A, end)
  for lo from 0 to end - 1
    swap(A[lo], A[end - lo])

procedure pancake_sort(A)
  n = length(A)
  for size from n down to 2
    maxIdx = index of maximum in A[0 .. size - 1]
    if maxIdx != size - 1 then
      if maxIdx != 0 then
        flip(A, maxIdx)
      flip(A, size - 1)

反転1回は O(k)（k は反転長）の要素移動を伴う。素朴な実装では各ラウンドで最大を線形探索するため、最悪でも平均でも O(n²) の時間になりやすい。

追加配列を使わなければ 空間計算量は O(1) のインプレースソートである。反転は等しい値の相対順序を入れ替えうるため、一般に 不安定 なソートとして扱われる。

操作が「接頭辞の反転」に限定されるという制約下での整列問題として知られ、フリップ回数を最小化する研究（パンケーキ問題）とも結びつく。実務の汎用ソートとしてはあまり使われないが、アルゴリズム教育では許可される操作が少ない場合の整列例としてよく登場する。

接頭辞の反転だけという制約は人工的だが、許される操作が少ない状況での整列や、フリップ回数の最小化といった組合せ論的な側面を学ぶ題材として有用である。大規模データの実用ソートには、クイックソートやマージソートなどが一般的に選ばれる。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000039	0.000432	1662	1668
512	0.000165	0.001256	1666	1672
1024	0.000585	0.003192	1674	1680
2048	0.002193	0.023284	1690	1696
4096	0.007713	0.033231	1722	1728
8192	0.028133	0.335716	1786	1792
16384	0.103849	0.432677	1917	1924
32768	0.458149	1.456860	2178	2184

計測に使用したコードを表示する

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 = 15;
const RUNS: usize = 8192;
fn flip_prefix(a: &mut [usize], end: usize) {
    let mut lo = 0;
    let mut hi = end;
    while lo < hi {
        a.swap(lo, hi);
        lo += 1;
        hi -= 1;
    }
}

fn pancake_sort(a: &mut [usize]) {
    let n = a.len();
    for size in (2..=n).rev() {
        let mut max_idx = 0;
        for i in 1..size {
            if a[i] > a[max_idx] {
                max_idx = i;
            }
        }
        if max_idx != size - 1 {
            if max_idx != 0 {
                flip_prefix(a, max_idx);
            }
            flip_prefix(a, size - 1);
        }
    }
}

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

    pancake_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