CODEWITHSUNDEEP
c++
Charbel Sarkis
Charbel Sarkis

Reputation: 81

how to make this program run faster?

I'm always getting around 12 ms I want to get around 5ms.
How can I achieve this?
Does using an iterator make a program run faster? 

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // for (int i = 1; i < nums.size(); i++) {
        //     nums[0] ^= nums[i];
        // }
        // return nums[0];

        for (auto i = nums.begin() + 1; i < nums.end(); ++i) {
            nums[0] ^= *i;
        }
        return nums[0];
    }
};

Upvotes: 2

Views: 313

Answers (2)

3CxEZiVlQ
3CxEZiVlQ

Reputation: 38912

Discarding access nums[0] in the loop, makes tests 5x faster.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int r = nums[0];
        for (auto i = nums.begin() + 1; i < nums.end(); ++i) {
            r ^= *i;
        }
        nums[0] = r;
        return r;
    }
};

http://quick-bench.com/w0-RRDzLq9RF-tbLjdSS2omgyGM

The performance is better because of int r stored in one of the CPU registers. If you try int& r = nums[0];, the performance is the same as OP's origin one.

I have looked at Blastfurnace's answer. It seems the compiler optimizes code better if the whole vector is iterated. So the solution bellow is even 7x faster than OP's original one.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int r = 0;
        for (auto i = nums.begin(); i < nums.end(); ++i) {
            r ^= *i;
        }
        nums[0] = r;
        return r;
    }
};

And the final 7x faster and shorter solution if range-for-loop used

class Solution {
public:
    int singleNumber1(std::vector<int>& nums) {
        int r = 0;
        for (const int i : nums) {
            r ^= i;
        }
        nums[0] = r;
        return r;
    }
};

Upvotes: 6

Blastfurnace
Blastfurnace

Reputation: 18652

I modified the code in S.M.'s answer by replacing the for loop with a call to std::accumulate. Quickbench showed an additional 1.4x speedup over the hand-rolled loop.

class Solution {
public:
    int singleNumber(std::vector<int>& nums) {
        int r = std::accumulate(nums.begin(), nums.end(), 0, std::bit_xor<int>());
        nums[0] = r; // is this necessary?
        return r;
    }
};

http://quick-bench.com/8dnWzm3o4l2m7p3zXM-8FmxH97I

Upvotes: 2

Related Questions