From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 90C04BC0A for ; Fri, 8 Jun 2007 11:05:50 +0200 (CEST) Received: from moutng.kundenserver.de (moutng.kundenserver.de [212.227.126.177]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5895n9v030926 for ; Fri, 8 Jun 2007 11:05:50 +0200 Received: from [141.84.136.30] (helo=[152.78.96.56]) by mrelayeu.kundenserver.de (node=mrelayeu7) with ESMTP (Nemesis), id 0ML2xA-1HwaPS1MWU-0000kU; Fri, 08 Jun 2007 11:05:31 +0200 Message-ID: <46691BE3.1050607@functionality.de> Date: Fri, 08 Jun 2007 10:05:39 +0100 From: Thomas Fischbacher User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.12) Gecko/20060607 Debian/1.7.12-1.2 X-Accept-Language: en MIME-Version: 1.0 To: skaller Cc: Jacques Garrigue , sds@gnu.org, caml-list@inria.fr Subject: Re: [Caml-list] Re: compiling large file hogs RAM and takes a long time. References: <4666E11F.6000308@podval.org> <466829A3.2090508@gnu.org> <20070608.100255.84973407.garrigue@math.nagoya-u.ac.jp> <1181267500.15201.144.camel@rosella.wigram> In-Reply-To: <1181267500.15201.144.camel@rosella.wigram> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Provags-ID: V01U2FsdGVkX18zSWjtPHsxBdeqbYQHLNG+4S6DMYv0ZBZu2CF IMRLWZdg3hCyqoDjQBZBoKp9Gl573dCF2f1i5o0BaDoX63gIq2 NXJu5JAC1JqqaL10EWgnQ== X-Miltered: at discorde with ID 46691BEE.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; compiler:01 wrote:01 caml-list:01 binary:01 compiling:02 seems:03 computing:05 long:06 upper:06 quite:07 file:08 actually:10 constant:10 changes:12 enough:14 skaller wrote: > You mention in the ticket there is a hard way out .. using > binary trees; hard because it would require changes everywhere > in the compiler. Is this actually enough? Seems to reduce > > O(n * n * log n) > > to > > O( n * log n * log n) > > which is still pretty bad.. is that right? What would be so bad about O(n log n log n)? After all, in our relevant computing universe, there always is an upper bound to log n which is quite a small constant (like 25 or so). -- best regards, Thomas Fischbacher tf@functionality.de