Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Christoph Bauer <c_bauer@i...>
Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys
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