Re: [Caml-list] Array.filter (was Multi-keyed lookup table?)

[ijtrotts@ucdavis.edu]

On Sun, Aug 10, 2003 at 10:48:08PM -0700, David Brown wrote:
> On Sat, Aug 09, 2003 at 07:34:35PM -0700, ijtrotts@ucdavis.edu wrote:
> 
> > # let filter f a = 
> >    let n = ref 0 in 
> >    for i = 0 to Array.length a - 1 do if f a.(i) then incr n done;
> >    let k = ref 0 in 
> >    Array.init !n 
> >     (fun i -> while not (f a.(!k)) do incr k done; incr k; a.(!k-1));;
> 
> Unfortunately, this calls f twice on each element.  If that solution is
> not acceptable, then the results of f a.(i) could be cached in some type
> of bit array (perhaps in a string), and then that string iterated again.
> 
> This function also poorly if f a.(i) isn't really functional, and
> returns different results.  For example:
> 
>    List.filter (fun _ -> Random.bool) data
> 
> will return roughly half of the items, randomly.  This would cause array
> bounds problems about half the time with the above code.
> 
> Dave Brown
> 

Good idea.  This would be more robust:

let filter f arr = 
   let n = ref 0 in
   let tmp = Array.map (fun x -> if f x then (incr n; 1) else 0) arr in
   let k = ref 0 in
   Array.init !n
    (fun i -> while tmp.(!k) <> 1 do incr k done; incr k; arr.(!k-1));;

or...

let filter2 f arr = 
   let n = ref 0 in
   let tmp = String.create (Array.length arr) in
   for i = 0 to Array.length arr - 1 do 
    tmp.[i] <- if f arr.(i) then (incr n; '1') else '0'
   done;
   let k = ref 0 in
   Array.init !n
    (fun i -> while tmp.[!k] <> '1' do incr k done; incr k; arr.(!k-1));;

-- 
Issac Trotts
Programmer
Center for Neuroscience
University of California, Davis 

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