Archive

Archive for December, 2011

Functional Splay heap

Citing from Purely Functional Data Structures, page 52:

Splay trees, perhaps in combination with the ExplicitMin functor, are the fastest known implementation of heaps for most applications that do not depend on persistence and that do not call the merge function.

Here is my F# port:

type SplayHeap<‘a> = E | T of SplayHeap<‘a> * ‘a * SplayHeap<‘a>

 

exception Empty

 

module SplayHeap =

    let empty = E

    let isEmpty = function

        | E -> true

        | _ -> false

    let rec partition pivot = function

        | E -> E, E

        | T(a,x,b) as t ->           

            if x <= pivot then

                match b with

                | E -> t, E

                | T(b1,y,b2) ->

                    if y <= pivot then

                        let small, big = partition pivot b2

                        T(T(a,x,b1),y,small), big

                    else

                        let small, big = partition pivot b1

                        T(a,x,small),T(big,y,b2)

            else

                match a with

                | E -> E, t

                | T(a1,y,a2) ->

                    if y <= pivot then

                        let small, big = partition pivot a2

                        T(a1,y,small),T(big,x,b)

                    else

                        let small, big = partition pivot a1

                        small,T(big,y,T(a2,x,b))

    let insert x t = let a, b = partition x t in T(a,x,b)       

    let rec merge = function

        | E, t -> t

        | T(a,x,b), t ->

            let ta, tb = partition x t           

            T(merge(ta,a), x, merge(tb,b))

    let rec findMin = function

        | E -> raise Empty

        | T(E,x,_) -> x

        | T(a,_,_) -> findMin a

    let rec deleteMin = function

        | E -> raise Empty

        | T(E,x,b) -> b

        | T(T(E,x,b),y,c) -> T(b,y,c)

        | T(T(a,x,b),y,c) -> T(deleteMin a, x, T(b,y,c))

Advertisements
Categories: Uncategorized

C++ Sudoku solver–new numbers

I continued to squeeze more performance out of my C++ Sudoku solver. Quite amazingly IMHO, a 9×9 Sudoku can now be solved in 0.000023 seconds. However, the solver is still single threaded and does not maximize the two cores on my machine so there is still room for improvement I guess.

sudoku

This version is tagged as 4.0 and can be downloaded from http://bitbucket.org as usual:

https://bitbucket.org/d95danb/sudokucpp

As a final note I must say that AMD:s code analyst has been really helpful and easy to work with. Without a good profiler I would have been lost by now.

Categories: Uncategorized

Functional queues

I picked up the book Purely Functional Data Structures today. I bought it quite a while ago but, to be honest, I have not spent much time reading it. The book is being more of the abstract and theoretic kind and in order to actually understand what I was reading I felt like I needed to get some hands on experience. In chapter 5 the author gives pseudo code for a functional queue implementation. I started of by writing it down in F#:

type Queue<‘a> = List<‘a>*List<‘a>

 

module Queue =

    // Invariant: f is empty iff r is also empty

    let private checkf (f,r) =

        match f with

        | [] -> (List.rev r, [])

        | _ -> (f,r)

    let empty = ([], [])

    let isEmpty (f,_) = List.isEmpty f

    let head = function

        | x::_, _ -> x

        | _ -> failwith "empty queue"

    let snoc (f,r) x = (f,x::r) |> checkf

    let tail q =

        let tail’ = function

            | _::fs,r -> (fs,r)

            | _ -> failwith "empty queue"

        tail’ q |> checkf

 

The idea is to represent a queue by two lists; the front and the rear. I.e. the queue [1,2,3,4,5] can be represented by ([1,2,3],[5,4]). Note that the rear is stored reversed. We ensure that the front is never empty except when the entire queue is empty. This is done by the checkf function. This design can easily be extended to support a double-ended queue, or dequeue which is left as an exercise for the reader. The author kindly hints that we should now ensure that front and rear lists should be non-empty if the queue contains two or more elements. If this is violated the non-empty list should be split in halves to provide new front and rear lists (also noticing that  one must be reversed). So here we are, my dequeue implementation in F#:

 

type Dequeue<‘a> = List<‘a>*List<‘a>

 

module Dequeue =

    // Invariant: f and r are non-empty iff q contains two or more elements

 

    // Helpers

    let private singleOrEmpty = function

        | [] -> true

        | [_] -> true

        | _ -> false

 

    let private splitInHalves l =

        let len = (List.length l) / 2

        (Seq.take len l |> Seq.toList, Seq.skip len l |> Seq.toList)

 

    let private checkf = function

        | [], r when not(singleOrEmpty r) -> let r’,f’ = splitInHalves r in List.rev f’, r’

        | q -> q

 

    let private checkr = function

        | f, [] when not(singleOrEmpty f) -> let f’,r’ = splitInHalves f in f’, List.rev r’

        | q -> q

 

    let private check q = (checkf >> checkr) q

 

    // Empty

    let empty = ([], [])

    let isEmpty (f,r) = List.isEmpty f && List.isEmpty r

 

    // Conversion

    let toList (f,r) = f @ (List.rev r)

 

    // Insert, inspect and remove the front element

    let cons (f,r) x = (x::f, r) |> check

    let head = function

        | x::_,_ -> x

        | [],[x] -> x

        | _ -> failwith "empty queue"

    let tail q =

        let tail’ = function

            | _::fs,r -> (fs,r)

            | _ -> failwith "empty queue"

        tail’ q |> check

 

    // Insert, inspect and remove rear element

    let snoc (f,r) x = (f,x::r) |> check

    let last = function

        | _,x::_ -> x

        | [x],[] -> x

        | _ -> failwith "empty queue"

    let init q =

        let init’ = function

            | f,_::rs -> (f,rs)

            | _ -> failwith "empty queue"

        init’ q |> check

 

Yup. Not much to say more than that. Good exercise.

Categories: Uncategorized