From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA13999; Mon, 11 Aug 2003 20:55:09 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA18180 for <caml-list@pauillac.inria.fr>; Mon, 11 Aug 2003 20:55:08 +0200 (MET DST)
Received: from manzanita ([128.120.141.214])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h7BIt7f07860
	for <caml-list@inria.fr>; Mon, 11 Aug 2003 20:55:07 +0200 (MET DST)
Received: from ijtrotts by manzanita with local (Exim 3.36 #1 (Debian))
	id 19lvJQ-0000Hw-00
	for <caml-list@inria.fr>; Sun, 10 Aug 2003 11:53:04 -0700
Date: Sun, 10 Aug 2003 11:53:04 -0700
From: ijtrotts@ucdavis.edu
To: caml-list@inria.fr
Subject: Re: [Caml-list] Array.filter (was Multi-keyed lookup table?)
Message-ID: <20030810185304.GA902@localhost>
References: <005d01c35e51$7c927200$6628f9c1@zofo> <20030809165720.GE21525@swordfish> <20030809184851.GA946@localhost> <20030810195307.GA19113@roke.freak> <20030810023435.GA3019@localhost> <20030811054808.GA13460@davidb.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20030811054808.GA13460@davidb.org>
User-Agent: Mutt/1.5.4i
X-Loop: caml-list@inria.fr
X-Spam: no; 0.00; ijtrotts:01 caml-list:01 incr:01 iterated:01 issac:01 trotts:01 davis:99 bool:01 center:98 0700,:01 cached:01 ucdavis:02 string:03 bounds:03 dave:03 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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