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