Rust で SkewHeap を書いてみた

タイトルのまんま．
純粋関数型データ構造っぽさを意識して書いてみました．

use std::rc::Rc;
enum SkewHeap<T: Ord + Clone> {
    Empty,
    Node(T, Rc<SkewHeap<T>>, Rc<SkewHeap<T>>)
}

impl<T: Ord + Clone> Clone for SkewHeap<T> {
    fn clone(&self) -> SkewHeap<T> {
        match *self {
            SkewHeap::Empty => SkewHeap::Empty,
            SkewHeap::Node(ref v, ref l, ref r) => SkewHeap::Node((*v).clone(), (*l).clone(), (*r).clone()),
        }
    }
}

impl<T: Ord + Clone> SkewHeap<T> {
    fn push(&self, val: T) -> SkewHeap<T> {
        self.meld(SkewHeap::Node(val, Rc::new(SkewHeap::Empty), Rc::new(SkewHeap::Empty)))
    }

    fn meld(&self, other: SkewHeap<T>) -> SkewHeap<T> {
        match *self {
            SkewHeap::Empty => other.clone(),
            SkewHeap::Node(ref v1, ref l1, ref r1) => {
                match other {
                    SkewHeap::Empty => self.clone(),
                    SkewHeap::Node(ref v2, ref l2, ref r2) => {
                        if v1 < v2 {
                            let r = r1.clone();
                            //SkewHeap::Node(v1.clone(), l1.clone(), Rc::new(r.meld(other.clone())))
                            SkewHeap::Node(v1.clone(), Rc::new(r.meld(other.clone())), l1.clone())
                        } else {
                            let r = r2.clone();
                            //SkewHeap::Node(v2.clone(), l2.clone(), Rc::new(r.meld(self.clone())))
                            SkewHeap::Node(v2.clone(), Rc::new(r.meld(self.clone())), l2.clone())
                        }
                    }
                }
            }
        }
    }

    fn pop(&self) -> (Option<T>, SkewHeap<T>) {
        match *self {
            SkewHeap::Empty => (None, SkewHeap::Empty),
            SkewHeap::Node(ref v, ref l, ref r) => {
                (Some(v.clone()), l.meld((**r).clone()))
            }
        }
    }
}

使ってみた

試しに以下の問題を解いてみた．
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C

結果は 3.99 sec で TLE．まあ clone しまくってるのでそれはそう．予想より早い（もっと遅いと思っていた）

追記
木の形偏ってるなあと思っていたら，meld するときに swap するの忘れてた．すると 3.99 sec から 3.07 sec に改善した．

感想

もし競プロならこのままだと使えない．純粋関数型っぽさを捨てれば早いのは書ける．Rust はライフタイムの制約が厳しすぎて，変更が加わらなかったノードは共有するみたいなコードを書くのが難しい．どうかけばいいかわからん．