From: William James <w_a_x_man@...>
Date: 2006-08-04T11:30:11+09:00
Subject: Re: For performance, write it in OCaml

Jon Harrop wrote:
> William James wrote:
> > Here's a faster version of my program.
> >
> > Eliminated a "not" in a loop by replacing the array of booleans
> > that shows incompatibility of two rows with an array that shows
> > compatibility.
>
> Heh, should've thought of that. :-)
>
> > Borrowed you idea of creating an output line ahead of time and
> > modifying it in place.
> >
> > Timings:
> > 1.11  yours
> > 1.04  mine
>
> I get the opposite order:
>
> 0.394s yours
> 0.390s mine
>
> but your timings are probably more accurate because your computer is so
> slow. ;-)

It's 800MHz.  I ran each program 4 times and took the average.

>
> You can make it slightly faster by factoring out the CSE "compatible
> (latest)", giving:
>
> 0.382s
>
> That's actually faster than the C here. Woohoo! :-)

Good point.  That cuts my time to 1.01 seconds.
Also cleaned up the code a bit.
Here's the final version.

(* compile with:
ocamlopt -unsafe -inline 100 latin-squares.ml -o latin-squares.exe
*)

(* permutation code by Eric C. Cooper *)
let rec distribute elt = function
    (hd :: tl) as list -> (elt :: list) ::
      (List.map (fun x -> hd :: x) (distribute elt tl))
  | [] -> [ [elt] ]
let rec permute = function
    x :: rest -> List.flatten (List.map (distribute x) (permute rest))
  | [] -> [ [] ]

let list =  [ 1; 2; 3; 4; 5 ]
let size = List.length list

let perms = Array.of_list (permute list)
let n = Array.length perms

(* Boolean array used to determine if one row is
   compatible with another. *)
let compatible =  Array.make_matrix  n n  true ;;
Array.iteri (fun x ex ->
  Array.iteri (fun y ey ->
    compatible.(x).(y) <- List.for_all2 (<>) ex ey) perms ) perms

let join list = String.concat "" (List.map string_of_int list)
let output_strings = Array.map join perms

(* For speed, create a string that's the length of the lines
   that we'll print; the :'s that aren't needed as separators
   will later be overwritten.  *)
let output_line = String.make (size*(size+1)-1) ':' ^ "\n"
let board =  Array.make size 0

(* A recursive function. *)
let rec add_a_row row =
  if row = size then
    ( for i=0 to size-1 do
        String.blit
            output_strings.(board.(i)) 0 (* source *)
            output_line (i*(size+1))     (* dest *)
            size
      done;
      print_string output_line
    )
  else
    for latest = 0 to n - 1 do
      let compatible_slice = compatible.(latest) in
      (* Create a changeable thing (variable). *)
      let prev_row = ref 0 in
      (* The ! below fetches the variable's value. *)
      while !prev_row < row  &&
            compatible_slice.(board.(!prev_row)) do
        incr prev_row
      done;
      if !prev_row = row then
        ( board.(row) <- latest ; add_a_row (row + 1) )
    done
;;

add_a_row 0




>
> Using bitvectors may also improve things, depending if skipping a bunch of
> comparisons in that loop is significant. However, I think it is time we
> searched for a new task to optimise. Ray tracer anyone? ;-)
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy
> Objective CAML for Scientists
> http://www.ffconsultancy.com/products/ocaml_for_scientists