The constant of small vector may be huge!
Разница между en1 и en2, 170 символ(ов) изменены
When solving AtCoder Grand Contest 044 Problem B, I wrote some O(n^3) code with n<=500 like:↵


~~~~~↵
typedef vector<int> vi;↵
vector<vi> dirs({{0,1}, {0,-1}, {-1,0}, {1,0}});↵
...↵
for (auto 
vidir : dirs){ // run O(n^3) times↵
...↵
}↵
~~~~~↵



and get TLE. On my pc it runs within 4900ms.↵
During the contest I have no idea why.(dumb me)↵
After the contest I looked at other people's solution and finally get accepted solution, just add an '&' after 'auto':↵


~~~~~↵
for (auto& vidir : dirs){ // run O(n^3) times↵
...↵
}↵
~~~~~↵


480 ms on my pc! 10 times faster!↵

I did more tests:↵

~~~~~↵
for (int dd = 0; dd<4; ++dd){ // run O(n^3) times↵
    vi dir = dirs[dd];↵
~~~~~↵


4900 ms↵


~~~~~↵
for (int dd = 0; dd<4; ++dd){ // run O(n^3) times↵
    vi& dir = dirs[dd];↵
480 ms↵
~~~~~↵


480 ms↵


~~~~~

vi dir;↵
for (int dd = 0; dd<4; ++dd){ // run O(n^3) times↵
    dir = dirs[dd];↵
~~~~~↵


1800 ms↵

Maybe vector is too big, I tried pair:↵

~~~~~↵
vector<pair<int, int>> dirs({{0,1}, {0,-1}, {-1,0}, {1,0}});↵
for (auto dir : dirs){ // run O(n^3) times↵
~~~~~↵


370 ms, ↵
no difference if I add ‘&’, maybe because pair of int is the same size as 64 bit pointers.↵

Final co
unclusion:↵
Seems like ↵

~~~~~↵
for (auto vi : dirs)↵
~~~~~↵


is equivalent to↵

~~~~~↵
for (int dd = 0; dd<4; ++dd){ // run O(n^3) times↵
    vi dir = dirs[dd];↵
~~~~~↵


that will construct a vector and assignment another vector to it every iteration. which cost much more time than simple data structures or referaence.↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский iynaur87 2020-05-24 02:00:01 55
en3 Английский iynaur87 2020-05-24 01:53:10 3 Tiny change: 'for (auto vi : dirs)\n' -> 'for (auto dir : dirs)\n'
en2 Английский iynaur87 2020-05-24 01:51:42 170
en1 Английский iynaur87 2020-05-24 01:47:06 1407 Initial revision (published)