From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 887C9BB94 for ; Fri, 22 Jul 2005 17:51:34 +0200 (CEST) Received: from postfix4-2.free.fr (postfix4-2.free.fr [213.228.0.176]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6MFpYIW023729 for ; Fri, 22 Jul 2005 17:51:34 +0200 Received: from mch (tal21-1-82-225-174-33.fbx.proxad.net [82.225.174.33]) by postfix4-2.free.fr (Postfix) with ESMTP id 25E1B32340A for ; Fri, 22 Jul 2005 17:51:34 +0200 (CEST) From: Michel Quercia Organization: =?iso-8859-1?q?=C9ducation?= Nationale To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] How to do this properly with OCaml? Date: Fri, 22 Jul 2005 17:54:04 +0200 User-Agent: KMail/1.7.2 References: In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit Content-Disposition: inline Message-Id: <200507221754.05054.michel.quercia@prepas.org> X-Miltered: at nez-perce with ID 42E11606.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; quercia:01 quercia:01 prepas:01 caml-list:01 ocaml:01 heap:01 heap:01 overwrite:01 arrays:01 non-empty:01 downto:01 arrays:01 downto:01 blit:01 prepas:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 Le Vendredi 22 Juillet 2005 16:26, Thomas Fischbacher a écrit : > I repeatedly stumble across problems ... > (2) Make an optional array of tuples which is None until the first entry > is made. > > One drawback of approach (2) is that when we "remove" entries from the > heap, the underlying array will keep unnecessary references to values > which by chance might be quite big, and which we might want to be > reclaimed by GC, so that's not too beautiful for a general-purpose > application. if you know which element of the heap will removed last, then you can overwrite any element to be removed with this one. Otherwise pick some element when building the heap and use it for removals. > The very same problem appears in a different guise when one tries to write > a function that flattens 'a array array -> 'a array. Is the following code that ugly ? let join_arrays aa = (* get total length and index of first non-empty array *) let l = ref 0 and i = ref 0 in for j = Array.length(aa) - 1 downto 0 do let lj = Array.length aa.(j) in if lj > 0 then begin l := !l + lj; i := j end done; (* now copy all arrays, ending with the first non empty *) if !l = 0 then [||] else begin let r = Array.make !l aa.(!i).(0) in for j = Array.length(aa) - 1 downto !i do let lj = Array.length aa.(j) in if lj > 0 then begin l := !l - lj; Array.blit aa.(j) 0 r !l lj end done; r end -- Michel Quercia 23 rue de Montchapet, 21000 Dijon http://michel.quercia.free.fr (maths) http://pauillac.inria.fr/~quercia (informatique) mailto:michel.quercia@prepas.org