Why Such difference in Execution Time?

general
, , ,
1

Execution Time increases by 0.96 secs just because I replaced the data type of a variable from “long long int” to “int” . I was wondering why this happens ? Please Note ( long long takes lesser time than just int ; this is what i found weird)

Problem: TSORT Problem - CodeChef

Solutions 1) CodeChef: Practical coding for everyone (used long long here)

           2)   https://www.codechef.com/viewsolution/21700483    (used just int here)
2

sizeof(int) is 16 bits(minimum possible in C language) where as long int is 32 bits and long long int is 64 bit here the space required for the execution of the code will increase exponentially(ie 2^n).
Since the space required has increased,

=>more data has to be carried in between RAM and processor,

=>since finite bits of data can be transferred per cycle from ram to processor => more cycles,
(varies from processor to processor)

=>each cycle has some execution time.

Hence, the increase in execution time.

3

Execution time is not increased by data type, it is just because of endl

endl flush the cache or buffer whenever it executes, that is why it increases the execution of your solution

1 Like
4

For what its worth, this code is definitely faster:

#include<bits/stdc++.h>
using namespace std;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t, n;
  cin>>t;
  vector<int> a(1000001, 0);
  for(int i=0; i<t; ++i) {
      cin >> n;
      ++a[n];
  }
  for(int i=0; i<=1000000; ++i) {
      for(int j=0; j<a[i]; ++j) {
            cout << i << "\n";
      }
  }
  return 0;	       	     
}

The contributing factors:

  • Usage of sync_with_studio(false) and cin.tie(NULL);
  • Usage of pigeonhole sort instead of quick sort - Pigeonhole Sort - GeeksforGeeks
  • Usage of \n instead of std::endl
5

Sorry Dude
Rather the one with Long Long Is getting executed Earlier !

6

Oh thanks !

@admin5 so using “\n” doesn’t do the same?

7

I’ll need to learn the first two factors you just mentioned !(it would be great if you could drop a link for the first one as well , Please)

Even Though @oleg_b thanks for such an Informative Answer ! I appreciate !

8

Yeah! because \n just print the next line nothing else

1 Like
9

First one is a trick to reduce the execution time of input and output statements this is called Fast IO.
Yeah but the real Fast IO is other than this.

You can find it on GeeksForGeeks called Fast IO

10 
sizeof(int) is 16 bits(minimum possible in C language) where as long int is 32 bits

int and long int have same size on codechef. 32 bits.

2 Likes