Блог пользователя fresher96

Автор fresher96, история, 8 лет назад, По-английски

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 :)

  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        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.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится +21 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        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]{};

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        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.