The Implicit Accumulator: a design pattern using optional arguments
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  PalKristian Engstad <pal_engstad@n...> 
Subject:  Re: [Camllist] Book about functional design patterns 
Quôc Peyrot wrote: > I think we agree, I'm just saying that C*N*log2(N) is a overestimated > 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 redblack 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ålKristian 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) 6339112. "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