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 HAA22215; Mon, 11 Aug 2003 07:48:12 +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 HAA31052 for ; Mon, 11 Aug 2003 07:48:11 +0200 (MET DST) Received: from opus.davidb.org (66-75-152-1.san.rr.com [66.75.152.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h7B5mAf21016 for ; Mon, 11 Aug 2003 07:48:10 +0200 (MET DST) Received: from davidb by opus.davidb.org with local (Exim 3.31 #1 (Debian)) id 19m5XM-0003W2-00; Sun, 10 Aug 2003 22:48:08 -0700 Date: Sun, 10 Aug 2003 22:48:08 -0700 From: David Brown To: Caml List Cc: ijtrotts@ucdavis.edu Subject: Re: [Caml-list] Array.filter (was Multi-keyed lookup table?) Message-ID: <20030811054808.GA13460@davidb.org> References: <005d01c35e51$7c927200$6628f9c1@zofo> <20030809165720.GE21525@swordfish> <20030809184851.GA946@localhost> <20030810195307.GA19113@roke.freak> <20030810023435.GA3019@localhost> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20030810023435.GA3019@localhost> User-Agent: Mutt/1.5.4i X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 ijtrotts:01 incr:01 iterated:01 bool:01 0700,:01 cached:01 ucdavis:02 string:03 bounds:03 dave:03 wrote:03 data:03 let:04 array:04 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 ------------------- 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