CODEWITHSUNDEEP
algorithmtime-complexitytiming
user1002358
user1002358

Reputation: 2942

Estimating simulation run time based on sample runs

I need to run a simulation over a weekend. I would like the simulation to be large enough that it will be as descriptive as possible, but I don't want it doesn't finish by the time I get back to work and I can't continue working on this software.

The algorithm is such that once started, it must complete or there is no point in running it at all.

The individual elements of the simulation run in a factorial, n^4, and n^2 

   n:
<= 6  =         0ms
   7  =         8ms
   8  =        91ms
   9  =     1,089ms
   10 =    14,666ms
   11 =   197,288ms
   12 = 3,091,739ms

I have fit a curve to these samples in WolframAlpha here. The two things that concern me are firstly that the n^4 component is negative, which doesn't make any sense since it is certainly a contributing factor to the run-time. The other thing is, I have tried to estimate run times in the past in similar situations and my extrapolations are usually way off.

Do any of you have experience with guessing the run-time of an algorithm based on the input size in this way?

Upvotes: 4

Views: 896

Answers (2)

salva
salva

Reputation: 10242

In general, when you have some O(N4) your also have to introduce terms for O(N3), O(N2), O(N) and O(1). In other words, try adding x3, x1, and x0 into the curve fitting model.

For this particular case, where you have a O(N!), well, I would follow amit advice and consider only the factorial part as it seems to converge quite fast.

But in any case, if you really have a O(N!) you don't need to estimate, just use a iterative deepening approach. Let your computer iteratively run the case for n=1,2,3,4,5,6,7... and let it go as far as it can.

It may seem that you are wasting your computer time, but if you analyze it, you will see that the wasted time is insignificant. For instance, you are already at n=12, so for n=13 the required CPU C13 would be 13*C12, C12 = 12*C11 and so on. Introducing your measurements, sum(C13..C0)/C13 = 1.082, so running your function for all the values from 0 to 13 will be only 8% more expensive than just running it for 13. And as you go for bigger values of N, this percentage will mitigate even further.

update:

Why you need to add terms for all the powers below the complexity level:

Consider a simple three level loop with complexity O(N3):

void foo(int n) {
  int i, j, k;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      for (k = 0; k < n; k++)
        do_something(i, j, k);
}

foo(3);

It is obvious that the do_something(i, j, k) is called n3 times.

But it we start from the beginning considering every instruction executed, we can see than entering and leaving the function, setting the stack and other low level tasks are done once; the i=0 instruction is also performed once. These are instructions corresponding to the n0 cost.

The instructions i < n, i++ and j=0 are called n times, they correspond to the n1 term.

The instructions j < n, j++ and k=0 are called n2 times, they correspond to the n2 term.

Well, and so on.

More complex cases are the same, you always have instructions running a number of times proportional to all the powers below that of the complexity level.

Regarding you measurement of C(0) = 0, it is just a problem of your timings not being accurate enough. It could be very small but never an absolute 0.

And finally, if your curve fitting doesn't work, it is because of the N! part as in that case you will also have instructions running (n-1)! times, and (n-2!) times and so on.

Upvotes: 1

amit
amit

Reputation: 178491

Why extrapolation fails:
Extrapolations are expected to be way off when you are looking to estimate a value outside of the original range.
In polynomial extrapolation at least - the error is function of the product of the distance between the point to all sample points, and the max of the n'th derivative of the function in the range. If this distance is large - it (The product of the distances and the max derivative) is expected to be high.

The n^4 component is giving a negative value because it is showing the best function which can explain the "observations".

For estimating run time out of the sample zone - I'd recommend to avoid using extrapolations. They are not good estimations by definition when going way out of the "comfort zone" of the known samples.

Thinking of an alternative:
I'd try to find a rough estimation of the constants (by statically analyzing the code) - mainly - I would like to see if the factorial component has very small constant, and the rest has very large constant. If it is not the case, the n^2, and n^4 components could be ignored - they are neglectable comparing to the factorial component, this will be much easier to analyze.

P.S. From looking at your dynamic data provided - it seems to be the case, the difference between run times is quickly converging into the factorial factor, so analyzing the function as factorial, and estimating f(12) ~= 12* f(11) and so on seems like a reasonable assumption.
If you want to be on the safe side, you can use f(n) = (n + d) * f(n-1), where d is a predefined positive constant, for example d = max{0,f(11)/f(10) - 11}.

P.S.2:
Since the behavior of factorial is so radical, you can try to run the simulation iteratively, f(1) + f(2) + ... + f(n) is not expected to take much longer then f(n) for any n > 10. By doing so, you will get the result you had time to calculate, although you abort it when you come back to office. This behavior is called any time.

Upvotes: 1

Related Questions