fresher96's blog

noob question related to std::vector
By fresher96, history, 8 years ago, In English

hi all, i have two simple questions if anyone can help.

first, please see this submission 20349642 and press the compare button. it will be compared with this submission 20349625. the code is long so don't be distracted.
what i want to know is why the first code gets AC while the second one gets Time limit exceeded on test 10. i even tested the second submission in gym and it got Time limit exceeded on test 39 (i set the time limit to 30 seconds).
i can't really see where does this huge difference come from.

second, there exists a huge difference between using vectors and static arrays. here, the size of the vector is fixed and i use passing with reference (even that the sizes of the vectors are very small 2×2). so there shouldn't be a big difference with using arrays. when i used the same code with arrays there was about 500 ms difference.
is there something to do that will make vectors faster (like using reserve function for push_back) or one simply should use arrays for a better performance?

thanks in advance. any help is appreciated :)

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by fresher96 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

It has been quite a while since I asked this question, but here are my thoughts after some more experience.

Using STL in general will results in a big constant factor in your time complexity. For example, in some sense, we can say that the $$$O(lgn)$$$ of using stl::map is bigger than the $$$O(lgn)$$$ of using a hand coded simple binary search or a Fenwick tree.

For this question, the difference also may be related to internal memory management in the library. In C++, declaring a static array and accessing it is quite efficient. The array will be allocated a contiguous slice in the stack part of the memory, and accessing A[i] will be the same as using a declared variable. Whereas, std::vector will be allocated in the heap which isn't linear and is less efficient than the stack.
Especially, that in this code I was using a nested vector< vector<int> >, so although the size is small $$$2 \times 2$$$, the memory allocation is probably quite inefficient and even accessing an element will be $$$O(1)$$$ with a big constant.

As an analogy, this seems to be similar to the difference in efficiency between using + - and % /. They both are $$$O(1)$$$ operators but in some tricky problems where the complexity is critical and barely passes the time limit, this is a deciding factor.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    So, have you gotten any fresher in the past 4 years?

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    we can say that the O(lgn) of using stl::map is bigger than the O(lgn) of using a hand coded simple binary search or a Fenwick tree

    Obviously the former will be slower than later(mostly) because Big O notation O(lgn) in map does not include constant factors(like height of rb-tree can be twice 2*logn), while with standard binary search / fenwick tree it's strictly O(lgn) considering that array lookup is O(1), these might also benefit from caching(when array is not too large) while that's not the case with rb-tree but it may or may not be very much noticable difference.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    I think your point about vectors not being contiguous in memory is incorrect, see this.

    → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I clicked on your submission & Compare and it appears that the newer version multiplies a couple ints instead of a multiplying matrices... doesn't that explain why there's a huge time difference?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Exactly. One version computes two multiplications, and the other creates two matrices and computes eight multiplications.

    Regarding array vs. vector speed: use array if size is small. If size is big, the difference is negligible.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Yes, thank you, you are both right.

      I remember that I asked this question as I thought it was important, because once in our national contest, a team got TLE instead of AC for a similar reason. They used std::set instead of using a static array and doing binary search manually.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      By small size, you mean for example under 1000 or under 10000? Or sth else?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        The overhead of a vector is 24/48 bytes on 32/64 bit compilers. ints are 4 bytes each. By the time you get to 10/20, the overhead becomes negligible. Generally, if your array is of such small size, its constant, like storing 3 things, or something like that. So you can use std::array for that.

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      AC using an array

      TLE using vector

      The size is big order of 10**5 but still, there is a huge difference in time. I don't understand the reason. Can you please explain?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        You create a vector of size 1e5 for each of T=1e4 test cases. That's obviously too slow.

        Your accepted submission doesn't clear the array every time. I guess it's UB.

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it +4 Vote: I do not like it

        Both submissions have the issue Errichto mentioned: you make a lot of unnecessary operations because of the fixed size you use. While stack array only has to initialize a huge memory chunk for each test case, std::vector also has to allocate it. static std::vector with std::fill has about the same performance here as static and stack-allocated arrays and identical (where it matters) assembly (vector, static array, same vector but unlucky)

        I think there's no UB in your accepted solution: all array elements after the first are zero-initialized, same as if you'd have written int d[262144]{};

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Thanks a lot for help. I now understand the mistake I was doing and the difference between vector and array which was causing the time difference.

        → Reply