QueueBenchmark

QueueBenchmark.hx

enum List<T> {
    Cons(h : T, t : List<T>);
    Nil;
}

enum StreamCell<T> {
    Cons(h : T, t : Stream<T>) : StreamCell<T>;
    Nil : StreamCell<T>;
}

typedef Stream<T> = Void -> StreamCell<T>

interface ListInterface<T, U : ListInterface<T, U>> {
    public function cons(x : T) : U;
    public function hd() : T;
    public function tl() : U;
    public function append(a : U) : U;
    public function reverse() : U;
    public function length() : Int;
    public function toArray() : Array<T>;
}

class StrictList<T> implements ListInterface<T, StrictList<T>> {
    private var body : List<T>;
    private var n    : Int;
    
    public function new(?l : List<T>, ?n = 0) {
        this.body = (l == null ? Nil : l);
        this.n = n;
    }
    
    public inline function cons(x : T) : StrictList<T> {
        return new StrictList(Cons(x, this.body), this.n + 1);
    }
    
    public inline function hd() : T {
        return switch(this.body) {
            case Cons(h, _): h;
            case Nil: throw "error!";
        };
    }
    
    public inline function tl() : StrictList<T> {
        return switch(this.body) {
            case Cons(_, t): new StrictList(t);
            case Nil: new StrictList();
        };
    }
    
    public function append(a : StrictList<T>) : StrictList<T> {
        function loop(x : List<T>, y : List<T>) : List<T> {
            return switch(x) {
                case Cons(h, t): Cons(h, loop(t, y));
                case Nil: y;
            }
        }
        
        return new StrictList<T>(loop(this.body, a.toList()), this.n + a.length());
    }
    
    public inline function reverse() : StrictList<T> {
        function loop(l : List<T>, a : List<T>) : List<T> {
            return switch(l) {
                case Cons(h, t): loop(t, Cons(h, a));
                case Nil: a;
            }
        }
        
        return new StrictList(loop(this.body, Nil), this.n);
    }
    
    public inline function length() : Int {
        return this.n;
    }
    
    public inline function toList() : List<T> {
        return this.body;
    }
    
    public inline function toArray() : Array<T> {
        function loop(l : List<T>, a : Array<T>) : Array<T> {
            return switch(l) {
                case Cons(h, t): a.push(h); loop(t, a);
                case Nil: a;
            };
        }
        
        return loop(this.body, []);
    }
}

class LazyList<T> implements ListInterface<T, LazyList<T>> {
    private var body : Stream<T>;
    private static var nil = function () : StreamCell<T> {
        return Nil; 
    };
    public var n : Int;
    
    public function new(?s : Stream<T>, ?n = 0) {
        s == null ? this.body = nil : this.body = s;
        this.n = n;
    }
    
    public inline function cons(x : T) : LazyList<T> {
        var s = this.toStream();
        return new LazyList(function() : StreamCell<T> {
            return Cons(x, s);
        }, this.n + 1);
    }
    
    public inline function hd() : T  {
        return switch(this.body()) {
            case Nil: throw "hd error!";
            case Cons(h, _): h;
        }
    }
    
    public inline function tl() : LazyList<T> {
        return switch(this.body()) {
            case Nil: new LazyList();
            case Cons(_, t): new LazyList(t);
        }
    }

    public inline function append(a : LazyList<T>) : LazyList<T> {
        function loop (x : Stream<T>, y : Stream<T>) : Stream<T> {
            return switch (x()) {
                case Nil: y;
                case Cons(h, t): function () : StreamCell<T> {
                    return Cons(h, loop(t, y));
                };
            };
        }
        
        return new LazyList(loop(this.body, a.body), this.n + a.n );
    }
    
    public inline function reverse() : LazyList<T> {
        function loop(s : Stream<T>, a : Stream<T>) : Stream<T> {
            return switch(s()) {
                case Nil : a;
                case Cons(h, t): 
                    loop(t, function () { return Cons(h, a); } );
            }
        }
        
        return new LazyList(loop(this.body, nil), this.n);
    }
    
    public inline function take(n : Int) : LazyList<T> {
        return new LazyList<T>(function () : StreamCell<T> {
            return switch (n) {
                  case 0: Nil;
                   case i: (this.tl().take(i - 1).cons(this.hd()).toStream())();
            }
        }, n);
    }
    
    public inline function toStream() : Stream<T> {
        return this.body;
    }
    
    public inline function toArray() : Array<T> {
        function loop(s : Stream<T>) {
            return switch(s()) {
                case Nil: [];
                case Cons(h, t): [h].concat(loop(t));
            };
        }
        
        return loop(this.body);
    }
    
    public inline function length() : Int {
        return this.n;
    }
}

typedef Tuple<T, U> = {
    var fst : T;
    var snd : U;
}

interface QueueInterface<T, U : QueueInterface<T, U>> {
    public function insert(e : T) : U;
    public function remove() : Tuple<T, U>;
    public function toArray() : Array<T>;
}

class StrictQueue<T> implements QueueInterface<T, StrictQueue<T>>{
    private var l : StrictList<T>;
    private var r : StrictList<T>;
    
    public function new (?l : StrictList<T>, ?r : StrictList<T>) {
        this.l = (l == null ? new StrictList<T>() : l);
        this.r = (r == null ? new StrictList<T>() : r);   
    }
    
    public inline function insert(e : T) : StrictQueue<T> {
        return new StrictQueue<T>(this.l.cons(e), this.r);
    }
    
    public inline function remove() : Tuple<T, StrictQueue<T>>{        
        return switch(this.r.toList()) {
            case Nil: (new StrictQueue<T>(new StrictList(), this.l.reverse())).remove();
            case Cons(h, t): {fst : h, snd : new StrictQueue<T>(this.l, new StrictList(t))};
        }
    }
    
    public inline function toArray() : Array<T> {
        return this.l.append(this.r.reverse()).toArray();
    }
}
    
class LazyQueue<T> implements QueueInterface<T, LazyQueue<T>> {
    private var l : LazyList<T>;
    private var r : LazyList<T>;
    
    public function new(?l : LazyList<T>, ?r : LazyList<T>) {
        this.l = (l == null ? new LazyList<T>() : l);
        this.r = (r == null ? new LazyList<T>() : r);
    }

    // rotate(L, R) = L.append(R.reverse()) if |R| = |L| + 1
    private static inline function rotate<U>(l : LazyList<U>, r : LazyList<U>, ?a : LazyList<U>) : LazyList<U> {
        if (a == null)
            a = new LazyList<U>(); 
        
        return new LazyList<U>(function () : StreamCell<U> {
            return switch((l.toStream())()) {
                case Nil: (a.cons(r.hd()).toStream())();
                case Cons(h, t): (rotate(l.tl(), r.tl(), a.cons(r.hd())).cons(h).toStream())();
            };
        }, l.length() + r.length());
    }
    
    private static inline function makeq<T>(l : LazyList<T>, r : LazyList<T>) {
        if (r.length() == l.length() + 1) {
            return new LazyQueue(rotate(l, r));
        } else {
            return new LazyQueue(l, r);
        }
    }
    
    public inline function insert(e : T): LazyQueue<T> {
        return makeq(this.l, this.r.cons(e));
    }
    
    public inline function remove() : Tuple<T, LazyQueue<T>> {
        return {fst : this.l.hd(),
                snd : makeq(this.l.tl(), this.r)};
    }
    
    public inline function toArray() : Array<T> {
        return this.l.append(this.r.reverse()).toArray();
    }
    
    public inline function length() : Int {
        return this.l.length() + this.r.length();
    }
}

class Test {
    static function benchmark<T : QueueInterface<Int, T>>(str : String, q : QueueInterface<Int, T>, n : Int) {
        var a = 0.0;
        
        for (i in 0 ... 10) {
            var timer = Date.now().getTime();
            var qq = q.insert(i);
            
            for (i in 0 ... n) {
                qq = q.insert(i);
                qq.remove().snd;
            }
            
            a += Date.now().getTime() - timer;
        }
        
        trace("---- " + str + " " + Std.string(n) + " ----");
        trace(a / 10);
        trace("---- end ----");
    }
    
    static function main() {
        benchmark("Queue", new StrictQueue<Int>(), 1000);
        benchmark("Queue", new StrictQueue<Int>(), 10000);
        benchmark("Queue", new StrictQueue<Int>(), 100000);
        
        benchmark("LazyQueue", new LazyQueue<Int>(), 1000);
        benchmark("LazyQueue", new LazyQueue<Int>(), 10000);
        benchmark("LazyQueue", new LazyQueue<Int>(), 100000);
   }
}