0

We are studying the performance of various sorting algorithms and implemented our version of mergesort. We are trying to measure the running time with different input, but when we run the main() program shown below, we are getting different time results.

For example, clock() function output below can show 30 seconds with large input, but when we use the actual timer using our phones, the main program takes about 2 minutes.

What are we missing here? Are we not using the clock() function in a right way? Why is there such a big difference (1.5 minutes)?

Thank you

int n;
cout << "Enter n - lenght of array" << endl;
cin >> n;

vector<int> v(n);

for(int i = 0; i < n; ++i)
{
    v[i] = i;
}

auto rng = default_random_engine {};
std::shuffle(std::begin(v), std::end(v), rng);

clock_t begin = clock();

sort(v);

cout << "done";

clock_t end = clock();

cout <<"total time : " << (double)(end-begin) / CLOCKS_PER_SEC<<endl;

return 0;
Marek R
  • 32,568
  • 6
  • 55
  • 140
user629034
  • 659
  • 2
  • 11
  • 30
  • 3
    I can't really see it causing 90 seconds' difference, but how long would `shuffle` take? – Adrian Mole Feb 17 '20 at 15:23
  • Are you measuring the execution of entire program with your phones, or just sorting? Since you are measuring only the sorting, with the `clock`. – Algirdas Preidžius Feb 17 '20 at 15:25
  • You're using clock() only for the `sort()`. Why do you expect it to be same as *what you measure with your phone*. Hey, atleast please time the program using `time` instead of relying on your super-fast reaction speed. – theWiseBro Feb 17 '20 at 15:26
  • 1
    In addition to what was already mentionen - I think - with `clock()` you meassure CPU-time, not wall-clock time. Which means your program could run for 2 minutes but it actually only uses the cpu for 1 minute or so. Also make sure, that you are running an optimized build. – Lukas-T Feb 17 '20 at 15:27
  • You should add a timer around the preparation steps too. Or a cout<<"start"< – SKCoder Feb 17 '20 at 15:27
  • 1
    related: https://stackoverflow.com/questions/2808398/easily-measure-elapsed-time – 463035818_is_not_an_ai Feb 17 '20 at 15:29
  • Unrelated to your 1.5 minute discrepancy, but move your `clock_t end = clock();` to right after `sort(v);` instead of after `cout << "done\n";`. You're needlessly measuring the time to write to the `ostream`. – JohnFilleau Feb 17 '20 at 15:30
  • for questions concerning runtime you should include a [mcve], the compiler version, compiler flags and the used benchmark (part of it is in the code, but what do you mean with "when we use the actual timer using our phones" ?) – 463035818_is_not_an_ai Feb 17 '20 at 15:31
  • in an optimized build I would expect that `sort(v)` takes 0 time, because you do not use its result. Is this all the code, or is there more? – 463035818_is_not_an_ai Feb 17 '20 at 15:32
  • Further to my earlier comment, adding a timer to just before the `vector v(n);` line and using a size of 100,000,000, I get a **sort** time of around 10s and a **total** time of around 16s. So, maybe there is something there on your platform. – Adrian Mole Feb 17 '20 at 15:35
  • 1
    How big is `n` in your tests? You aren't passing that vector by value to your sort function, are you? – Bob__ Feb 17 '20 at 15:53

1 Answers1

0

I ran your code by replacing the sort function with the std::sort, for n=5000000 it showed 11.744s then I moved the line clock_t begin = clock(); before the declaration of vector v and the time was 13.818s

So it seems memory allocation, O(N) initialization and shuffling can take a good amount of time and if you choose a much bigger number for n, depending on the efficiency of your sort function for a random inputset, initialization can take more time than the sort.

sowrov
  • 1,018
  • 10
  • 16