abba5's blog

By abba5, history, 6 weeks ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +35
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by abba5 (previous revision, new revision, compare).

»
6 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by abba5 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +1 Vote: I do not like it

That's why I prefer using comparators