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 (21:34) From: Quôc_Peyrot Subject: Re: [Caml-list] Book about functional design patterns
```
On Jun 27, 2007, at 11:18 PM, Pal-Kristian Engstad wrote:

> Quôc Peyrot wrote:
>>
>> On Jun 27, 2007, at 10:58 PM, Pal-Kristian Engstad wrote:
>>
>>> Quôc Peyrot wrote:
>>>> I don't understand that part. Each time you add a node, log2(n)
>>>> node needs to be re-allocated. Hence the total number of
>>>> reallocations is:
>>>> Sum(ceil(log2(i)), i = 1..N) with N = 1000000, which is
>>>> significant.
>>
>> Oops, my mistake I meant "floor" not ceil.
>>
>>> So you are saying that inserting N elements into a tree takes O
>>> (n*log2(n)).
>>
>> Not exactly, log2(N!) is a closer estimate (estimate because of
>> the "floor" introducing a bias in the sum)
> No, no. Let's assume it always touches log2(n) elements, where n
> goes from 1 .. N. Then we have:
>
>    time = C * log2(1) + C * log2(2) + C * log2(3) + .... + C * log
> N = C * (log2(1) + ... + log2(N) <= C * N * log2(N),
>
> since
>
>    log(n) <= log(N).

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.

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...)

--
Best Regards,
Quôc

```