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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 8CDC4BC6B for ; Fri, 8 Jun 2007 11:55:36 +0200 (CEST) Received: from moutng.kundenserver.de (moutng.kundenserver.de [212.227.126.186]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l589taqR002032 for ; Fri, 8 Jun 2007 11:55:36 +0200 Received: from [141.84.136.30] (helo=[152.78.96.56]) by mrelayeu.kundenserver.de (node=mrelayeu7) with ESMTP (Nemesis), id 0ML2xA-1HwbBu3fSG-0000kQ; Fri, 08 Jun 2007 11:55:35 +0200 Message-ID: <466927A0.9090309@functionality.de> Date: Fri, 08 Jun 2007 10:55:44 +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> <46691BE3.1050607@functionality.de> <1181295353.20252.26.camel@rosella.wigram> In-Reply-To: <1181295353.20252.26.camel@rosella.wigram> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Provags-ID: V01U2FsdGVkX18pWXVuQqF9HCK8kTTp8Ok+ujtWCn0J0MMint9 Mf7iHxCj69x2JGtCuZwBNEDh3a7vtOlfnYAFUuoFAhnt02KRH3 vRvW8Lvn8dr6vHgOv+Chg== X-Miltered: at concorde with ID 46692798.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; logarithmic:01 expansions:01 computed:01 conceptually:01 admittedly:01 model:01 magnetic:98 magnetic:98 needle:98 constants:01 constants:01 wrote:01 compile:01 compile:01 caml-list:01 skaller wrote: > Perhaps you're right .. still, there's a big difference > between a 5 minute compile (enough time to make a coffee!) > and a 2 hour compile (enough time to have lunch!) The point I wanted to make here is: when it comes to the evaluation whether extra logarithmic factors in time complexity do matter or not, it is very important to also pay attention to the constants involved. For example, take a set of N magnetic needles distributed randomly over space. In order to find the magnetic field experienced by every single needle that is created by all the others, you can do a naive O(N^2) algorithm that just sums contributions. There is a more clever - and technically very sophisticated - technique that uses multipole expansions to get a good approximation (the "fast multipole method"), which can be computed in O(N log N), but the constants are such that the break even point is not reached before N=1000, and depending how well your code is written, may lie above N=5000. If such a situation arouse, I would, for example, not have any objections against trading an O(N log N) algorithm for an O(N log N log N) algorithm that is conceptually so much simpler that the constant factor is smaller by two orders of magnitude... > I usually illustrate this by asking if you'd be happy > to give up your 2 / 52 week annual holiday .. that's > under 4% of the year.. I'm sure you'd be horrified .. > 4% is a LOT! I am always amazed when I hear this, thinking that we Europeans typically get at least 5 weeks of holiday per year. :-) Admittedly, according to the CIA world factbook, GDP per capita is about 1/4 higher in the US than in Germany (say), but I still prefer the more relaxed European model. -- best regards, Thomas Fischbacher tf@functionality.de