[Caml-list] The invert Benchmark

[Christophe TROESTLER <debian00@tiscalinet.be>]

[-- Attachment #1: Type: Text/Plain, Size: 812 bytes --]

Dear Caml riders,

I found by chance the "The invert Benchmark"
(http://www.lib.uchicago.edu/keith/crisis/benchmarks/invert/).  As you
will notice the Caml code (even compiled) performs poorly.  I guess
part of the problem is due to using Map when Hashtbl is more suited.
So I tried to rewrite the code using Hashtbl (attached to this mail).
What I got some trouble to figure out is how to get a list of the keys
where each of the keys appears only once.  I eventually went the easy
way.  Anybody got better ideas to improve efficiency?  Could a "keys"
function be an interesting addition to Hashtbl???

Another related question that popped up is: how to _efficiently_
implement a join operation (join : string -> string list -> string is
defined by: join c [s1;...;sn] = s1 ^ c ^ ... ^ c ^ sn) ?

Cheers,
ChriS

[-- Attachment #2: Code for "The invert Benchmark" --]
[-- Type: Text/Plain, Size: 857 bytes --]

open Printf

let process_input init_size =
  let table = Hashtbl.create init_size
  and split line = match Str.split (Str.regexp_string "\t") line with
    | [a; b] -> (b, a)
    | _ -> failwith "Bad file format" in
  let rec loop() =
    let line = read_line() in 
    let b, a = split line in (Hashtbl.add table b a;  loop())
  in try
      loop()
    with
      | End_of_file -> table


let get_keys t = 
  let module S = Set.Make (struct type t = string 
				  let compare = compare 
			   end) in
    S.elements(Hashtbl.fold (fun k d l -> S.add k l) t S.empty)

let print table =
  let keys = List.sort compare (get_keys table) in
    List.iter (fun b ->
 		 printf "%s" b;
		 let l = List.sort compare (Hashtbl.find_all table b) in
 		   List.iter (fun s -> printf "\t%s" s) l;
		   print_newline()
	      ) keys

let () =
  print(process_input 2000)