Re: [Caml-list] The invert Benchmark

[Markus Mottl <markus@oefai.at>]

On Wed, 17 Apr 2002, Christophe TROESTLER wrote:
> 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.

Looking at the code this does not surprise me...

> Anybody got better ideas to improve efficiency?  Could a "keys"
> function be an interesting addition to Hashtbl???

This should be about 10x faster than the initial version:

---------------------------------------------------------------------------
let report_url url = print_string ("\t" ^ url)

let report (file, url_lst) =
  let url_ar = Array.of_list url_lst in
  Array.sort compare url_ar;
  print_string file; Array.iter report_url url_ar; print_char '\n'

let _ =
  let table = Hashtbl.create 10000 in
  let cnt_ref = ref 0 in
  try
    while true do
      let line = input_line stdin in
      let ix = String.index line '\t' in
      let url = String.sub line 0 ix in
      let file = String.sub line (ix + 1) (String.length line - ix - 1) in
      try
        let urls_ref = Hashtbl.find table file in
        urls_ref := url :: !urls_ref
      with Not_found -> incr cnt_ref; Hashtbl.add table file (ref [url])
    done
  with
  | End_of_file ->
    let ar = Array.make !cnt_ref ("", []) in
    let coll file urls_ref cnt = ar.(cnt) <- file, !urls_ref; cnt - 1 in
    ignore (Hashtbl.fold coll table (!cnt_ref - 1));
    Array.sort compare ar; Array.iter report ar
  | Not_found -> failwith "bad data"
---------------------------------------------------------------------------

> 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) ?

Look up the function "String.concat" in the standard library...

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners