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 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id AA3B2BC6C for ; Wed, 27 Jun 2007 23:34:56 +0200 (CEST) Received: from smtp19.orange.fr (smtp19.orange.fr [80.12.242.1]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RLYuoS020485 for ; Wed, 27 Jun 2007 23:34:56 +0200 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf1927.orange.fr (SMTP Server) with ESMTP id 32C2D1C0026E for ; Wed, 27 Jun 2007 23:34:56 +0200 (CEST) Received: from [192.168.1.162] (ALagny-153-1-98-23.w90-3.abo.wanadoo.fr [90.3.145.23]) by mwinf1927.orange.fr (SMTP Server) with ESMTP id F0F441C00208; Wed, 27 Jun 2007 23:34:55 +0200 (CEST) X-ME-UUID: 20070627213455987.F0F441C00208@mwinf1927.orange.fr In-Reply-To: <4682D440.2060901@naughtydog.com> References: <200706271314.35134.jon@ffconsultancy.com> <1A1D6F56-B3DB-4552-969C-9859482175AC@lrde.epita.fr> <46826C69.5060802@functionality.de> <20070627191633.73ab011a@kerneis.info> <342AAB2F-A76C-42C8-A5F1-4139BE2FE4A9@lrde.epita.fr> <4682BF04.8090606@janestcapital.com> <4682CA02.4040006@janestcapital.com> <25B2FF5F-7C58-4F70-B1AE-0FD7577FB521@lrde.epita.fr> <4682CF58.7010709@naughtydog.com> <4682D440.2060901@naughtydog.com> Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Message-Id: Cc: caml-list@yquem.inria.fr Content-Transfer-Encoding: quoted-printable From: =?ISO-8859-1?Q?Qu=F4c_Peyrot?= Subject: Re: [Caml-list] Book about functional design patterns Date: Wed, 27 Jun 2007 23:34:54 +0200 To: Pal-Kristian Engstad X-Mailer: Apple Mail (2.752.2) X-Miltered: at discorde with ID 4682D800.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; lrde:01 node:01 node:01 inserting:01 inserting:01 allocations:01 2007,:98 2007,:98 8500:98 wrote:01 wrote:01 caml-list:01 oops:01 tree:02 functional:02 On Jun 27, 2007, at 11:18 PM, Pal-Kristian Engstad wrote: > Qu=F4c Peyrot wrote: >> >> On Jun 27, 2007, at 10:58 PM, Pal-Kristian Engstad wrote: >> >>> Qu=F4c Peyrot wrote: >>>> I don't understand that part. Each time you add a node, log2(n) =20 >>>> node needs to be re-allocated. Hence the total number of =20 >>>> reallocations is: >>>> Sum(ceil(log2(i)), i =3D 1..N) with N =3D 1000000, which is =20 >>>> significant. >> >> Oops, my mistake I meant "floor" not ceil. >> >>> So you are saying that inserting N elements into a tree takes O=20 >>> (n*log2(n)). >> >> Not exactly, log2(N!) is a closer estimate (estimate because of =20 >> the "floor" introducing a bias in the sum) > No, no. Let's assume it always touches log2(n) elements, where n =20 > goes from 1 .. N. Then we have: > > time =3D C * log2(1) + C * log2(2) + C * log2(3) + .... + C * log =20= > N =3D C * (log2(1) + ... + log2(N) <=3D C * N * log2(N), > > since > > log(n) <=3D log(N). I think we agree, I'm just saying that C*N*log2(N) is a over-=20 estimated upper bound for large N. C*(log2(1) + ... + log2(N)) =3D C * log2(1*2*....*N) =3D C * log2(N!) hence time <=3D C*log2(N!) <=3D C * N * log2(N) as an example, for N =3D 100 sum(floor(log2(i)), i =3D 1..100) =3D 480 log2(100!) =3D 524 (overestimated by 10%) 100 * log2(100) =3D 664 (overestimated by 40%) for large N, the difference is going to be significant. But anyway, the details doesn't matter, it just looks to me that =20 inserting N elements in a functional map, is really significant. If my maths are correct, for only 1000 elements, we are going to have =20= an extra 8500 allocations (the difference is so huge I actually can't =20= believe my maths...) --=20 Best Regards, Qu=F4c