Estimation of simulation run time based on sample runs

Question

I need to run a simulation over the weekend. I would like the simulation to be large enough to be as descriptive as possible, but I do not want it to end by the time I return to work, and I cannot continue to work on this software.

The algorithm is such that after starting it should be completed or it makes no sense to run it at all.

Individual elements of the simulation are performed in the 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 plot the curve for these patterns in WolframAlpha here . Two things that concern me are, firstly, that the n ^ 4 component is negative, which makes no sense, since this is certainly a factor affecting runtime. Another thing, I tried to estimate the runtime in the past in similar situations, and my extrapolations are usually deleted.

Do any of you have experience guessing the execution time of an algorithm based on the size of the input this way?

Answer 1

In the general case, when you have O (N ⁴ ), you also need to enter the terms for O (N ³ ), O (N ² ), O (N) and O (1). In other words, try adding x ³ x ¹ and x ⁰ to the curve fitting model.

In this particular case, when you have O (N!), I would follow the advice and consider only the factorial part, since it seems to converge quite quickly.

But in any case, if you really have O (N!), You do not need to evaluate, just use the 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 possible.

It may seem that you are wasting time on your computer time, but if you analyze it, you will see that the wasted time is negligible. For example, you are already at n = 12, so for n = 13 the required CPU C ₁₃ will be 13 * C ₁₂ , C ₁₂ = 12 * C ₁₁ and so on. Introducing your measurements, summarize (C ₁₃ .. C ₀ ) / C ₁₃ = 1.082, so running your function for all values ​​from 0 to 13 will cost 8% more than just running it at 13. And as you go to large N values, this percentage will be further softened.

Update

Why you need to add terms for all capacities below the difficulty level:

Consider a simple three-level cycle with complexity O (N ₃ ):

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

Obviously, do_something(i, j, k) is called n ³ times.

But we start from the very beginning, considering each executed command, we can see how to enter and leave the function, setting the stack and other low-level tasks that are performed once; the i=0 instruction is also executed once. These are instructions corresponding to a cost of n ⁰ .

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

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

Well, etc.

More complex cases are the same, you always have commands that are executed several times in proportion to all capacities below the level of complexity.

As for your measurement, C(0) = 0 , it's just a problem of your timings, which are not accurate enough. It can be very small, but not absolute 0.

And finally, if your curve fitting doesn't work, it's because of N! since in this case you will also follow instructions (n-1)! times and (n-2!) times, etc.

Answer 2

Why extrapolation is not performed:
Extrapolations are expected to be canceled if you want to estimate the value outside the original range.
By polynomial extrapolation, at least - the error is a function of the product of the distance between the point to all points in the sample and the maximum nth derivative of the function in the range. If this distance is large, it (the product of distances and the maximum derivative) is expected to be high.

Component n ^ 4 gives a negative value, because it shows a better function that can explain "observations".

To estimate the lead time from the sampling area - I would recommend avoiding the use of extrapolation. By definition, they are not good grades when leaving the “comfort zone” of known designs.

Thinking of an alternative: I would try to find an approximate estimate of the constants (statically analyzing the code) - basically - I would like to see if the factorial has a very small constant, and the rest has a very large constant. If this is not so, the components n ^ 2 and n ^ 4 can be ignored - they are negligible compared to the factorial component, it will be much easier to analyze.

PS From a look at the dynamic data you provided - it seems that the difference between the execution time quickly converges to a factorial factor, so analyzing the function as a factorial and evaluating f(12) ~= 12* f(11) , etc., seems like a reasonable assumption .
If you want to be safe, 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} .

PS2:
Since factorial behavior is so radical, you can try to run the simulation iteratively, f(1) + f(2) + ... + f(n) is expected to take much longer than f(n) for any n > 10 . By doing so, you will get a result that you have time to calculate, although you will stop it when you return to the office. This behavior is called at any time .