Itachi_Uchiha13's blog

Why does global vector avoid TLE
By Itachi_Uchiha13, history, 3 weeks ago, In English

I was solving 1955G - GCD on a grid, and I made 2 submissions. The first one 262439330 which gave TLE. The second one 262487569 ran in just 765ms.

The only change I made in these 2 submissions is that I declared a vector isposs globally instead of declaring it again in the function isPoss. Does memory allocation in C++ really have such a large overhead, or is there any other reason? I mean it takes more than 4x time to run, which is unexpected to me.

Link of diff: https://www.diffchecker.com/vVXUaFzd/

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

»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

because of the code logic is TLE. Opening an array is generally of a linear complexity rather than O(1). It has nothing to do with being global or not. When n and m are large enough, your tle code is equivalent to doing an additional traversal each time.

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

    Allocating an array space and initializing it is always O(n). The correct way to write it should be your global writing method, or.

    #include <xxx>
int solve() {
  vector<vector<int>> yourvector(n, vector<int>(m,0))
  fution<> useYourVector() -> bool {
    cleardata()
    then use vector
  };
  return; 
}

int main() {
 solve()
}
    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Yes I know memory allocation is not O(1). But since the function is anyways O(n*m) it should not make much of a difference to create a vector of dimensions n*m. I have made a small update, I hope that makes it more clear what I am trying to say.

    → Reply
»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Your second version differs from the first one not only in moving the isposs vector to the global namespace. Namely, in the first version you initialized isposs with default values every call while in the second version you used resize() that does not re-assign default values to existing elements, only to ones in extension. Also there are some assignments to elements of isposs missing in the first version (maybe they change time complexity, I do not know).

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Please take a look at this submission 262487569. The difference of the first one is that I have kept isposs global, and I am assigning default values each time in isPoss function.

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

      Yes, it seems like slow memory allocator. Besides, I changed the TLEed version (replaced vector with array) and it passed tests: 262492049.

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Wow that's surprising, it probably means vector allocation is slow in C++. If I find an answer to why this is happening I'll update it here.

        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          Here is the TLEed version with 1D-vector: 262495379 (also passes tests). You can make some conclusions :)

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

          A vector initializes each element upon creation, while an array keeps the memory uninitialized (unless you explicitly initialize it). Usually this difference is negligible, but they are surely different.

          → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Reference — link

→ Reply