sort comp() vs sort()

http://pastebin.com/mbgLg1Dk

9 years ago, # |

Should get AC

→ Reply

9 years ago, # ^ |

← Rev. 3 →

It is giving me TLE. Moreover, there is significant difference in time too if u see the link on ideone. One is taking 2.7s while other approx 5s.

→ Reply

9 years ago, # ^ |

What about this one? http://pastebin.com/GZmjve72

→ Reply

9 years ago, # |

+11

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

Hikari9

9 years ago, # |

← Rev. 3 →

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

9 years ago, # ^ |

← Rev. 2 →

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

→ Reply

9 years ago, # ^ |

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

Hikari9

9 years ago, # ^ |

+12

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

9 years ago, # ^ |

← Rev. 2 →

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

9 years ago, # ^ |

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

9 years ago, # ^ |

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

9 years ago, # ^ |

← Rev. 2 →

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

→ Reply

9 years ago, # ^ |

I don't have codechef account :)

→ Reply

9 years ago, # ^ |

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

https://isocpp.org/wiki/faq/inline-functions#inline-member-fns

9 years ago, # ^ |

→ Reply

9 years ago, # ^ |

The standard says that the declaration of inline and non-inline looks the same. This is not saying that member-functions are inline. The inline keyword is put on the member-function definition.

You can see in the example. The first is the declaration and the second is the definition.

→ Reply

9 years ago, # ^ |

Alright, from next section https://isocpp.org/wiki/faq/inline-functions#inline-member-fns-more it follows that my version was inlined :)

→ Reply

9 years ago, # ^ |

Interesting, I hadn't read the other sections of the page. The compiler decided to ignore it then, but accepts the inline suggestion when we specifically write inline.

→ Reply

Hikari9

9 years ago, # ^ |

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