This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

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

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-06-27 (22:20) From: Pal-Kristian Engstad Subject: Re: [Caml-list] Book about functional design patterns
```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.

100,000 random key, value pairs resulted in 151,587 allocations, and
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.

--