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=1.2 required=5.0 tests=AWL,RCVD_IN_WHOIS_BOGONS 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 EF0F9BC6B for ; Thu, 28 Jun 2007 00:20:17 +0200 (CEST) Received: from sdmx1.scea.com (sdmx1.scea.com [160.33.44.36]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RMKGJL029856 for ; Thu, 28 Jun 2007 00:20:17 +0200 Received: from edenfox.989studios.com (edenfox.989studios.com [160.33.45.60]) by sdmx1.scea.com (8.13.6/8.13.1) with ESMTP id l5RMJhsi005345; Wed, 27 Jun 2007 15:19:43 -0700 X-Envelope-From: X-Envelope-To: X-Envelope-To: Received: from postal1-dog.naughtydog.com (testmail.naughtydog.com [10.15.0.5]) by edenfox.989studios.com (8.13.7/8.13.7/SCEAint-1.0) with ESMTP id l5RMJgd0018293; Wed, 27 Jun 2007 15:19:42 -0700 Received: from [127.0.0.1] ([150.0.6.116]) by postal1-dog.naughtydog.com with Microsoft SMTPSVC(6.0.3790.3959); Wed, 27 Jun 2007 15:18:31 -0700 Message-ID: <4682E126.1050008@naughtydog.com> Date: Wed, 27 Jun 2007 15:13:58 -0700 From: Pal-Kristian Engstad User-Agent: Thunderbird 1.5.0.12 (Windows/20070509) MIME-Version: 1.0 To: =?ISO-8859-1?Q?Qu=F4c_Peyrot?= Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Book about functional design patterns 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> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-OriginalArrivalTime: 27 Jun 2007 22:18:31.0182 (UTC) FILETIME=[17FF9AE0:01C7B909] X-Scanned-By: MIMEDefang 2.48 on 160.33.44.36 X-Scanned-By: MIMEDefang 2.62 on 160.33.45.60 X-BorderEnvelope-To: X-BorderEnvelope-To: X-Miltered: at discorde with ID 4682E2A0.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; inserting:01 allocations:01 red-black:01 allocations:01 ocaml's:01 pke:01 8500:98 100,000:98 1.5:98 3.0:98 dog:98 wrote:01 caml-list:01 pairs:01 linear:02 Quôc Peyrot wrote: > I think we agree, I'm just saying that C*N*log2(N) is a over-estimated > upper bound for large N. > > C*(log2(1) + ... + log2(N)) = C * log2(1*2*....*N) = C * log2(N!) > hence > > time <= C*log2(N!) <= C * N * log2(N) > > as an example, for N = 100 > > sum(floor(log2(i)), i = 1..100) = 480 > log2(100!) = 524 (overestimated by 10%) > 100 * log2(100) = 664 (overestimated by 40%) > > for large N, the difference is going to be significant. Ok, I see what you mean. > But anyway, the details doesn't matter, it just looks to me that > inserting N elements in a functional map, is really significant. > If my maths are correct, for only 1000 elements, we are going to have > an extra 8500 allocations (the difference is so huge I actually can't > believe my maths...) But you are forgetting that you won't have to reallocate every log2(n) elements, for every n, there is a chance that the actual number is much less than log2(n). log2(n) really is just the worst case, where you have to change every red-black tree (say) all the way to the top. This is fairly unlikely, thus the number of allocations is in practice going to be far less. I tested OCaml's Map adding a counter for each allocation. Adding 100,000 random key, value pairs resulted in 151,587 allocations, and 1,000,000 adds resulted in 1,516,551 allocations. Adding sorted numbers gave: 299,964 and 2,999,958 allocations. So it looks like it is near linear (with a factor of 1.5 to 3.0) in practice. PKE. -- Pål-Kristian Engstad (engstad@naughtydog.com), Lead Graphics & Engine Programmer, "Uncharted"-team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North, Santa Monica, CA 90404, USA. Ph.: (310) 633-9112. "Most of us would do well to remember that there is a reason Carmack is Carmack, and we are not Carmack.", Jonathan Blow, 2/1/2006, GD Algo Mailing List