Why does global vector avoid TLE

→ Обратите внимание

До соревнования
Educational Codeforces Round 167 (Rated for Div. 2)
31:59:52
Зарегистрироваться »

→ Трансляции

Codeforces Educational Round 167 Solution Discussion (with Shayan)

Shayan

До начала 34:04:52

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3845
2	jiangly	3707
3	Benq	3630
4	orzdevinwang	3573
5	Geothermal	3569
5	cnnfls_csy	3569
7	jqdai0815	3532
8	ecnerwala	3501
9	gyh20	3447
10	Rebelz	3409

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	171
2	adamant	163
3	awoo	161
4	nor	152
5	maroonrk	151
5	-is-this-fft-	151
7	TheScrasse	148
8	atcoder_official	146
9	Petr	145
10	pajenegod	144

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Why does global vector avoid TLE

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

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/

Itachi_Uchiha13
5 недель назад
12

Комментарии (12)

Написать комментарий?

funcdfs

5 недель назад, # |

← Rev. 2 →

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.

→ Ответить

funcdfs

5 недель назад, # ^ |

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()
}

→ Ответить

Itachi_Uchiha13

5 недель назад, # ^ |

+11

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.

→ Ответить

Actium

5 недель назад, # |

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

→ Ответить

Itachi_Uchiha13

5 недель назад, # ^ |

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.

→ Ответить

Actium

5 недель назад, # ^ |

+10

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

→ Ответить

Itachi_Uchiha13

5 недель назад, # ^ |

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.

→ Ответить

Actium

5 недель назад, # ^ |

+15

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

→ Ответить

_Kee

4 недели назад, # ^ |

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.

→ Ответить