Why does global vector avoid TLE

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

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:46:52
Зарегистрироваться »

*есть доп. регистрация

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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

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

Всё →

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

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

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

→ Прямой эфир

Детальнее →

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

Why does global vector avoid TLE

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

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
6 месяцев назад
12

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

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

funcdfs

6 месяцев назад, # |

← 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

6 месяцев назад, # ^ |

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

6 месяцев назад, # ^ |

+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

6 месяцев назад, # |

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

6 месяцев назад, # ^ |

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

6 месяцев назад, # ^ |

+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

6 месяцев назад, # ^ |

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

6 месяцев назад, # ^ |

+15

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

→ Ответить

_Kee

6 месяцев назад, # ^ |

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.

→ Ответить