CODEWITHSUNDEEP
matlabcomplexity-theorysimulationtime-complexitymontecarlo
Appalachian Math
Appalachian Math

Reputation: 179

How to evaluate the cost of a simulation algorithm

I have a Monte Carlo Markov Chain simulation to test. The system size is n. Now I want to know what the relationship between n and the cost is. In other words, I want to know the power/order of n in the cost, e.g., is it n^2.5 or n^2.8?

Since there are many factors and steps involved, I prefer not to analyze the complexity first. I would very much like to run the simulation to obtain the machine time cost. So my question is how do I get the cost relation n^x, where x is unknown, based upon the machine time?

For example, when n = 1000, it takes t_1 to run a whole sweep, which is 1000 Monte Carlo steps. When n = 666, it takes t_2 to run a whole sweep, which is 666 Monte Carlo steps this time. I could obtain t_1, t_2, t_3 for different size of n, then how do I check the order of the cost?

BTW, does it matter if use different computer to get the machine time? Sorry for my ignorance.

Upvotes: 1

Views: 203

Answers (2)

chappjc
chappjc

Reputation: 30589

This MathWorks article has some general recommendations, including timeit, tic/toc and cputime.

The timeit function is often better since it accounts for first-time run costs. However, it is slightly more complicated to run, since it takes a function handle, and optionally, the number of output arguments from the handle:

X = [1 2; 3 4; 5 6; 7 8];
f = @() svd(X);
t = timeit(f, 3)

The reason why it is so handy, and accurate compared to tic/toc is because:

timeit calls the specified function multiple times, and computes the median of the measurements.

The cputime function is interesting as it will give higher numbers compared to tic/toc and timeit on multithreaded machines. If you are interested in the computational burden, perhaps this is a more relevant metric. The cputime Function vs. tic/toc and timeit.

There used to be flops command to return the number of floating point operations, but that was removed ages ago. If you really want to count flops, the Lightspeed toolbox has functions for this purpose.

Upvotes: 1

Lazarus
Lazarus

Reputation: 358

Use tic, toc to get the times for different n. If you there is a distribution of the time for a given n, then get the average.

Then, if you know it has the exponential form, you can get

order = log(avgtime);

With the different order values for each of the n values, you'll run a best fit (possibly polyfit).

Upvotes: 2

Related Questions