0

Below are two sets of code performing the same functionality. Here the method is almost same. Could anyone explain me why the runtime of code1 is lesser than code2.

#code 1

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int count=0, res=0;
        int n= nums.size();
        for(int i=0;i<n;i++){
            if(nums[i]==0){
                count=0;
            }
            else{
                count++;
                res = max(count,res);
            }
        }
        
        return res;
    }
};

#code 2

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int count=0, res=0;
        int n= nums.size();
        for(int i=0;i<n;i++){
            if(nums[i]==0){
                count++;
                res = max(res,count);

            }
            else{
                count=0;            
            }
        }
        
        return res;
    }
};

Code1 takes 24ms to run while code2 takes 36ms to run.

François Andrieux
  • 28,148
  • 6
  • 56
  • 87
Rahul Ranjan
  • 1
  • 3
    How did you measure the performance? – Kevin Jul 02 '21 at 16:44
  • 3
    The logic is different, so it may depend on input values. Maybe it has to perform `max` way more often with code 2 than code 1. Or maybe this is an error in how you measured performance. Your sample size might be too small, you may be testing these consecutively or you may otherwise introduce other measurement biases. Please show how you compiled your tests and how you measured performance. – François Andrieux Jul 02 '21 at 16:48
  • How did you compile your code? With which compiler and flags? – unddoch Jul 02 '21 at 17:08
  • 24 or 36 ms is in the order of the time the OS takes to spawn a process. If you run the function only once, the measurement is completely wrong. Try to call the function a few thousand times, until the process lasts at least some seconds. – prapin Jul 02 '21 at 17:34
  • That could be because of the branch predictor. Check that excellent answer about it. https://stackoverflow.com/a/11227902/5688187 – MartinVeronneau Jul 02 '21 at 20:47
  • Also, try to comment the line calling `max` and see if the performance is similar. – MartinVeronneau Jul 02 '21 at 20:50

1 Answers1

1

If we are talking about the run-time, take into consideration the time complexity of the program which is O(n), where n is the number of inputs. Also, you are traversing the vector, so it really would be depending on the input arrangements.

For example, if your vector contains [0,0,0,0,0,0,1,1,1,1], then in case of code1, max will be called 4 times, but in code2, max will be 6 times, which will increase the execution time for code2.

But if your vector contains [1,1,1,1,1,1,0,0,0,0], then code1 will require more time to execute than code2.

Harsh patel
  • 445
  • 5
  • 11