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:  Quôc_Peyrot <chojin@l...> 
Subject:  Re: [Camllist] Book about functional design patterns 
On Jun 27, 2007, at 11:18 PM, PalKristian Engstad wrote: > Quôc Peyrot wrote: >> >> On Jun 27, 2007, at 10:58 PM, PalKristian Engstad wrote: >> >>> Quôc Peyrot wrote: >>>> I don't understand that part. Each time you add a node, log2(n) >>>> node needs to be reallocated. 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