On Monday 27 August 2007 09:09:17 manu wrote:
Daniel Fischer's modifications to my original program lead to a 400 % speed boost !!! (It now runs in 22 seconds on my machine) He avoided unecessary calls to 'length', uses Array instead of Map, refactored 'search' function (details below)
I've put up his version on hpaste : http://hpaste.org/2452#a1
You shouldn't have any problem writing a purely functional solver that is faster and much shorter than Norvig's Python without having to use arrays. The following purely functional OCaml solver is faster than Norvig's, for example, and uses lists, tuples and maps: open List let invalid (i, j) (i', j') = i=i' || j=j' || i/3=i'/3 && j/3=j'/3 let select p n p' ns = if invalid p p' then filter ((<>) n) ns else ns let cmp (_, l1) (_, l2) = compare (length l1) (length l2) let add p n sols = sort cmp (map (fun (p', ns) -> p', select p n p' ns) sols) module Map = Map.Make(struct type t = int * int let compare = compare end) let rec search f sol = function | [] -> f sol | (p, ns)::sols -> iter (fun n -> search f (Map.add p n sol) (add p n sols)) ns -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e