Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys

[Christoph Bauer <c_bauer@informatik.uni-kl.de>]

Brian Hurt <bhurt@spnz.org> writes:

> let uniq lst =
>    let rec loop accum = function
>        | [] -> List.rev accum
>        | x :: [] -> List.rev (x :: accum)
>        | x :: y :: t ->
>            if (x = y) then
>                loop accum (x :: t)
>            else
>                loop (x :: accum) (y :: t)
>     in
>     loop [] lst
> ;;

I found these lines in my code:

let unique list =
  let h = Hashtbl.create (2*List.length list) in
    List.filter
      (fun a -> 
           let known =  Hashtbl.mem h a in
           Hashtbl.add h a true;     
           not known) list

On average Hashtbl.mem should take 2 accesses. So this algorithm
runs in O(n). (But the worst case is very bad.)

Regards,
Christoph Bauer	   

-- 
beginfig(1)u=3cm;draw fullcircle scaled 2u;x0=x1=y1=x2=y3=0;-y0=y2=x3=1u;
filldraw z0..{left}z1{left}..z2{curl 1}..z3..z0..cycle;def t(expr p)=fullcircle
scaled .25u shifted(0,p*u);enddef;unfill t(.5);fill t(-.5);endfig;bye

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