Re: [Caml-list] Re: compiling large file hogs RAM and takes a long time.

[Thomas Fischbacher <tf@functionality.de>]

skaller wrote:

> Perhaps you're right .. still, there's a big difference
> between a 5 minute compile (enough time to make a coffee!)
> and a 2 hour compile (enough time to have lunch!)

The point I wanted to make here is: when it comes to the evaluation
whether extra logarithmic factors in time complexity do matter or
not, it is very important to also pay attention to the constants
involved.

For example, take a set of N magnetic needles distributed randomly
over space. In order to find the magnetic field experienced by every
single needle that is created by all the others, you can do a naive
O(N^2) algorithm that just sums contributions. There is a more
clever - and technically very sophisticated - technique that uses
multipole expansions to get a good approximation (the
"fast multipole method"), which can be computed in O(N log N),
but the constants are such that the break even point is not
reached before N=1000, and depending how well your code is
written, may lie above N=5000.

If such a situation arouse, I would, for example,
not have any objections against trading an O(N log N) algorithm
for an O(N log N log N) algorithm that is conceptually so much
simpler that the constant factor is smaller by two orders
of magnitude...

> I usually illustrate this by asking if you'd be happy
> to give up your 2 / 52 week annual holiday .. that's
> under 4% of the year.. I'm sure you'd be horrified ..
> 4% is a LOT!

I am always amazed when I hear this, thinking that we
Europeans typically get at least 5 weeks of holiday
per year. :-)

Admittedly, according to the CIA world factbook, GDP
per capita is about 1/4 higher in the US than in Germany
(say), but I still prefer the more relaxed European model.

-- 
best regards,
Thomas Fischbacher
tf@functionality.de