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 :)
Auto comment: topic has been updated by fresher96 (previous revision, new revision, compare).
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::mapis 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
stackpart of the memory, and accessingA[i]will be the same as using a declared variable. Whereas,std::vectorwill be allocated in theheapwhich isn't linear and is less efficient than thestack.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.So, have you gotten any fresher in the past 4 years?
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.
I think your point about vectors not being contiguous in memory is incorrect, see this.
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?
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.
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::setinstead of using a static array and doing binary search manually.By small size, you mean for example under 1000 or under 10000? Or sth else?
The overhead of a vector is 24/48 bytes on 32/64 bit compilers.
intsare 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 usestd::arrayfor that.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?
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.
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::vectoralso has to allocate it.static std::vectorwithstd::fillhas 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]{};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.