### abba5's blog

By abba5, history, 6 weeks ago,

I was trying to submit this -> Remove Max Number of Edges to Keep Graph Fully Traversable question.
but I got TLE because of sort using rbegin

sort( edges.rbegin(), edges.rend())


but after change with comparator funtction code got accepted.

sort(edges.begin(), edges.end(), [&](vector <int> &a, vector <int> &b){
return a[0] > b[0];
});


Submission Using rbegin

Submission Using comparator

I tried to run this in local and got similar performance but when I used some different build command I got 2x time difference for $N = 10^5$

Build command:

1. g++ a.cpp

2. g++ -std=c++17 -Wshadow -Wall -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -DLOCAL a.cpp

output using 1st build command:

0.0290290006s
0.0652360022s


output using 2nd build command:

0.9816750288s
2.1033749580s


Following code I used for bench-marking.

Bench-marking code

Can anyone explain why this time difference happening?
Will this happen in code-forces also?

• +35

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by abba5 (previous revision, new revision, compare).
 » 6 weeks ago, # | ← Rev. 2 →   +4 same thing happened to me last month..... was using sort(vector.rbegin(),vector.rend()) and got tle.....after the contest i used sort(vector.begin(),vector.end(),greater()) and then got AC... i used to thought that complexity of both sorting is same
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by abba5 (previous revision, new revision, compare).
 » 6 weeks ago, # |   +2 Can anyone explain why this time difference happening? It is happening because you have used the compile flags without knowing what they do.-D_GLIBCXX_DEBUG: it inserts some debug / sanity checks that can really slow your code down. For example, you may get $O(n)$ complexity for std::binary_serach.And you forgot the most important flag -O2. With -O2 both of them takes same time.
•  » » 6 weeks ago, # ^ |   0 Thanks for the comment.I tried using -O2 flag and found it does make a difference. Using it with Debug flag is still slow.I think leetcode people are not using this flag as well, thus the TLE.Keeping that aside, still building only with g++ also results in a large difference in run time of the two methods to sort. I didn't notice that before. Can you please explain how that might be happening?Thanks in advance
 » 6 weeks ago, # |   +1 That's why I prefer using comparators