[Rust] スターリンソートと PartialOrd

ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる

— やんぎん (@4116You) 2019年7月28日

スターリンソートの実装

スターリンソートの実装がどんどん出てきています (Haskell, C#他) がまだ Rust はないようなので, 睡眠導入剤代わりに書きました. [追記] 書いたとき寝ぼけてたのでコード修正 (2019-07-31). [追記2] Copy をつければより Rust らしく書けたので差し替えます. scan って便利ですね. (2019-08-01)

fn stalin_sort<T: PartialOrd+Copy>(vec: &mut Vec<T>) {
    *vec = vec.iter().scan(vec[0], |prev, x| { 
        if *prev <= *x { *prev = *x; }
        Some(( *x, *prev <= *x ))
    }).filter_map(|(x,r)| if r { Some(x) } else { None }).collect();
}

驚くべきことに, 本来ソートは Ord にしか導入できない概念ですが, スターリンソートは PartialOrd に対しても実行することができます.

Ord と PartialOrd

良い機会なので Ord と PartialOrd について備忘録を兼ねてまとめておきます. 要は jawp とか集合論の教科書を読んでもらえばそれで良いのですが.

集合 $X$ が与えられたとき, その直積 $X \times X$ の部分集合 $R \subset X \times X$ のことを $X$ 上の 二項関係 と呼び, $x$, $y \in X$ が $(x, y ) \in R$ を満たすことを $$x R y$$ と表記します. 例えば二項関係 $R = \{ ( x, x ) | x \in X \}$ は等号を表します.

集合 $X$ の二項関係 $O$ が次の条件を満足するとき, $O$ を $X$ の 半順序 (partial order), 組 $( X, O )$ を 半順序集合 (partially orderd set, poset) と呼びます.

• 任意の $x \in X$ について $x O x$. (反射律)
• $x O y$ かつ $y O z$ ならば $x O z$. (推移律)
• $x O y$ かつ $y O x$ ならば $x = y$. (反対称律)

さらに, 上の 3 条件に加えて次の条件もが成り立つとき, $O$ を $X$ の 全順序 (total order) または単に順序, 組 $( X, O )$ を全順序集合 (totally orderd set) と呼びます.

• 任意の $x$, $y \in X$ について $x O y$ か $y O x$ の少なくとも一方が成立する.

通常, 半順序または全順序を記号 $\leq$ により表します. また, $x \leq y$ かつ $x \neq y$ であることを $x < y$ と表します.

ここまでは純粋な数学でしたが, これらの概念を Rust ではトレイトによって表現します. まず先に全順序について見ておくと, Ord トレイトは次のような定義となっています.

trait Ord: Eq + PartialOrd<Self> {
    fn cmp(&self, other: &Self) -> Ordering;
}

ここに Ordering は enum (std::cmp::Ordering) で, 以下のように定義されます.

enum Ordering {
    Less,
    Equal,
    Greater,
}

つまり同じ型のふたつのインスタンスについて, 比較関数を呼ぶとより大きいか等しいか小さいかが確定するものが Ord だ, という訳です. Ord トレイトは .max() メソッドと .min() メソッドを提供します.

一方, 半順序を表す PartialOrd トレイトですが, これは比較関数を呼び出したときに $x \leq y$ が成立するかそうでないか, が確定するようなものでした (そもそも二項関係は $( x , y ) \in R$ が成り立つこととして定義されたことを思い出しましょう). 従って, 大きいとも小さいとも判断できない「比較不能」という元の組が存在し得ます. これは Rust では Option<Ordering> として表現できますから, PartialOrd の定義は次のようなものになります.

trait PartialOrd<Rhs = Self>: PartialEq<Rhs>
where Rhs: ?Sized, 
{
    fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>;
}

さて, 数値を表す Rust のプリミティブ型はすべて PartialOrd です. 浮動小数点数 (f32 と f64) を除くと Ord でもあります. 浮動小数点数には大小比較のできない NaN が含まれますから, Ord にはできない訳です. 他に全順序ではなく半順序が必要なシチュエーションとしては, 集合の包含関係, 木構造におけるノードの相対的な位置関係, などがあります.

ここまで来ると, スターリンソートがなぜ PartialOrd に対しても適用できたのかが明らかです. 例として木構造で考えると, 異なる枝に乗っているノードは明らかに比較不能ですからそれをソートすることは本来できません. しかしスターリンソートでは異なる枝に乗っているノードは粛清されますから, このような問題は生じないのです. 同じ枝に乗っているノードならすべて残るとも言っていませんが...