I was solving 1955G - НОД на клетчатом поле, 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/
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.
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.
Your second version differs from the first one not only in moving the
ispossvector to the global namespace. Namely, in the first version you initializedisposswith default values every call while in the second version you usedresize()that does not re-assign default values to existing elements, only to ones in extension. Also there are some assignments to elements ofispossmissing in the first version (maybe they change time complexity, I do not know).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.
Yes, it seems like slow memory allocator. Besides, I changed the TLEed version (replaced vector with array) and it passed tests: 262492049.
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.
Here is the TLEed version with 1D-vector: 262495379 (also passes tests). You can make some conclusions :)
A
vectorinitializes each element upon creation, while anarraykeeps the memory uninitialized (unless you explicitly initialize it). Usually this difference is negligible, but they are surely different.Auto comment: topic has been updated by Itachi_Uchiha13 (previous revision, new revision, compare).
Auto comment: topic has been updated by Itachi_Uchiha13 (previous revision, new revision, compare).
Reference — link