Re: [Caml-list] Book about functional design patterns

[Pal-Kristian Engstad <pal_engstad@naughtydog.com>]

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