Why c++ solution of this problem is the slowest?


  • 0

    As a common sense, c++ is the fastest language (except assembly language).
    But why in this problem it happens to be the slowest?


  • 0
    Q

    I also want to know why? @西兑, did you figure out why?


  • 0
    Q

    I think I figured out the answer! It should be due to the "push_back()" function of the vector<int> type that is causing the slowness of C++ solution.

    The "push_back()" method will check if the pre-allocated array has enough space. If not, it will increase the vector length by 2x and then copy all the old vector element to the new allocated vector, push_back the newly added element, and then delete the old vector. This process will take a long time.

    Unlike other languages, say, Java, the API uses int[] array. The size of the array is fixed and the accessing of the array is pretty fast. No "push_back" action is required.


  • 0

    Your answer may be right,
    but my solution does not use a vector, I only used a pointer and it will allocate enough space once. Even though, my solution is still 500ms+. I think there may be more reasons.


  • 0
    Q

    I just did this test, allocating enough space at the beginning, still really slow...

    NumArray(vector<int> &nums) {
    sums[0] = 0;
    for(int i=0; i<nums.size(); ++i) {
    sums[i+1] = sums[i]+nums[i];
    }
    }

    int sumRange(int i, int j) {
        return sums[j+1]-sums[i];
    }
    private:
    int sums[200000];

  • 0

    yeah,your test is exactly my solution.
    So my words is that there may be more reasons lead to the slow run time, your "pushback()" statement may have some impact but not that seriously.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.