rahul_1234's blog

sort comp() vs sort()
By rahul_1234, history, 8 years ago, In English

In the problem https://www.codechef.com/problems/CHEFQUE,

submission : https://ideone.com/l2LPvy got TLE. It used comp().

However, when I didn't use comp() and just used sort( vc.begin(), vc.end() ) it got accepted. Submission link https://ideone.com/NgbwUO.

Even though both are doing same thing, why comp() is giving TLE and how can we improve on it. Please somebody guide me on this.

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

Comments Comments (20)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://pastebin.com/mbgLg1Dk

Should get AC

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I think the problem is that using a function pointer for the comparison wastes a lot of time in function calls. The second version uses the comparison operator directly.

In your example, there are 281009016 calls to comp(). This takes its toll. Passing arguments by reference saves ~0.5s. Unfortunately, it seems the compiler ignores inlining the function. So, I don't see better than just avoid using comp() here.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Change bool comp( pair<...> pa1, pair<...> pa2 ) to bool comp( const pair<...>& pa1, const pair<...>& pa2).

Remember that in C++, passing variables to a function copies the variables each time you call it. In your case, you are passing a pair<pair<ll, int>, bool>, which uses around 24 bytes if I'm not mistaken. In essence, by just passing your pair you already did work. What more if you did it n log n times in a sort, you get an overhead factor of 24.

The thing is, you can bypass the default parameter copy by declaring it as a constant reference. Use bool comp(const TYPE& a, const TYPE& b) instead of bool comp(TYPE a, TYPE b). By doing so, instead of copying your variables everytime, you just copy its address but reference the same variable. Normally, addresses are just around 4 bytes... 20 bytes less!

The reason why the default pair sort is faster is because C++ STL implements constant referencing in all its default sorts. It's the standard.

EDIT: It seems you already tried the constant reference but it's still TLE? Why don't you try

inline bool comp(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) {
    return pa1.f.f < pa2.f.f || (pa1.f.f == pa2.f.f && pa1.f.s < pa2.f.s);
}

~~~~~

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This too https://ideone.com/ANL4Xo is giving TLE. Above BekzhanKassenov suggested the same but the code is producing TLE on codechef.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Moreover it is taking 3.5s while without comp() the code is taking 2.7s on ideone. So, is there any other method which brings execution time to approx 2.7s?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        That's really weird. I tried some submissions. Here's what I found.

        inline function pointer, equal before less: TLE

        inline bool comp(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) {
    if (pa1.f.f == pa2.f.f)
    	return pa1.f.s < pa2.f.s;
    return pa1.f.f < pa2.f.f;
}

        inline function pointer, less before equal: TLE

        inline bool comp(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) {
    return pa1.f.f < pa2.f.f || (pa1.f.f == pa2.f.f && pa1.f.s < pa2.f.s);
}

        struct comparator, equal before less: TLE

        struct comp {
    inline bool operator()(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) const {
        if (pa1.f.f == pa2.f.f)
        	return pa1.f.s < pa2.f.s;
        return pa1.f.f < pa2.f.f;
    }
};

        struct comparator, less before equal: Accepted 1.76s

        struct comp {
    inline bool operator()(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) const {
         return pa1.f.f < pa2.f.f || (pa1.f.f == pa2.f.f && pa1.f.s < pa2.f.s);
    }
};

        I found out that the last one, according to WikiBooks, is the "most optimal one", though I don't know yet why it's optimal. Weird.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          It got accepted using inline function. Thanks a lot.

          Can u plz explain why it got accepted now but was giving TLE before?

          Again thanks a lot.

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          I think the answer to why is at the end of the section you linked: "Function-objects are usually expanded inline and are therefore as efficient as in-place code, while functions passed by pointers are rarely inlined."

          I didn't expect the compiler to treat them so differently regarding inlining.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            But previously I suggested version with functor and rahul_1234 said that it's TLE. Your version differs from mine only with word inline. AFAIK all member functions in class/struct are inline by default?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 2   Vote: I like it +1 Vote: I do not like it

              U can check urself by submitting on problem link given above. That was producing TLE but using inline works.

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I've never heard that member functions are inline by default. I don't think so, but don't have a reference at hand at the moment.

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              inline generally tells the compiler "hey, compile me without using a function stack as if I'm being run in the same line." It's like a macro, but it's not. Not sure how it works assembly level, I just know it's really fast because it's like a direct command.

              → Reply