This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[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: 2004-04-23 (17:24) From: Christoph Bauer 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
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

```