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 TAA12115; Mon, 24 Sep 2001 19:48:26 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA12109 for <caml-list@pauillac.inria.fr>; Mon, 24 Sep 2001 19:48:25 +0200 (MET DST)
Received: from math.unifi.it (hermes.math.unifi.it [150.217.33.222])
	by nez-perce.inria.fr (8.11.1/8.10.0) with SMTP id f8OHmOX28067
	for <caml-list@inria.fr>; Mon, 24 Sep 2001 19:48:24 +0200 (MET DST)
Received: (qmail 10568 invoked from network); 24 Sep 2001 17:48:24 -0000
Received: from sisiphos.math.unifi.it (mail@150.217.33.46)
  by hermes.math.unifi.it with SMTP; 24 Sep 2001 17:48:24 -0000
Received: from maggesi by sisiphos.math.unifi.it with local (Exim 3.12 #1 (Debian))
	id 15lZqB-0006nu-00
	for <caml-list@inria.fr>; Mon, 24 Sep 2001 19:48:23 +0200
To: caml-list@inria.fr
Subject: Re: [Caml-list] mark_slice, sweep_slice, oldify
References: <200109191640.SAA0000032430@beaune.inria.fr>
From: Marco Maggesi <maggesi@math.unifi.it>
Date: 24 Sep 2001 19:48:23 +0200
Message-ID: <87zo7kscns.fsf@sisiphos.math.unifi.it>
User-Agent: Gnus/5.090001 (Oort Gnus v0.01) Emacs/20.7
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk


Damien and Xavier, thank you for your clear and concrete answers.  I
already had some benefit by playing with [Gc.set].  However, I think I
will need more time to do some tests and understand better what's
going on, but I do not have enough time at the moment.  I will send a
notice if I will obtain something interesting.

I realized that my problem can be described with a good approximation
as follows: how to merge a certain number of ordered lists in a single
orederd list.  Even better, I need to merge a matrix a_{i,j} of
elements which are ordered by rows and by columns
  a_{i+1,j} >= a_{i,j}   and   a_{1,j+1} >= a_{i,j}
for all i, j.

My approach is to use leftist trees to reduce the cost of merging
lists in pairs.  Probably, this is responsable for the allocation of
many intermediate structures to compute the result.  Probably I can do
better than that.  I think I have to look more depthly in the theory.
(Perhaps The Art of Computer Programs?)

Ciao, Marco
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr